Тензорное ранговое разложение

В полилинейной алгебре ранга разложение тензорного ^[1] или ранга R разложение - это разложение тензора в сумму R тензоров ранга 1, где R минимально. Вычисление этого разложения является открытой проблемой. ^{[ нужны разъяснения ]}

Каноническое полиадическое разложение (CPD) — это вариант разложения тензорного ранга, в котором тензор аппроксимируется как сумма K тензоров ранга 1 для заданного пользователем K . CP-разложение нашло некоторые применения в лингвистике и хемометрике . Его представил Фрэнк Лорен Хичкок в 1927 году. ^[2] и позже несколько раз заново открывался, особенно в психометрии. ^[3]^[4] Разложение CP называется CANDECOMP, ^[3] ПАРАФАК, ^[4] или CANDECOMP/PARAFAC (CP). Обратите внимание, что ранговое разложение PARAFAC2 является разновидностью разложения CP. ^[5]

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

Обозначения

Скалярная переменная обозначается строчными курсивными буквами: $a$ а верхняя граница скаляра обозначается заглавной курсивной буквой: $A$ .

Индексы обозначаются комбинацией строчных и прописных курсивных букв. $1\leq i\leq I$ . Множественные индексы, с которыми можно столкнуться при обращении к множественным модам тензора, удобно обозначать как $1\leq i_{m}\leq I_{m}$ где $1\leq m\leq M$ .

Вектор обозначается строчной жирной буквой Times Roman, $\mathbf {a}$ а матрица обозначается жирными заглавными буквами $\mathbf {A}$ .

Тензор более высокого порядка обозначается каллиграфическими буквами: ${\mathcal {A}}$ . Элемент $M$ -тензор порядка ${\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\times \dots I_{m}\times \dots I_{M}}$ обозначается $a_{i_{1},i_{2},\dots ,i_{m},\dots i_{M}}$ или ${\mathcal {A}}_{i_{1},i_{2},\dots ,i_{m},\dots i_{M}}$ .

Определение

Тензор данных ${\mathcal {A}}\in {\mathbb {F} }^{I_{0}\times I_{1}\times \ldots \times I_{C}}$ представляет собой набор многомерных наблюдений, организованных в $массив M$ -way, где $M$ = $C$ +1. Каждый тензор можно представить с достаточно большим $R$ как линейная комбинация $r$ Тензоры 1-го ранга:

{\mathcal {A}}=\sum _{r=1}^{R}\lambda _{r}\mathbf {a} _{0,r}\otimes \mathbf {a} _{1,r}\otimes \mathbf {a} _{2,r}\dots \otimes \mathbf {a} _{c,r}\otimes \cdots \otimes \mathbf {a} _{C,r},

где $\lambda _{r}\in {\mathbb {R} }$ и $\mathbf {a} _{m,r}\in {\mathbb {F} }^{I_{m}}$ где $1\leq m\leq M$ . Когда количество членов $R$ минимально в приведенном выше выражении, то $R$ называется рангом тензора, а разложение часто называют разложением (тензорного) ранга , минимальным CP-разложением или каноническим полиадическим разложением (CPD) . Если количество членов не минимально, то приведенное выше разложение часто называют CANDECOMP/PARAFAC , «Полиадическое разложение».

Тензорный ранг

В отличие от случая матриц, вычисление ранга тензора NP-трудно . ^[6] Единственный примечательный и хорошо понятный случай состоит из тензоров в $F^{I_{m}}\otimes F^{I_{n}}\otimes F^{2}$ , ранг которого можно получить из нормальной формы Кронекера – Вейерштрасса линейного матричного пучка , который представляет тензор. ^[7] Существует простой алгоритм с полиномиальным временем для подтверждения того, что тензор имеет ранг 1, а именно разложение по сингулярным значениям более высокого порядка .

Ранг тензора нулей по соглашению равен нулю. Ранг тензора $\mathbf {a} _{1}\otimes \cdots \otimes \mathbf {a} _{M}$ является одним, при условии, что $\mathbf {a} _{m}\in F^{I_{m}}\setminus \{0\}$ .

Полевая зависимость

Ранг тензора зависит от поля, по которому тензор разлагается. Известно, что некоторые действительные тензоры могут допускать комплексное разложение, ранг которого строго меньше ранга вещественного разложения того же тензора. В качестве примера: ^[8] рассмотрим следующий действительный тензор

{\mathcal {A}}=\mathbf {x} _{1}\otimes \mathbf {x} _{2}\otimes \mathbf {x} _{3}+\mathbf {x} _{1}\otimes \mathbf {y} _{2}\otimes \mathbf {y} _{3}-\mathbf {y} _{1}\otimes \mathbf {x} _{2}\otimes \mathbf {y} _{3}+\mathbf {y} _{1}\otimes \mathbf {y} _{2}\otimes \mathbf {x} _{3},

где $\mathbf {x} _{i},\mathbf {y} _{j}\in \mathbb {R} ^{2}$ . Известно, что ранг этого тензора по действительным числам равен 3, а его комплексный ранг равен только 2, поскольку он представляет собой сумму комплексного тензора ранга 1 с его комплексно-сопряженным , а именно

{\mathcal {A}}={\frac {1}{2}}({\bar {\mathbf {z} }}_{1}\otimes \mathbf {z} _{2}\otimes {\bar {\mathbf {z} }}_{3}+\mathbf {z} _{1}\otimes {\bar {\mathbf {z} }}_{2}\otimes \mathbf {z} _{3}),

где $\mathbf {z} _{k}=\mathbf {x} _{k}+i\mathbf {y} _{k}$ .

Напротив, ранг вещественных матриц никогда не уменьшится при расширении поля до $\mathbb {C}$ : вещественный ранг матрицы и комплексный ранг матрицы совпадают для вещественных матриц.

Общий ранг

