Журнал вычислительной математики и математической физики, 2019, T. 59, № 2, стр. 211-216

Тензорные поезда, впервые предложенные в [1], стали популярным инструментом приближения тензоров благодаря небольшим затратам памяти $O(dnr + d{{r}^{3}})$, высокой скорости выполнения операций (для малых рангов такая же асимптотика, как для канонического разложения) и быстрому алгоритму построения (см. [2]) с помощью крестовых аппроксимаций матриц развертки, для которых применяется алгоритм ${\text{maxvol}}$ [3]. Данный алгоритм позволяет найти подматрицу $\hat {A}$, объем которой ${{V}_{2}}(\hat {A}) = \operatorname{vol} (\hat {A}) = {\text{|}}\det \hat {A}{\text{|}}$ нельзя уменьшить заменой лишь одной строки или столбца. В том случае, когда объем найденной матрицы оказывается максимальным или почти максимальным (что часто выполняется на практике) среди подматриц, отличающихся не более, чем одной строкой и одним столбцом, можно гарантировать высокую точность построенной на основе $\hat {A}$ крестовой аппроксимации по норме Чебышёва.

Теорема 1 (см. [4]). Пусть матрица $A \in {{\mathbb{C}}^{{M \times N}}}$ имеет следующую блочную форму:

где подматрица ${{A}_{{11}}} \in {{\mathbb{C}}^{{r \times r}}}$, $\operatorname{rank} {{A}_{{11}}} = r$ обладает максимальным объемом среди всех подматриц размера $r \times r$. Рассмотрим псевдоскелетную аппроксимацию матрицы $A$, построенную на столбцах $C = \left[ {\begin{array}{*{20}{c}} {{{A}_{{11}}}} \\ {{{A}_{{21}}}} \end{array}} \right]$ и строках $R = \left[ {\begin{array}{*{20}{c}} {{{A}_{{11}}}}&{{{A}_{{12}}}} \end{array}} \right]$, используя в качестве ядра $G$ матрицу $A_{{11}}^{{ - 1}}$. Тогда выполняется следующая оценка: где ${{\left\| E \right\|}_{C}}$ – ошибка наилучшего приближения $A$ по $C$-норме (норме Чебышёва), В случае, когда объем ${{A}_{{11}}}$ отличается от максимального в $\alpha \geqslant 1$ раз, получим

Попытки прямого обобщения данной и похожих оценок на тензоры вызывают часто встречающуюся в таких случаях трудность – появление в коэффициенте множителя, экспоненциально зависящего от размерности тензора $d$. Такие оценки для разложения Таккера были впервые получены в [5] (случай $d = 3$) и обобщены и улучшены в [6].

В данной статье будут доказаны оценки погрешности аппроксимации тензоров по норме Чебышёва с коэффициентом, пропорциональным ${{r}^{{lo{{g}_{2}}d}}}$ вместо ${{r}^{d}}$, что гарантирует высокую точность аппроксимаций даже при большом числе размерностей тензора.

Стоит отметить, что в [7] уже была предложена похожая оценка, однако с коэффициентом, зависящим от максимального числа обусловленности $\kappa = {{\left\| {\hat {A}} \right\|}_{C}}{{\left\| {{{{\hat {A}}}^{{ - 1}}}} \right\|}_{C}}$ среди всех используемых при построении подматриц $\hat {A}$, который ничем не ограничен. Например, если

то матрица максимального объема размера $2 \times 2$ равна: и $\kappa = 1{\text{/}}\varepsilon $. В результате оценка ошибки не будет убывать при уменьшении $\varepsilon $, хотя ошибка наилучшего приближения стремится к нулю.

