Метод попеременных линейных схем для оптимизации тензоров в формате Tensor Train

Недавние достижения в области приближения тензорных произведений предлагают перспективные новые форматы представления тензоров в виде древовидных тензорных сетей. В отличие от канонического r-членного представления (CANDECOMP, PARAFAC), эти новые форматы обеспечивают устойчивые представления при чуть большем объёме требуемых данных. Формат tensor train (TT) [SIAM J. Sci. Comput., 33 (2011), pp. 2295–2317], простой частный случай иерархического формата Таккера (hierarchical Tucker) [J. Fourier Anal. Appl., 5 (2009), p. 706], является полезным прототипом для практического представления тензоров низкого ранга. В этой статье мы показываем, как задачи оптимизации можно рассматривать в формате TT посредством обобщения алгоритма попеременных наименьших квадратов (ALS) и модифицированного подхода (MALS), позволяющего динамически адаптировать ранги. Формулировка компонентных уравнений в терминах так называемых операторов ретракции помогает продемонстрировать, что многие структурные свойства исходных задач переносятся на микро-итерации, что, насколько нам известно, даёт первый устойчивый универсальный алгоритм для решения задач оптимизации в тензорном формате. На примерах линейных систем и собственных задач мы выводим конкретные рабочие уравнения для шагов микро-итераций; численные примеры подтверждают теоретические результаты, касающиеся устойчивости разложения TT и алгоритмов ALS и MALS, но также показывают, что в некоторых случаях при итеративном приближении тензоров низкого ранга требуются высокие TT-ранги, указывая на возможности для дальнейшего улучшения.