Общий ранг $r(I_{1},\ldots ,I_{M})$ определяется как наименьший ранг $r$ такая, что замыкание в топологии Зарисского множества тензоров ранга не более $r$ это все пространство $F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}$ . В случае комплексных тензоров тензоры ранга не более $r(I_{1},\ldots ,I_{M})$ образуют плотный набор $S$ : каждый тензор в вышеупомянутом пространстве либо имеет ранг меньше общего ранга, либо является пределом в евклидовой топологии последовательности тензоров из $S$ . В случае вещественных тензоров множество тензоров ранга не более $r(I_{1},\ldots ,I_{M})$ образует лишь открытое множество положительной меры в евклидовой топологии. Могут существовать евклидово открытые множества тензоров ранга строго выше родового ранга. Все ранги, возникающие на открытых множествах в евклидовой топологии, называются типичными рангами . Наименьший типичный ранг называется родовым рангом; это определение применимо как к комплексным, так и к действительным тензорам. Родовой ранг тензорных пространств первоначально изучался в 1983 году Фолькером Штрассеном . ^[9]

В качестве иллюстрации изложенных выше концепций известно, что и 2, и 3 являются типичными рангами $\mathbb {R} ^{2}\otimes \mathbb {R} ^{2}\otimes \mathbb {R} ^{2}$ в то время как общий ранг $\mathbb {C} ^{2}\otimes \mathbb {C} ^{2}\otimes \mathbb {C} ^{2}$ равно 2. Практически это означает, что случайно выбранный действительный тензор (из непрерывной вероятностной меры в пространстве тензоров) размера $2\times 2\times 2$ будет тензором ранга 1 с нулевой вероятностью, тензором ранга 2 с положительной вероятностью и тензором ранга 3 с положительной вероятностью. С другой стороны, случайно выбранный комплексный тензор того же размера будет тензором ранга 1 с вероятностью ноль, тензором ранга 2 с вероятностью единица и тензором ранга 3 с вероятностью нуль. Известно даже, что общий действительный тензор третьего ранга в $\mathbb {R} ^{2}\otimes \mathbb {R} ^{2}\otimes \mathbb {R} ^{2}$ будет иметь комплексный ранг, равный 2.

Общий ранг тензорных пространств зависит от различия между сбалансированными и несбалансированными тензорными пространствами. Тензорное пространство $F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}$ , где $I_{1}\geq I_{2}\geq \cdots \geq I_{M}$ ,называется несбалансированным, если

I_{1}>1+\prod _{m=2}^{M}I_{m}-\sum _{m=2}^{M}(I_{m}-1),

иначе его называют сбалансированным .

Несбалансированные тензорные пространства

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

r(I_{1},\ldots ,I_{M})=\min \left\{I_{1},\prod _{m=2}^{M}I_{m}\right\}

почти везде . Точнее, ранг каждого тензора в несбалансированном тензорном пространстве. $F^{I_{1}\times \cdots \times I_{M}}\setminus Z$ , где $Z$ — некоторое неопределенное замкнутое множество в топологии Зарисского, равное указанному выше значению. ^[10]

Сбалансированные тензорные пространства

Ожидаемый родовой ранг тензоров , живущих в сбалансированном тензорном пространстве, равен

r_{E}(I_{1},\ldots ,I_{M})=\left\lceil {\frac {\Pi }{\Sigma +1}}\right\rceil

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

\Pi =\prod _{m=1}^{M}I_{m}\quad {\text{and}}\quad \Sigma =\sum _{m=1}^{M}(I_{m}-1).

Точнее, ранг каждого тензора в $\mathbb {C} ^{I_{1}\times \cdots \times I_{M}}\setminus Z$ , где $Z$ — некоторое неопределенное замкнутое множество в топологии Зарисского , ожидается, что оно будет равно указанному выше значению. ^[11] Для реальных тензоров $r_{E}(I_{1},\ldots ,I_{M})$ - это наименьший ранг, который ожидается на множестве положительных евклидовых мер. Значение $r_{E}(I_{1},\ldots ,I_{M})$ часто называют ожидаемым общим рангом тензорного пространства $F^{I_{1}\times \cdots \times I_{M}}$ потому что это только предположительно верно. Известно, что истинный родовой ранг всегда удовлетворяет

r(I_{1},\ldots ,I_{M})\geq r_{E}(I_{1},\ldots ,I_{M}).

Гипотеза Або -Оттавиани-Петерсона ^[11] утверждает, что ожидается равенство, т.е. $r(I_{1},\ldots ,I_{M})=r_{E}(I_{1},\ldots ,I_{M})$ , со следующими исключительными случаями:

$F^{(2m+1)\times (2m+1)\times 3}{\text{ with }}m=1,2,\ldots$
$F^{(m+1)\times (m+1)\times 2\times 2}{\text{ with }}m=2,3,\ldots$

Известно, что в каждом из этих исключительных случаев родовой ранг равен $r(I_{1},\ldots ,I_{m},\ldots ,I_{M})=r_{E}(I_{1},\ldots ,I_{M})+1$ . Заметим, что хотя набор тензоров ранга 3 в $F^{2\times 2\times 2\times 2}$ дефектен (13, а не ожидаемое 14), общий ранг в этом пространстве по-прежнему остается ожидаемым, 4. Аналогично, набор тензоров ранга 5 в $F^{4\times 4\times 3}$ является дефектным (44, а не ожидаемое 45), но общий ранг в этом пространстве по-прежнему равен ожидаемому 6.

Гипотеза АОП полностью доказана в ряде частных случаев. Ликтейг еще в 1985 году показал, что $r(n,n,n)=r_{E}(n,n,n)$ , при условии, что $n\neq 3$ . ^[12] В 2011 году крупный прорыв был сделан Каталисано, Джерамитой и Джимильяно, которые доказали, что ожидаемая размерность набора рангов $s$ тензоры формата $2\times 2\times \cdots \times 2$ является ожидаемым, за исключением тензоров ранга 3 в случае с 4 факторами, однако ожидаемый ранг в этом случае по-прежнему равен 4. Как следствие, $r(2,2,\ldots ,2)=r_{E}(2,2,\ldots ,2)$ для всех бинарных тензоров. ^[13]