Итак, пусть нам дан $d$-мерный тензор $A$ с индексами столбцов ${{i}_{1}},\;...,\;{{i}_{d}}$. Его мы будем обозначать через $A\left( {{{i}_{1}},\; \ldots ,\;{{i}_{d}}} \right)$. Буквой $J$ далее будем обозначать мультииндексы, содержащие в себе значения одновременно нескольких ${{i}_{k}}$. При записи в скобках это означает, что несколько индексов объединены в один, что уменьшает размерность тензора. Например, матрица $A({{i}_{k}},{{J}^{{ \ne k}}})$ является $k$-й матрицей развертки тензора $A$. Ее строки соответствуют индексу ${{i}_{k}}$, а столбцы, наоборот, соответствуют столбцам тензора $A$, когда все индексы, кроме ${{i}_{k}}$, фиксированы и их значения хранятся в мультииндексе ${{J}^{{ \ne k}}}$.

Мы будем приближать заданный нам тензор способом, аналогичным предложенному в [2]:

где $d$ – число измерений тензора, $J_{{{{t}_{k}}}}^{{ > k}}$ – часть номеров столбцов, выбранных среди мультииндекса ${{J}^{{ > k}}} = \overline {{{i}_{{k + 1}}} \ldots {{i}_{d}}} $. Аналогично, $J_{{{{s}_{k}}}}^{{ \leqslant k}}$ представляет из себя выбор части номеров строк из мультииндекса ${{J}^{{ \leqslant k}}} = \overline {{{i}_{1}} \ldots {{i}_{k}}} $. Если все подматрицы вида состоят из $r$ строк и столбцов, то мы получаем некоторое приближение ранга $r$.

Для случая $d = 2$ мы получаем известное псевдоскелетное разложение матрицы:

Здесь и далее индекс $\tau $ обозначает $\tau $-псевдообращение: перед взятием псевдообратной матрицы все сингулярные числа, меньшие $\tau $, зануляются. Это позволяет ограничить 2-норму $\tau $-псевдообратной матрицы значением $1{\text{/}}\tau $, так как при псевдообращении нулевые сингулярные числа остаются нулевыми. Индекс $r$ будет обозначать, что у матрицы все сингулярные числа после $r$-го (с нумерацией по убыванию) приравниваются нулю. Когда используются сразу два индекса, $\tau $ и $r$, это означает, что считаются нулевыми все сингулярные числа, меньшие $\tau $ или с номером, большим $r$. Индекс $k$ при этом, как и ранее, будет использоваться только для обозначения того, что это матрица вида (4).

Если ${{A}_{k}} \in {{\mathbb{C}}^{{r \times r}}}$ обладает максимальным объемом, а $\tau = 0$, то из теоремы 1 известна оценка на $C - {\text{н о р м у }}$ приближения (5):

где $F$ – наилучшее по $C$-норме приближение ранга $r$.

Вместо ${{i}_{1}}$ и ${{i}_{2}}$ в (5) можно подставить мультииндексы. В частности,

Далее можно рассмотреть уже тензоры столбцов $C = A\left( {{{J}^{{ \leqslant k - 1}}},{{i}_{k}},J_{{{{t}_{k}}}}^{{ > k}}} \right)$ и строк $R = A\left( {J_{{{{s}_{k}}}}^{{ \leqslant k}},{{i}_{{k + 1}}},{{J}^{{ > k + 1}}}} \right)$ по отдельности, перегруппировать в них индексы и снова применить псевдоскелетное разложение. В конечном итоге, продолжая эту процедуру, получаем структуру вида (3). Оценим $C$-норму погрешности аппроксимации такого представления тензора.

Теорема 2. Для любого тензора $A = A\left( {{{i}_{1}},\; \ldots ,\;{{i}_{d}}} \right)$ существует его приближение $\tilde {A}$ вида (3) такое, что

где $F$ – наилучшее по $C$-норме приближение тензора $A$ ранга $r$.

Доказательство. Итак, выбрав в матрице-развертке тензора подматрицу максимального объема $\hat {A}$, на первом шаге мы получим разложение следующего вида:

где через $A$ будем уже обозначать матрицу развертки, а $\hat {A}$ – матрицу на пересечении столбцов $C$ и строк $R$, $E$ – погрешность такой аппроксимации.

