Для доказательства того, что сложность алгоритма TTSVD (Truncated Tensor Singular Value Decomposition) составляет $O(N^4)$, необходимо рассмотреть ключевые этапы алгоритма и определить, какие вычисления вносят основной вклад в общую сложность.

1. Краткий обзор алгоритма TTSVD

TTSVD используется для разложения многомерных данных (тензоров) в TT-формат (Tensor Train). Основные этапы алгоритма:

1. Последовательное вычисление матриц через тензоры и разложение их с помощью SVD (сингулярного разложения).
2. Транспонирование, перестановка и уменьшение размера данных на каждом этапе.
3. Ограничение рангов до заданного значения $r$ (ранжирование).

Теперь мы определим сложность каждого этапа.

---

2. Основной вклад в вычислительную сложность

(а) Применение SVD

SVD является центральным шагом TTSVD. Пусть исходный тензор имеет размеры ( N \times N \times \cdots \times N \