Максимальный ранг

Максимальный ранг , который может быть допущен любым из тензоров в тензорном пространстве, вообще говоря, неизвестен; отсутствует даже предположение об этом максимальном ранге. В настоящее время лучшая общая верхняя оценка гласит, что максимальный ранг $r_{\mbox{max}}(I_{1},\ldots ,I_{M})$ из $F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}$ , где $I_{1}\geq I_{2}\geq \cdots \geq I_{M}$ , удовлетворяет

r_{\mbox{max}}(I_{1},\ldots ,I_{M})\leq \min \left\{\prod _{m=2}^{M}I_{m},2\cdot r(I_{1},\ldots ,I_{M})\right\},

где $r(I_{1},\ldots ,I_{M})$ это (наименьший) общий ранг $F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}$ . ^[14]Хорошо известно, что указанное неравенство может быть строгим. Например, общий ранг тензоров в $\mathbb {R} ^{2\times 2\times 2}$ равно двум, так что приведенная выше оценка дает $r_{\mbox{max}}(2,2,2)\leq 4$ , при этом известно, что максимальный ранг равен 3. ^[8]

Пограничный ранг

Ранг- $s$ тензор ${\mathcal {A}}$ называется граничным тензором , если существует последовательность тензоров ранга не более $r<s$ чей предел ${\mathcal {A}}$ . Если $r$ является наименьшим значением, для которого существует такая сходящаяся последовательность, то его называют рангом граничным ${\mathcal {A}}$ . Для тензоров второго порядка, т. е. матриц, ранг и граничный ранг всегда совпадают, однако для тензоров порядка $\geq 3$ они могут отличаться. Граничные тензоры были впервые изучены в контексте быстрых приближенных алгоритмов умножения матриц Бини, Лотти и Романи в 1980 году. ^[15]

Классическим примером граничного тензора является тензор третьего ранга.

{\mathcal {A}}=\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \otimes \mathbf {u} \otimes \mathbf {u} ,\quad {\text{with }}\|\mathbf {u} \|=\|\mathbf {v} \|=1{\text{ and }}\langle \mathbf {u} ,\mathbf {v} \rangle \neq 1.

Его можно сколь угодно хорошо аппроксимировать следующей последовательностью тензоров ранга 2:

{\begin{aligned}{\mathcal {A}}_{m}&=m(\mathbf {u} +{\frac {1}{m}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{m}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{m}}\mathbf {v} )-m\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {u} \\&=\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \otimes \mathbf {u} \otimes \mathbf {u} +{\frac {1}{m}}(\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {v} +\mathbf {v} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {v} \otimes \mathbf {v} \otimes \mathbf {u} )+{\frac {1}{m^{2}}}\mathbf {v} \otimes \mathbf {v} \otimes \mathbf {v} \end{aligned}}

как $m\to \infty$ . Следовательно, его пограничный ранг равен 2, что строго меньше его ранга. Когда два вектора ортогональны, этот пример также известен как W. состояние

Характеристики

Идентифицируемость

Из определения чистого тензора следует, что ${\mathcal {A}}=\mathbf {a} _{1}\otimes \mathbf {a} _{2}\otimes \cdots \otimes \mathbf {a} _{M}=\mathbf {b} _{1}\otimes \mathbf {b} _{2}\otimes \cdots \otimes \mathbf {b} _{M}$ тогда и только тогда, когда существуют $\lambda _{k}$ такой, что $\lambda _{1}\lambda _{2}\cdots \lambda _{M}=1$ и $\mathbf {a} _{m}=\lambda _{m}\mathbf {b} _{m}$ для всех м . По этой причине параметры $\{\mathbf {a} _{m}\}_{m=1}^{M}$ тензора ранга 1 ${\mathcal {A}}$ называются идентифицируемыми или существенно уникальными. Ранг- $r$ тензор ${\mathcal {A}}\in F^{I_{1}}\otimes F^{I_{2}}\otimes \cdots \otimes F^{I_{M}}$ называется идентифицируемым , если каждое из его тензорных разложений является суммой одного и того же множества $r$ различные тензоры $\{{\mathcal {A}}_{1},{\mathcal {A}}_{2},\ldots ,{\mathcal {A}}_{r}\}$ где ${\mathcal {A}}_{i}$ имеют ранг 1. Идентифицируемый ранг- $r$ таким образом, имеет только одно существенно уникальное разложение ${\mathcal {A}}=\sum _{i=1}^{r}{\mathcal {A}}_{i},$ и все $r!$ тензорные ранговые разложения ${\mathcal {A}}$ можно получить перестановкой порядка слагаемых. Заметим, что при разложении тензорного ранга все ${\mathcal {A}}_{i}$ различны, иначе ранг ${\mathcal {A}}$ было бы максимум $r-1$ .

Общая идентифицируемость

Тензоры порядка 2 в $F^{I_{1}}\otimes F^{I_{2}}\simeq F^{I_{1}\times I_{2}}$ , т. е. матрицы, не идентифицируемы для $r>1$ . По существу это следует из наблюдения ${\mathcal {A}}=\sum _{i=1}^{r}\mathbf {a} _{i}\otimes \mathbf {b} _{i}=\sum _{i=1}^{r}\mathbf {a} _{i}\mathbf {b} _{i}^{T}=AB^{T}=(AX^{-1})(BX^{T})^{T}=\sum _{i=1}^{r}\mathbf {c} _{i}\mathbf {d} _{i}^{T}=\sum _{i=1}^{r}\mathbf {c} _{i}\otimes \mathbf {d} _{i},$ где $X\in \mathrm {GL} _{r}(F)$ является обратимым $r\times r$ матрица, $A=[\mathbf {a} _{i}]_{i=1}^{r}$ , $B=[\mathbf {b} _{i}]_{i=1}^{r}$ , $AX^{-1}=[\mathbf {c} _{i}]_{i=1}^{r}$ и $BX^{T}=[\mathbf {d} _{i}]_{i=1}^{r}$ . Это можно показать ^[16] это для каждого $X\in \mathrm {GL} _{n}(F)\setminus Z$ , где $Z$ является замкнутым множеством в топологии Зариского, разложение в правой части представляет собой сумму другого набора тензоров ранга 1, чем разложение в левой части, что влечет за собой, что тензоры второго порядка ранга $r>1$ в целом не идентифицируются.