Далее мы строим разложение для тензоров, соответствующих матрицам $C$ и $R$. В конечном итоге, получим некоторые приближения этих тензоров:

На каждом шаге мы будем использовать разложение ранга $r$, то есть $r$ строк и столбцов. Если каждый раз при построении матриц развертки делить индексы примерно поровну, то конечный результат будет достигнут не более, чем за $\left\lceil {\mathop {log}\nolimits_2 d} \right\rceil $ шагов. При этом погрешность, которая окажется на $k$-м слое (шаге), будет оцениваться следующим образом (для простоты индекс $k$, который здесь является верхним, чтобы не путать с подматрицей ${{A}_{k}}$, далее будет опущен): где ${{\varepsilon }_{{k + 1}}}$ – оценка для наибольшей погрешности на $k + 1$-м слое. Таким образом, нужно выбрать такую оценку ${{\varepsilon }_{k}}$, чтобы гарантировать неравенство При этом при $k = [\mathop {log}\nolimits_2 d]$ можно считать значение ${{\varepsilon }_{k}}$ равным оценке для ${{\left\| E \right\|}_{C}}$ для всего тензора.

Для начала оценим погрешность $E$:

Одним из свойств подматрицы максимального объема является то, что 2-норма строк $C{{\hat {A}}^{{ - 1}}}$ не превосходит $\sqrt r $. Оно следует напрямую из соотношения которое доказано в [8]. То же верно и для 2-нормы столбцов ${{\hat {A}}^{{ - 1}}}R$. $C$-норма произведения трех матриц далее оценивается через произведение максимальной $2$-нормы строк первой матрицы, $2$-нормы второй матрицы и максимальной $2$-нормы столбцов третьей матрицы: Поэтому для $C$-нормы погрешности будет верно следующее соотношение с учетом (7): Теперь оценим остальные слагаемые, применяя, где необходимо, выражение (7) и оценивая 2-норму строк и столбцов через $C$-норму: Взяв $\tau = {{\varepsilon }_{{k + 1}}}$, получим следующую оценку для погрешности на k-м слое: Таким образом, достаточно взять Суммируя полученную в результате раскрытия рекурренты геометрическую прогрессию, получаем оценку (6).

Оценку (6) можно улучшить, если использовать $n > r$ строк и столбцов. В этом случае в качестве $\hat {A}$ нужно использовать подматрицу максимального $r$-проективного объема, т.е. обладающую максимальным произведением первых $r$ сингулярных чисел:

Крестовая аппроксимация на основе максимального проективного объема была подробно исследована в [9], где, в частности, были получены следующие оценки: где ${{R}_{i}}$ – произвольная строка матрицы $R$, а ${{C}_{j}}$ – произвольный столбец $C$, не содержащиеся в $\hat {A}$. Для столбцов и строк из $\hat {A}$ в правой части неравенств будет 1, а потому они остаются верными, пока $n \leqslant 2r - 1$.

Теорема 3. Для любого тензора $A = A\left( {{{i}_{1}},\; \ldots ,\;{{i}_{d}}} \right)$ существует его приближение $\tilde {A}$ вида (3) такое, что

где $F$ – наилучшее по $C$-норме приближение тензора $A$ ранга $r$, а $n \leqslant 2r - 1$.

Доказательство проводится полностью аналогично случаю $n = r$. В качестве матрицы $B$ будем использовать $\hat {A}_{{\tau r}}^{ + }$. Нам снова нужно оценить каждое из слагаемых погрешности на $k$-м слое:

Для этого воспользуемся выражениями (9) и (10): Полагая $\tau = \sqrt {\tfrac{{n(n - r + 1)}}{r}} {{\varepsilon }_{{k + 1}}}$, получаем, что можно выбрать Здесь снова можно просуммировать геометрическую прогрессию, что даст в итоге (11).

Следствие. Выбрав $n = 2r - 1$, получим оценку

Как видим, в случае тензоров, как и в случае матриц, дополнительные $r - 1$ строк и столбцов позволяют уменьшить в два раза степенную зависимость коэффициента от $r$.