Ситуация полностью меняется для тензоров высших порядков в $F^{I_{1}}\otimes F^{I_{2}}\otimes \cdots \otimes F^{I_{M}}$ с $M>2$ и все $I_{m}\geq 2$ . Для простоты обозначений без ограничения общности предположим, что множители упорядочены так, что $I_{1}\geq I_{2}\geq \cdots \geq I_{M}\geq 2$ . Позволять $S_{r}\subset F^{I_{1}}\otimes \cdots F^{I_{m}}\otimes \cdots \otimes F^{I_{M}}$ обозначим множество тензоров ранга, ограниченного $r$ . была доказана правильность следующего утверждения Затем с помощью компьютерного доказательства для всех пространств размерности $\Pi <15000$ , ^[17] и предполагается, что оно справедливо в целом: ^[17]^[18]^[19]

Существует закрытое множество $Z_{r}$ в топологии Зарисского такая, что каждый тензор ${\mathcal {A}}\in S_{r}\setminus Z_{r}$ можно опознать ( $S_{r}$ в этом случае называется обобщенно идентифицируемым ), если только не имеет место один из следующих исключительных случаев:

Ранг слишком велик: $r>r_{E}(I_{1},I_{2},\ldots ,I_{M})$ ;
Пространство является идентифицируемо неуравновешенным, т. е. ${\textstyle I_{1}>\prod _{m=2}^{M}i_{m}-\sum _{m=2}^{M}(I_{m}-1)}$ , и ранг слишком велик: ${\textstyle r\geq \prod _{m=2}^{M}I_{m}-\sum _{m=2}^{M}(I_{m}-1)}$ ;
Пространство – это дефектный корпус $F^{4}\otimes F^{4}\otimes F^{3}$ и звание такое $r=5$ ;
Пространство – это дефектный корпус $F^{n}\otimes F^{n}\otimes F^{2}\otimes F^{2}$ , где $n\geq 2$ , и ранг $r=2n-1$ ;
Пространство $F^{4}\otimes F^{4}\otimes F^{4}$ и звание такое $r=6$ ;
Пространство $F^{6}\otimes F^{6}\otimes F^{3}$ и звание такое $r=8$ ; или
Пространство $F^{2}\otimes F^{2}\otimes F^{2}\otimes F^{2}\otimes F^{2}$ и звание такое $r=5$ .
Пространство идеально, т.е. ${\textstyle r_{E}(I_{1},I_{2},\ldots ,I_{M})={\frac {\Pi }{\Sigma +1}}}$ является целым числом, а ранг равен ${\textstyle r=r_{E}(I_{1},I_{2},\ldots ,I_{M})}$ .

В этих исключительных случаях общее (и минимальное) число комплексных разложений равно

оказался $\infty$ в первых 4 случаях;
в случае 5 оказалось два; ^[20]
ожидал ^[21] быть шестью в случае 6;
в случае 7 оказалось два; ^[22] и
ожидал ^[21] быть не менее двух в случае 8, за исключением двух идентифицируемых случаев $F^{5}\otimes F^{4}\otimes F^{3}$ и $F^{3}\otimes F^{2}\otimes F^{2}\otimes F^{2}$ .

Таким образом, общий тензор порядка $M>2$ и ранг ${\textstyle r<{\frac {\Pi }{\Sigma +1}}}$ то, что не является несбалансированным по идентифицируемости, ожидается, что оно будет идентифицируемым (по модулю исключительных случаев в небольших пространствах).

Некорректность стандартной задачи аппроксимации

Задача аппроксимации ранга требует ранг- $r$ разложение, наиболее близкое (в обычной евклидовой топологии) к некоторому рангу. $s$ тензор ${\mathcal {A}}$ , где $r<s$ . То есть человек пытается решить

\min _{\mathbf {a} _{i}^{m}\in F^{I_{m}}}\|{\mathcal {A}}-\sum _{i=1}^{r}\mathbf {a} _{i}^{1}\otimes \mathbf {a} _{i}^{2}\otimes \cdots \otimes \mathbf {a} _{i}^{M}\|_{F},

где $\|\cdot \|_{F}$ является нормой Фробениуса .

Это было показано в статье де Сильвы и Лима в 2008 году. ^[8] что описанная выше стандартная задача аппроксимации может быть некорректной . Решение вышеупомянутой проблемы иногда может не существовать, поскольку множество, по которому выполняется оптимизация, не замкнуто. Таким образом, минимизатора может не существовать, даже если нижняя граница существует. В частности, известно, что некоторые так называемые граничные тензоры могут быть сколь угодно хорошо аппроксимированы последовательностью тензоров ранга не более $r$ , даже несмотря на то, что предел последовательности сходится к тензору ранга строго выше $r$ . Тензор ранга 3

{\mathcal {A}}=\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \otimes \mathbf {u} \otimes \mathbf {u} ,\quad {\text{with }}\|\mathbf {u} \|=\|\mathbf {v} \|=1{\text{ and }}\langle \mathbf {u} ,\mathbf {v} \rangle \neq 1

может быть сколь угодно хорошо аппроксимирован следующей последовательностью тензоров ранга 2

{\mathcal {A}}_{n}=n(\mathbf {u} +{\frac {1}{n}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{n}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{n}}\mathbf {v} )-n\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {u}

как $n\to \infty$ . Этот пример прекрасно иллюстрирует общий принцип, согласно которому последовательность рангов $r$ тензоры, которые сходятся к тензору строго более высокого ранга, должны допускать по крайней мере два отдельных члена ранга 1, нормы которых становятся неограниченными. Формально говоря, всякий раз, когда последовательность

{\mathcal {A}}_{n}=\sum _{i=1}^{r}\mathbf {a} _{i,n}^{1}\otimes \mathbf {a} _{i,n}^{2}\otimes \cdots \otimes \mathbf {a} _{i,n}^{M}

имеет свойство, которое ${\mathcal {A}}_{n}\to {\mathcal {A}}$ (в евклидовой топологии) как $n\to \infty$ , то должно существовать по крайней мере $1\leq i\neq j\leq r$ такой, что

\|\mathbf {a} _{i,n}^{1}\otimes \mathbf {a} _{i,n}^{2}\otimes \cdots \otimes \mathbf {a} _{i,n}^{M}\|_{F}\to \infty {\text{  and  }}\|\mathbf {a} _{j,n}^{1}\otimes \mathbf {a} _{j,n}^{2}\otimes \cdots \otimes \mathbf {a} _{j,n}^{M}\|_{F}\to \infty

как $n\to \infty$ . Это явление часто встречается при попытке аппроксимировать тензор с помощью алгоритмов численной оптимизации. Иногда ее называют проблемой расходящихся компонентов . Кроме того, было показано, что случайный тензор низкого ранга над действительными числами может не допускать аппроксимации ранга 2 с положительной вероятностью, что привело к пониманию того, что проблема некорректности является важным фактором при использовании разложения ранга тензора.

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

Расчет цены за день

Альтернативные алгоритмы:

Прямые алгоритмы:

карандашные алгоритмы ^[23]^[24]^[25]^[26]^[27]^[28]^[29]
моментные алгоритмы ^[30]

Общие алгоритмы оптимизации:

Общие алгоритмы решения полиномиальной системы:

гомотопическое продолжение ^[31]

Приложения

В машинном обучении CP-декомпозиция является центральным компонентом обучения вероятностных моделей скрытых переменных с помощью метода сопоставления моментов. Например, рассмотрим модель с несколькими представлениями ^[32] которая представляет собой вероятностную модель скрытых переменных. В этой модели генерация выборок постулируется следующим образом: существует скрытая случайная величина, которая не наблюдается напрямую, учитывая, что существует несколько условно независимых случайных величин, известных как разные «виды» скрытой переменной. Например, предположим, что имеется три представления. $x_{1},x_{2},x_{3}$ из $k$ -состояние категориальной скрытой переменной $h$ . Тогда эмпирический третий момент этой модели скрытой переменной $E[x_{1}\otimes x_{2}\otimes x_{3}]$ является тензором ранга 3 и может быть разложен как: $E[x_{1}\otimes x_{2}\otimes x_{3}]=\sum _{i=1}^{k}Pr(h=i)E[x_{1}|h=i]\otimes E[x_{2}|h=i]\otimes E[x_{3}|h=i]$ .

В таких приложениях, как тематическое моделирование , это можно интерпретировать как совместное появление слов в документе. Тогда коэффициенты разложения этого тензора эмпирического момента можно интерпретировать как вероятность выбора конкретной темы и каждого столбца факторной матрицы. $E[x|h=i]$ соответствует вероятностям слов в словаре соответствующей темы.

См. также

Ссылки