Насколько данные оценки могут быть близки к реальному положению дел? Рассмотрим для простоты оценку (1) для матриц. В ней присутствует коэффициент ${{(r + 1)}^{2}}$. Численные эксперименты со случайными матрицами в [9] показали коэффициент вида ${{(\alpha r + 1)}^{2}}$ с достаточно малым $\alpha $ вместо коэффициента ${{(r + 1)}^{2}}$. В результате предсказанная оценкой квадратичная зависимость наблюдалась лишь на очень больших рангах, когда ${{\alpha }^{2}}{{r}^{2}} > > 1$. Что касается коэффициента, который возводится в степень $lo{{g}_{2}}d$, то для него также разумно предположить, что, например, 2-норма строк ${{E}_{C}}$ изменяется как $\sqrt {q + \alpha n} {{\left\| {{{E}_{C}}} \right\|}_{C}}$. Это означает, что на практике экспоненциальная зависимость от $lo{{g}_{2}}d$ будет заметна лишь на очень больших рангах, в то время как при достаточно малых рангах зависимость будет не более, чем степенной или даже линейной: в случае малости погрешности даже при больших $\tau $ верно равенство ${{\hat {A}}_{\tau }} = {{\hat {A}}_{r}}$, которое исключает одно из слагаемых и почти сводит к нулю ${{\left\| {{{E}_{C}}B{{E}_{R}}} \right\|}_{C}}$, поэтому в итоге в степень $lo{{g}_{2}}d$ будет возводиться число, близкое к 2.

Например, для $r = 1$ можно выбрать $\tau = {{\sigma }_{1}}(\hat {A}) \geqslant {{\left\| A \right\|}_{C}} \geqslant {{\left\| F \right\|}_{C}}$, что уже исключает необходимость $\tau $-псевдообращения. И тогда

Более того, ${{\left\| {{{E}_{C}}B{{E}_{R}}} \right\|}_{C}}$ может уменьшать погрешность, а не увеличивать, и тогда $O(\left\| F \right\|_{C}^{2}/{{\left\| A \right\|}_{C}})$ также исчезнет. Более глубокий анализ может позволить полностью избавиться от двух слагаемых даже при больших рангах.

Ранг 1 также можно рассматривать как частный случай канонического разложения, что при малых значениях погрешности приводит к оценке вида

При $d = 2$ данная оценка совпадает с (12). При этом легко привести пример последовательности тензоров, для которой оценка (13) достигается, когда величина погрешности стремится к нулю. Например, для ${{\left\| F \right\|}_{C}} = \varepsilon $, а погрешность построенной на основе максимального элемента (что соответствует максимальному объему для $r = 1$) аппроксимации равна Тем не менее, как уже было сказано, как минимум для матриц полученная оценка достигается крайне редко.

В целом точность полученной формулы по некоторым аспектам остается под вопросом и требует проведения соответствующих вычислительных экспериментов с тензорами.

Естественно, рассуждения для среднего не отменяют возможность существования худшего случая, на котором полученная оценка будет достигаться для рангов, больших 1, хотя на данный момент такие примеры неизвестны.

Конечно, возможно также существование оценок по норме Чебышёва, никак не связанных с максимальным объемом или крестовыми аппроксимациями, однако, в матричном случае никаких аналогов, дающих схожие оценки по $C$-норме, автору неизвестны и мало какие алгоритмы способны соревноваться по простоте и скорости построения аппроксимации с крестовым методом.

Также крайне интересны были бы оценки крестовых аппроксимаций, например, по норме Фробениуса, так как в матричном случае известны оценки, сколь угодно близкие к точности сингулярного разложения [10]. Однако за неимением полного аналога $SVD$ для тензоров получение таких оценок до сих пор является крайне сложной задачей.

Вышесказанное еще сильнее подчеркивает важность полученного результата – доказаны такие оценки, аналоги которых пока остаются практически недостижимыми для всех прочих норм и методов.