^ Папалексакис, Евангелос. «Автоматический тензорный майнинг без присмотра с оценкой качества» (PDF) .
^ Ф. Л. Хичкок (1927). «Выражение тензора или полиады как сумма произведений». Журнал математики и физики . 6 (1–4): 164–189. дои : 10.1002/sapm192761164 .
^ Перейти обратно: ^а ^б Кэрролл, доктор медицинских наук ; Чанг, Дж. (1970). «Анализ индивидуальных различий в многомерном масштабировании посредством n -стороннего обобщения разложения Эккарта – Янга». Психометрика . 35 (3): 283–319. дои : 10.1007/BF02310791 . S2CID 50364581 .
^ Перейти обратно: ^а ^б Харшман, Ричард А. (1970). «Основы процедуры PARAFAC: модели и условия для «объяснительного» мультимодального факторного анализа» (PDF) . Рабочие документы Калифорнийского университета в Лос-Анджелесе по фонетике . 16:84 . № 10085. Архивировано из оригинала (PDF) 10 октября 2004 г.
^ Гуджрал, Экта. «Aptera: автоматический тензорный анализ PARAFAC2» (PDF) . АСОНАМ 2022.
^ Хиллар, CJ ; Лим, Л. (2013). «Большинство тензорных задач NP-Hard». Журнал АКМ . 60 (6): 1–39. arXiv : 0911.1393 . дои : 10.1145/2512329 . S2CID 1460452 .
^ Ландсберг, Дж. М. (2012). Тензоры: геометрия и приложения . АМС.
^ Перейти обратно: ^а ^б ^с де Сильва, В .; Лим, Л. (2008). «Тензорный ранг и некорректность задачи наилучшего низкорангового приближения». Журнал SIAM по матричному анализу и его приложениям . 30 (3): 1084–1127. arXiv : math/0607647 . дои : 10.1137/06066518x . S2CID 7159193 .
^ Штрассен, В. (1983). «Ранг и оптимальное вычисление универсальных тензоров» . Линейная алгебра и ее приложения . 52/53: 645–685. дои : 10.1016/0024-3795(83)80041-x .
^ Катализано, М.В. ; Герамита, А.В. ; Джимильяно, А. (2002). «Ранги тензоров, секущие многообразия Сегре и жирные точки» . Линейная алгебра и ее приложения . 355 (1–3): 263–285. дои : 10.1016/s0024-3795(02)00352-x .
^ Перейти обратно: ^а ^б Або, Х. ; Оттавиани, Г .; Петерсон, К. (2009). «Индукция секущих разновидностей сортов Сегре». Труды Американского математического общества . 361 (2): 767–792. arXiv : math/0607191 . дои : 10.1090/s0002-9947-08-04725-9 . S2CID 59069541 .
^ Ликтейг, Томас (1985). «Типичный тензорный ранг» . Линейная алгебра и ее приложения . 69 : 95–120. дои : 10.1016/0024-3795(85)90070-9 .
^ Катализано, М.В. ; Герамита, А.В. ; Джимильяно, А. (2011). «Секущие разновидности $\mathbb {P}$ ¹ × ··· × $\mathbb {P}$ ¹ ( n - раз) не являются дефектными для n ≥ 5" . Журнал алгебраической геометрии . 20 (2): 295–327. doi : 10.1090/s1056-3911-10-00537-0 .
^ Блекерман, Г .; Тейтлер, З. (2015). «О максимальных, типовых и родовых званиях». Математические Аннален . 362 (3–4): 1–11. arXiv : 1402.2371 . дои : 10.1007/s00208-014-1150-3 . S2CID 14309435 .
^ Бини, Д. ; Лотти, Дж .; Романи, Ф. (1980). «Приближенные решения вычислительной задачи билинейной формы». SIAM Журнал по научным вычислениям . 9 (4): 692–697. дои : 10.1137/0209053 .
^ Харрис, Джо (1992). геометрия Алгебраическая Тексты для аспирантов по математике. Том. 133. дои : 10.1007/978-1-4757-2189-8 . ISBN 978-1-4419-3099-6 .
^ Перейти обратно: ^а ^б Кьянтини, Л.; Оттавиани, Г.; Ванниеувенховен, Н. (1 января 2014 г.). «Алгоритм общей и специфической идентифицируемости низкого ранга комплексных тензоров». Журнал SIAM по матричному анализу и его приложениям . 35 (4): 1265–1287. arXiv : 1403.4157 . дои : 10.1137/140961389 . ISSN 0895-4798 . S2CID 28478606 .
^ Боччи, Криштиану; Кьянтини, Лука; Оттавиани, Джорджио (01 декабря 2014 г.). «Уточненные методы идентифицируемости тензоров». Анналы чистой и прикладной математики . 193 (6): 1691–1702. arXiv : 1303.6915 . дои : 10.1007/s10231-013-0352-8 . ISSN 0373-3114 . S2CID 119721371 .
^ Кьянтини, Л.; Оттавиани, Г.; Ванниевенховен, Н. (01 января 2017 г.). «Эффективные критерии специфической идентифицируемости тензоров и форм». Журнал SIAM по матричному анализу и его приложениям . 38 (2): 656–681. arXiv : 1609.00123 . дои : 10.1137/16m1090132 . ISSN 0895-4798 . S2CID 23983015 .
^ Кьянтини, Л.; Оттавиани, Г. (1 января 2012 г.). «О общей идентифицируемости 3-тензоров малого ранга». Журнал SIAM по матричному анализу и его приложениям . 33 (3): 1018–1037. arXiv : 1103.2696 . дои : 10.1137/110829180 . ISSN 0895-4798 . S2CID 43781880 .
^ Перейти обратно: ^а ^б Хауэнштайн, доктор юридических наук; Одинг, Л.; Оттавиани, Г.; Соммесе, AJ (2016). «Гомотопические методы тензорного разложения и идеальной идентифицируемости». Дж. Рейн Анжью. Математика . 2019 (753): 1–22. arXiv : 1501.00090 . doi : 10.1515/crelle-2016-0067 . S2CID 16324593 .
^ Боччи, Криштиану; Кьянтини, Лука (2013). «Об идентифицируемости бинарных произведений Сегре» . Журнал алгебраической геометрии . 22 (1): 1–11. arXiv : 1105.3643 . дои : 10.1090/s1056-3911-2011-00592-4 . ISSN 1056-3911 . S2CID 119671913 .
^ Доманов, Игнат; Латаувер, Ливен Де (январь 2014 г.). «Каноническое полиадическое разложение тензоров третьего порядка: сведение к обобщенному разложению по собственным значениям». Журнал SIAM по матричному анализу и его приложениям . 35 (2): 636–660. arXiv : 1312.2848 . дои : 10.1137/130916084 . ISSN 0895-4798 . S2CID 14851072 .
^ Доманов, Игнат; Де Латаувер, Ливен (январь 2017 г.). «Каноническое полиадическое разложение тензоров третьего порядка: смягченные условия единственности и алгебраический алгоритм». Линейная алгебра и ее приложения . 513 : 342–375. arXiv : 1501.07251 . дои : 10.1016/j.laa.2016.10.019 . ISSN 0024-3795 . S2CID 119729978 .
^ Фабер, Николаас (Клаас) М.; Ферре, Джоан; Боке, Рикар (январь 2001 г.). «Итеративно перевзвешенный метод аннигиляции обобщенного ранга». Хемометрика и интеллектуальные лабораторные системы . 55 (1–2): 67–90. дои : 10.1016/s0169-7439(00)00117-9 . ISSN 0169-7439 .
^ Леурганс, SE ; Росс, RT; Абель, РБ (октябрь 1993 г.). «Разложение трехсторонних массивов». Журнал SIAM по матричному анализу и его приложениям . 14 (4): 1064–1083. дои : 10.1137/0614071 . ISSN 0895-4798 .
^ Лорбер, Авраам. (октябрь 1985 г.). «Особенности количественного определения химического состава по двумерному массиву данных методом факторного анализа рангов». Аналитическая химия . 57 (12): 2395–2397. дои : 10.1021/ac00289a052 . ISSN 0003-2700 .
^ Санчес, Эухенио; Ковальски, Брюс Р. (январь 1990 г.). «Тензорное разрешение: прямое трилинейное разложение». Журнал хемометрики . 4 (1): 29–45. дои : 10.1002/cem.1180040105 . ISSN 0886-9383 . S2CID 120459386 .
^ Сэндс, Ричард; Янг, Форрест В. (март 1980 г.). «Модели компонентов для трехсторонних данных: алгоритм попеременных наименьших квадратов с оптимальными функциями масштабирования». Психометрика . 45 (1): 39–67. дои : 10.1007/bf02293598 . ISSN 0033-3123 . S2CID 121003817 .
^ Бернарди, А.; Брачат, Дж.; Комон, П.; Моррен, Б. (май 2013 г.). «Общее тензорное разложение, матрицы моментов и приложения». Журнал символических вычислений . 52 : 51–71. arXiv : 1105.1229 . дои : 10.1016/j.jsc.2012.05.012 . ISSN 0747-7171 . S2CID 14181289 .
^ Бернарди, Алессандра; Далео, Ной С.; Хауэнштайн, Джонатан Д.; Муррен, Бернар (декабрь 2017 г.). «Тензорное разложение и гомотопическое продолжение». Дифференциальная геометрия и ее приложения . 55 : 78–105. arXiv : 1512.04312 . дои : 10.1016/j.difgeo.2017.07.009 . ISSN 0926-2245 . S2CID 119147635 .
^ Анандкумар, Анимашри; Ге, Ронг; Сюй, Дэниел; Какаде, Шам М; Тельгарский, Матус (2014). «Тензорные разложения для изучения моделей со скрытыми переменными». Журнал исследований машинного обучения . 15 (1): 2773–2832.

Дальнейшее чтение

Колда Тамара Георгиевна ; Бадер, Бретт В. (2009). «Тензорные разложения и приложения». СИАМ преп . 51 (3): 455–500. Бибкод : 2009SIAMR..51..455K . CiteSeerX 10.1.1.153.2059 . дои : 10.1137/07070111X . S2CID 16074195 .
Ландсберг, Джозеф М. (2012). Тензоры: геометрия и приложения . АМС.

Внешние ссылки

Учебное пособие по ПАРАФАК
Параллельный факторный анализ (PARAFAC)
FactoMineR (бесплатное программное обеспечение для исследовательского многомерного анализа данных, связанное с R )

[1] Папалексакис, Евангелос. «Автоматический тензорный майнинг без присмотра с оценкой качества» (PDF) .

[2] Ф. Л. Хичкок (1927). «Выражение тензора или полиады как сумма произведений». Журнал математики и физики . 6 (1–4): 164–189. дои : 10.1002/sapm192761164 .

[cc1970-3] Перейти обратно: ^а ^б Кэрролл, доктор медицинских наук ; Чанг, Дж. (1970). «Анализ индивидуальных различий в многомерном масштабировании посредством n -стороннего обобщения разложения Эккарта – Янга». Психометрика . 35 (3): 283–319. дои : 10.1007/BF02310791 . S2CID 50364581 .

[h1970-4] Перейти обратно: ^а ^б Харшман, Ричард А. (1970). «Основы процедуры PARAFAC: модели и условия для «объяснительного» мультимодального факторного анализа» (PDF) . Рабочие документы Калифорнийского университета в Лос-Анджелесе по фонетике . 16:84 . № 10085. Архивировано из оригинала (PDF) 10 октября 2004 г.

[5] Гуджрал, Экта. «Aptera: автоматический тензорный анализ PARAFAC2» (PDF) . АСОНАМ 2022.

[6] Хиллар, CJ ; Лим, Л. (2013). «Большинство тензорных задач NP-Hard». Журнал АКМ . 60 (6): 1–39. arXiv : 0911.1393 . дои : 10.1145/2512329 . S2CID 1460452 .

[7] Ландсберг, Дж. М. (2012). Тензоры: геометрия и приложения . АМС.

[dSL2008-8] Перейти обратно: ^а ^б ^с де Сильва, В .; Лим, Л. (2008). «Тензорный ранг и некорректность задачи наилучшего низкорангового приближения». Журнал SIAM по матричному анализу и его приложениям . 30 (3): 1084–1127. arXiv : math/0607647 . дои : 10.1137/06066518x . S2CID 7159193 .

[9] Штрассен, В. (1983). «Ранг и оптимальное вычисление универсальных тензоров» . Линейная алгебра и ее приложения . 52/53: 645–685. дои : 10.1016/0024-3795(83)80041-x .

[10] Катализано, М.В. ; Герамита, А.В. ; Джимильяно, А. (2002). «Ранги тензоров, секущие многообразия Сегре и жирные точки» . Линейная алгебра и ее приложения . 355 (1–3): 263–285. дои : 10.1016/s0024-3795(02)00352-x .

[aop2009-11] Перейти обратно: ^а ^б Або, Х. ; Оттавиани, Г .; Петерсон, К. (2009). «Индукция секущих разновидностей сортов Сегре». Труды Американского математического общества . 361 (2): 767–792. arXiv : math/0607191 . дои : 10.1090/s0002-9947-08-04725-9 . S2CID 59069541 .

[12] Ликтейг, Томас (1985). «Типичный тензорный ранг» . Линейная алгебра и ее приложения . 69 : 95–120. дои : 10.1016/0024-3795(85)90070-9 .

[13] Катализано, М.В. ; Герамита, А.В. ; Джимильяно, А. (2011). «Секущие разновидности $\mathbb {P}$ ¹ × ··· × $\mathbb {P}$ ¹ ( n - раз) не являются дефектными для n ≥ 5" . Журнал алгебраической геометрии . 20 (2): 295–327. doi : 10.1090/s1056-3911-10-00537-0 .

[14] Блекерман, Г .; Тейтлер, З. (2015). «О максимальных, типовых и родовых званиях». Математические Аннален . 362 (3–4): 1–11. arXiv : 1402.2371 . дои : 10.1007/s00208-014-1150-3 . S2CID 14309435 .

[15] Бини, Д. ; Лотти, Дж .; Романи, Ф. (1980). «Приближенные решения вычислительной задачи билинейной формы». SIAM Журнал по научным вычислениям . 9 (4): 692–697. дои : 10.1137/0209053 .

[16] Харрис, Джо (1992). геометрия Алгебраическая Тексты для аспирантов по математике. Том. 133. дои : 10.1007/978-1-4757-2189-8 . ISBN 978-1-4419-3099-6 .

[:6-17] Перейти обратно: ^а ^б Кьянтини, Л.; Оттавиани, Г.; Ванниеувенховен, Н. (1 января 2014 г.). «Алгоритм общей и специфической идентифицируемости низкого ранга комплексных тензоров». Журнал SIAM по матричному анализу и его приложениям . 35 (4): 1265–1287. arXiv : 1403.4157 . дои : 10.1137/140961389 . ISSN 0895-4798 . S2CID 28478606 .

[18] Боччи, Криштиану; Кьянтини, Лука; Оттавиани, Джорджио (01 декабря 2014 г.). «Уточненные методы идентифицируемости тензоров». Анналы чистой и прикладной математики . 193 (6): 1691–1702. arXiv : 1303.6915 . дои : 10.1007/s10231-013-0352-8 . ISSN 0373-3114 . S2CID 119721371 .

[19] Кьянтини, Л.; Оттавиани, Г.; Ванниевенховен, Н. (01 января 2017 г.). «Эффективные критерии специфической идентифицируемости тензоров и форм». Журнал SIAM по матричному анализу и его приложениям . 38 (2): 656–681. arXiv : 1609.00123 . дои : 10.1137/16m1090132 . ISSN 0895-4798 . S2CID 23983015 .

[20] Кьянтини, Л.; Оттавиани, Г. (1 января 2012 г.). «О общей идентифицируемости 3-тензоров малого ранга». Журнал SIAM по матричному анализу и его приложениям . 33 (3): 1018–1037. arXiv : 1103.2696 . дои : 10.1137/110829180 . ISSN 0895-4798 . S2CID 43781880 .

[:7-21] Перейти обратно: ^а ^б Хауэнштайн, доктор юридических наук; Одинг, Л.; Оттавиани, Г.; Соммесе, AJ (2016). «Гомотопические методы тензорного разложения и идеальной идентифицируемости». Дж. Рейн Анжью. Математика . 2019 (753): 1–22. arXiv : 1501.00090 . doi : 10.1515/crelle-2016-0067 . S2CID 16324593 .

[22] Боччи, Криштиану; Кьянтини, Лука (2013). «Об идентифицируемости бинарных произведений Сегре» . Журнал алгебраической геометрии . 22 (1): 1–11. arXiv : 1105.3643 . дои : 10.1090/s1056-3911-2011-00592-4 . ISSN 1056-3911 . S2CID 119671913 .

[23] Доманов, Игнат; Латаувер, Ливен Де (январь 2014 г.). «Каноническое полиадическое разложение тензоров третьего порядка: сведение к обобщенному разложению по собственным значениям». Журнал SIAM по матричному анализу и его приложениям . 35 (2): 636–660. arXiv : 1312.2848 . дои : 10.1137/130916084 . ISSN 0895-4798 . S2CID 14851072 .

[24] Доманов, Игнат; Де Латаувер, Ливен (январь 2017 г.). «Каноническое полиадическое разложение тензоров третьего порядка: смягченные условия единственности и алгебраический алгоритм». Линейная алгебра и ее приложения . 513 : 342–375. arXiv : 1501.07251 . дои : 10.1016/j.laa.2016.10.019 . ISSN 0024-3795 . S2CID 119729978 .

[25] Фабер, Николаас (Клаас) М.; Ферре, Джоан; Боке, Рикар (январь 2001 г.). «Итеративно перевзвешенный метод аннигиляции обобщенного ранга». Хемометрика и интеллектуальные лабораторные системы . 55 (1–2): 67–90. дои : 10.1016/s0169-7439(00)00117-9 . ISSN 0169-7439 .

[26] Леурганс, SE ; Росс, RT; Абель, РБ (октябрь 1993 г.). «Разложение трехсторонних массивов». Журнал SIAM по матричному анализу и его приложениям . 14 (4): 1064–1083. дои : 10.1137/0614071 . ISSN 0895-4798 .

[27] Лорбер, Авраам. (октябрь 1985 г.). «Особенности количественного определения химического состава по двумерному массиву данных методом факторного анализа рангов». Аналитическая химия . 57 (12): 2395–2397. дои : 10.1021/ac00289a052 . ISSN 0003-2700 .

[28] Санчес, Эухенио; Ковальски, Брюс Р. (январь 1990 г.). «Тензорное разрешение: прямое трилинейное разложение». Журнал хемометрики . 4 (1): 29–45. дои : 10.1002/cem.1180040105 . ISSN 0886-9383 . S2CID 120459386 .

[29] Сэндс, Ричард; Янг, Форрест В. (март 1980 г.). «Модели компонентов для трехсторонних данных: алгоритм попеременных наименьших квадратов с оптимальными функциями масштабирования». Психометрика . 45 (1): 39–67. дои : 10.1007/bf02293598 . ISSN 0033-3123 . S2CID 121003817 .

[30] Бернарди, А.; Брачат, Дж.; Комон, П.; Моррен, Б. (май 2013 г.). «Общее тензорное разложение, матрицы моментов и приложения». Журнал символических вычислений . 52 : 51–71. arXiv : 1105.1229 . дои : 10.1016/j.jsc.2012.05.012 . ISSN 0747-7171 . S2CID 14181289 .

[31] Бернарди, Алессандра; Далео, Ной С.; Хауэнштайн, Джонатан Д.; Муррен, Бернар (декабрь 2017 г.). «Тензорное разложение и гомотопическое продолжение». Дифференциальная геометрия и ее приложения . 55 : 78–105. arXiv : 1512.04312 . дои : 10.1016/j.difgeo.2017.07.009 . ISSN 0926-2245 . S2CID 119147635 .

[anandkumar2014tensor-32] Анандкумар, Анимашри; Ге, Ронг; Сюй, Дэниел; Какаде, Шам М; Тельгарский, Матус (2014). «Тензорные разложения для изучения моделей со скрытыми переменными». Журнал исследований машинного обучения . 15 (1): 2773–2832.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]