Разложение ранга тензора
Разложение в полилинейной алгебре

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

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

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

Обозначение

Скалярная переменная обозначается строчными курсивными буквами, а скаляр верхней границы обозначается заглавной курсивной буквой . а {\displaystyle а} А {\displaystyle А}

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

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

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

Определение

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

А = ∑ г = 1 Р λ г а 0 , г ⊗ а 1 , г ⊗ а 2 , г ⋯ ⊗ а с , г ⊗ ⋯ ⊗ а С , г , {\displaystyle {\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},}

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

Ранг тензора

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

Ранг тензора нулей по соглашению равен нулю. Ранг тензора равен единице, при условии, что . a 1 ⊗ ⋯ ⊗ a M {\displaystyle \mathbf {a} _{1}\otimes \cdots \otimes \mathbf {a} _{M}} a m ∈ F I m ∖ { 0 } {\displaystyle \mathbf {a} _{m}\in F^{I_{m}}\setminus \{0\}}

Зависимость поля

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

A = x 1 ⊗ x 2 ⊗ x 3 + x 1 ⊗ y 2 ⊗ y 3 − y 1 ⊗ x 2 ⊗ y 3 + y 1 ⊗ y 2 ⊗ x 3 , {\displaystyle {\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},}

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

A = 1 2 ( z ¯ 1 ⊗ z 2 ⊗ z ¯ 3 + z 1 ⊗ z ¯ 2 ⊗ z 3 ) , {\displaystyle {\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}),}

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

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

Общий ранг

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

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

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

I 1 > 1 + ∏ m = 2 M I m − ∑ m = 2 M ( I m − 1 ) , {\displaystyle I_{1}>1+\prod _{m=2}^{M}I_{m}-\sum _{m=2}^{M}(I_{m}-1),}

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

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

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

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

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

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

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

r E ( I 1 , … , I M ) = ⌈ Π Σ + 1 ⌉ {\displaystyle r_{E}(I_{1},\ldots ,I_{M})=\left\lceil {\frac {\Pi }{\Sigma +1}}\right\rceil }

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

Π = ∏ m = 1 M I m and Σ = ∑ m = 1 M ( I m − 1 ) . {\displaystyle \Pi =\prod _{m=1}^{M}I_{m}\quad {\text{and}}\quad \Sigma =\sum _{m=1}^{M}(I_{m}-1).}

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

r ( I 1 , … , I M ) ≥ r E ( I 1 , … , I M ) . {\displaystyle r(I_{1},\ldots ,I_{M})\geq r_{E}(I_{1},\ldots ,I_{M}).}

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

  • F ( 2 m + 1 ) × ( 2 m + 1 ) × 3  with  m = 1 , 2 , … {\displaystyle F^{(2m+1)\times (2m+1)\times 3}{\text{ with }}m=1,2,\ldots }
  • F ( m + 1 ) × ( m + 1 ) × 2 × 2  with  m = 2 , 3 , … {\displaystyle F^{(m+1)\times (m+1)\times 2\times 2}{\text{ with }}m=2,3,\ldots }

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

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

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

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

r max ( I 1 , … , I M ) ≤ min { ∏ m = 2 M I m , 2 ⋅ r ( I 1 , … , I M ) } , {\displaystyle 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\},}

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

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

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

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

A = u ⊗ u ⊗ v + u ⊗ v ⊗ u + v ⊗ u ⊗ u , with  ‖ u ‖ = ‖ v ‖ = 1  and  ⟨ u , v ⟩ ≠ 1. {\displaystyle {\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:

A m = m ( u + 1 m v ) ⊗ ( u + 1 m v ) ⊗ ( u + 1 m v ) − m u ⊗ u ⊗ u = u ⊗ u ⊗ v + u ⊗ v ⊗ u + v ⊗ u ⊗ u + 1 m ( u ⊗ v ⊗ v + v ⊗ u ⊗ v + v ⊗ v ⊗ u ) + 1 m 2 v ⊗ v ⊗ v {\displaystyle {\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}}}

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

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

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

Из определения чистого тензора следует, что тогда и только тогда, когда существуют такие, что и для всех m . По этой причине параметры тензора ранга 1 называются идентифицируемыми или существенно уникальными. Тензор ранга 1 называется идентифицируемым, если каждое из его разложений тензорного ранга является суммой одного и того же набора различных тензоров , где ' имеют ранг 1. Таким образом, идентифицируемый rank- имеет только одно существенно уникальное разложение , и все разложения тензорного ранга могут быть получены перестановкой порядка слагаемых. Заметим, что в разложении тензорного ранга все ' различны, иначе ранг был бы не более . A = a 1 ⊗ a 2 ⊗ ⋯ ⊗ a M = b 1 ⊗ b 2 ⊗ ⋯ ⊗ b M {\displaystyle {\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}} λ k {\displaystyle \lambda _{k}} λ 1 λ 2 ⋯ λ M = 1 {\displaystyle \lambda _{1}\lambda _{2}\cdots \lambda _{M}=1} a m = λ m b m {\displaystyle \mathbf {a} _{m}=\lambda _{m}\mathbf {b} _{m}} { a m } m = 1 M {\displaystyle \{\mathbf {a} _{m}\}_{m=1}^{M}} A {\displaystyle {\mathcal {A}}} r {\displaystyle r} A ∈ F I 1 ⊗ F I 2 ⊗ ⋯ ⊗ F I M {\displaystyle {\mathcal {A}}\in F^{I_{1}}\otimes F^{I_{2}}\otimes \cdots \otimes F^{I_{M}}} r {\displaystyle r} { A 1 , A 2 , … , A r } {\displaystyle \{{\mathcal {A}}_{1},{\mathcal {A}}_{2},\ldots ,{\mathcal {A}}_{r}\}} A i {\displaystyle {\mathcal {A}}_{i}} r {\displaystyle r} A = ∑ i = 1 r A i , {\displaystyle {\mathcal {A}}=\sum _{i=1}^{r}{\mathcal {A}}_{i},} r ! {\displaystyle r!} A {\displaystyle {\mathcal {A}}} A i {\displaystyle {\mathcal {A}}_{i}} A {\displaystyle {\mathcal {A}}} r − 1 {\displaystyle r-1}

Общая идентификация

Тензоры 2-го порядка в , т.е. матрицы, не идентифицируемы для . Это по существу следует из наблюдения, где — обратимая матрица, , и . Можно показать [16] , что для любого , где — замкнутое множество в топологии Зарисского, разложение в правой части является суммой другого набора тензоров ранга 1, чем разложение в левой части, что влечет за собой то, что тензоры ранга 2 в общем случае не идентифицируемы. F I 1 ⊗ F I 2 ≃ F I 1 × I 2 {\displaystyle F^{I_{1}}\otimes F^{I_{2}}\simeq F^{I_{1}\times I_{2}}} r > 1 {\displaystyle r>1} A = ∑ i = 1 r a i ⊗ b i = ∑ i = 1 r a i b i T = A B T = ( A X − 1 ) ( B X T ) T = ∑ i = 1 r c i d i T = ∑ i = 1 r c i ⊗ d i , {\displaystyle {\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 ∈ G L r ( F ) {\displaystyle X\in \mathrm {GL} _{r}(F)} r × r {\displaystyle r\times r} A = [ a i ] i = 1 r {\displaystyle A=[\mathbf {a} _{i}]_{i=1}^{r}} B = [ b i ] i = 1 r {\displaystyle B=[\mathbf {b} _{i}]_{i=1}^{r}} A X − 1 = [ c i ] i = 1 r {\displaystyle AX^{-1}=[\mathbf {c} _{i}]_{i=1}^{r}} B X T = [ d i ] i = 1 r {\displaystyle BX^{T}=[\mathbf {d} _{i}]_{i=1}^{r}} X ∈ G L n ( F ) ∖ Z {\displaystyle X\in \mathrm {GL} _{n}(F)\setminus Z} Z {\displaystyle Z} r > 1 {\displaystyle r>1}

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

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

  1. Ранг слишком велик: ; r > r E ( I 1 , I 2 , … , I M ) {\displaystyle r>r_{E}(I_{1},I_{2},\ldots ,I_{M})}
  2. Пространство является несбалансированным по идентифицируемости, т.е. , а ранг слишком велик: ; I 1 > ∏ m = 2 M i m − ∑ m = 2 M ( I m − 1 ) {\textstyle I_{1}>\prod _{m=2}^{M}i_{m}-\sum _{m=2}^{M}(I_{m}-1)} r ≥ ∏ m = 2 M I m − ∑ m = 2 M ( I m − 1 ) {\textstyle r\geq \prod _{m=2}^{M}I_{m}-\sum _{m=2}^{M}(I_{m}-1)}
  3. Пространство — это дефектный случай , а ранг — ; F 4 ⊗ F 4 ⊗ F 3 {\displaystyle F^{4}\otimes F^{4}\otimes F^{3}} r = 5 {\displaystyle r=5}
  4. Пространство — дефектный случай , где , а ранг — ; F n ⊗ F n ⊗ F 2 ⊗ F 2 {\displaystyle F^{n}\otimes F^{n}\otimes F^{2}\otimes F^{2}} n ≥ 2 {\displaystyle n\geq 2} r = 2 n − 1 {\displaystyle r=2n-1}
  5. Пространство равно , а ранг равен ; F 4 ⊗ F 4 ⊗ F 4 {\displaystyle F^{4}\otimes F^{4}\otimes F^{4}} r = 6 {\displaystyle r=6}
  6. Пространство равно , а ранг равен ; или F 6 ⊗ F 6 ⊗ F 3 {\displaystyle F^{6}\otimes F^{6}\otimes F^{3}} r = 8 {\displaystyle r=8}
  7. Пространство равно , а ранг равен . F 2 ⊗ F 2 ⊗ F 2 ⊗ F 2 ⊗ F 2 {\displaystyle F^{2}\otimes F^{2}\otimes F^{2}\otimes F^{2}\otimes F^{2}} r = 5 {\displaystyle r=5}
  8. Пространство является совершенным, т.е. представляет собой целое число, а ранг равен . r E ( I 1 , I 2 , … , I M ) = Π Σ + 1 {\textstyle r_{E}(I_{1},I_{2},\ldots ,I_{M})={\frac {\Pi }{\Sigma +1}}} r = r E ( I 1 , I 2 , … , I M ) {\textstyle r=r_{E}(I_{1},I_{2},\ldots ,I_{M})}

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

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

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

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

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

min a i m ∈ F I m ‖ A − ∑ i = 1 r a i 1 ⊗ a i 2 ⊗ ⋯ ⊗ a i M ‖ F , {\displaystyle \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},}

где - норма Фробениуса . ‖ ⋅ ‖ F {\displaystyle \|\cdot \|_{F}}

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

A = u ⊗ u ⊗ v + u ⊗ v ⊗ u + v ⊗ u ⊗ u , with  ‖ u ‖ = ‖ v ‖ = 1  and  ⟨ u , v ⟩ ≠ 1 {\displaystyle {\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

A n = n ( u + 1 n v ) ⊗ ( u + 1 n v ) ⊗ ( u + 1 n v ) − n u ⊗ u ⊗ u {\displaystyle {\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} }

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

A n = ∑ i = 1 r a i , n 1 ⊗ a i , n 2 ⊗ ⋯ ⊗ a i , n M {\displaystyle {\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}}

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

‖ a i , n 1 ⊗ a i , n 2 ⊗ ⋯ ⊗ a i , n M ‖ F → ∞  and  ‖ a j , n 1 ⊗ a j , n 2 ⊗ ⋯ ⊗ a j , n M ‖ F → ∞ {\displaystyle \|\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 }

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

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

Расчет CPD

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

  • альтернативный метод наименьших квадратов (ALS)
  • чередующаяся диагонализация послойно (ASD)

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

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

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

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

Приложения

В машинном обучении CP-разложение является центральным компонентом в обучении вероятностных моделей скрытых переменных с помощью техники сопоставления моментов. Например, рассмотрим модель с несколькими представлениями [32], которая является вероятностной моделью скрытых переменных. В этой модели генерация выборок постулируется следующим образом: существует скрытая случайная величина, которая не наблюдается напрямую, при этом существует несколько условно независимых случайных величин, известных как различные «представления» скрытой переменной. Например, предположим, что существует три представления категориальной скрытой переменной с -состоянием . Тогда эмпирический третий момент этой модели скрытых переменных является тензором ранга 3 и может быть разложен как: . x 1 , x 2 , x 3 {\displaystyle x_{1},x_{2},x_{3}} k {\displaystyle k} h {\displaystyle h} E [ x 1 ⊗ x 2 ⊗ x 3 ] {\displaystyle E[x_{1}\otimes x_{2}\otimes x_{3}]} E [ x 1 ⊗ x 2 ⊗ x 3 ] = ∑ i = 1 k P r ( h = i ) E [ x 1 | h = i ] ⊗ E [ x 2 | h = i ] ⊗ E [ x 3 | h = i ] {\displaystyle 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 ] {\displaystyle E[x|h=i]}

Смотрите также

Ссылки

  1. ^ Папалексакис, Евангелос. «Автоматический неконтролируемый тензорный майнинг с оценкой качества» (PDF) .
  2. ^ FL Hitchcock (1927). «Выражение тензора или полиадического уравнения в виде суммы произведений». Журнал математики и физики . 6 ( 1– 4): 164– 189. doi :10.1002/sapm192761164.
  3. ^ ab Carroll, JD; Chang, J. (1970). "Анализ индивидуальных различий в многомерном шкалировании посредством n -стороннего обобщения разложения "Эккарта–Юнга"". Psychometrika . 35 (3): 283– 319. doi :10.1007/BF02310791. S2CID  50364581.
  4. ^ ab Harshman, Richard A. (1970). "Основы процедуры PARAFAC: Модели и условия для "объяснительного" мультимодального факторного анализа" (PDF) . UCLA Working Papers in Phonetics . 16 : 84. № 10,085. Архивировано из оригинала (PDF) 10 октября 2004 г.
  5. ^ Гуджрал, Экта. «Aptera: автоматический тензорный анализ PARAFAC2» (PDF) . АСОНАМ 2022.
  6. ^ Хиллар, К.Дж.; Лим, Л. (2013). «Большинство тензорных задач являются NP-трудными». Журнал ACM . 60 (6): 1– 39. arXiv : 0911.1393 . doi : 10.1145/2512329. S2CID  1460452.
  7. ^ Ландсберг, Дж. М. (2012). Тензоры: геометрия и приложения . AMS.
  8. ^ abc de Silva, V.; Lim, L. (2008). «Тензорный ранг и некорректность задачи наилучшего низкорангового приближения». Журнал SIAM по матричному анализу и приложениям . 30 (3): 1084–1127 . arXiv : math/0607647 . doi :10.1137/06066518x. S2CID  7159193.
  9. ^ Штрассен, В. (1983). «Ранг и оптимальное вычисление общих тензоров». Линейная алгебра и ее приложения . 52/53: 645– 685. doi : 10.1016/0024-3795(83)80041-x .
  10. ^ Catalisano, MV; Geramita, AV; Gimigliano, A. (2002). «Ранги тензоров, секущие многообразия многообразий Сегре и толстые точки». Линейная алгебра и ее приложения . 355 ( 1– 3): 263– 285. doi : 10.1016/s0024-3795(02)00352-x .
  11. ^ ab Abo, H.; Ottaviani, G.; Peterson, C. (2009). «Индукция для секущих многообразий многообразий Сегре». Труды Американского математического общества . 361 (2): 767– 792. arXiv : math/0607191 . doi :10.1090/s0002-9947-08-04725-9. S2CID  59069541.
  12. ^ Ликтейг, Томас (1985). «Типичный тензорный ранг». Линейная алгебра и ее приложения . 69 : 95– 120. doi : 10.1016/0024-3795(85)90070-9 .
  13. ^ Catalisano, MV; Geramita, AV; Gimigliano, A. (2011). "Секущие многообразия P {\displaystyle \mathbb {P} } 1 × ··· × P {\displaystyle \mathbb {P} } 1 (n-times) не являются дефектными для 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. doi :10.1137/0209053.
  16. ^ Харрис, Джо (1992). Алгебраическая геометрия SpringerLink . Graduate Texts in Mathematics. Том 133. doi :10.1007/978-1-4757-2189-8. ISBN 978-1-4419-3099-6.
  17. ^ ab Chiantini, L.; Ottaviani, G.; Vannieuwenhoven, N. (2014-01-01). «Алгоритм для общей и низкоранговой специфической идентифицируемости комплексных тензоров». SIAM Journal on Matrix Analysis and Applications . 35 (4): 1265– 1287. arXiv : 1403.4157 . doi : 10.1137/140961389. ISSN  0895-4798. S2CID  28478606.
  18. ^ Боччи, Криштиану; Кьянтини, Лука; Оттавиани, Джорджио (01 декабря 2014 г.). «Уточненные методы идентифицируемости тензоров». Аннали ди Математика Pura ed Applicata . 193 (6): 1691–1702 . arXiv : 1303.6915 . дои : 10.1007/s10231-013-0352-8. ISSN  0373-3114. S2CID  119721371.
  19. ^ Chiantini, L.; Ottaviani, G.; Vannieuwenhoven, N. (2017-01-01). «Эффективные критерии специфической идентифицируемости тензоров и форм». SIAM Journal on Matrix Analysis and Applications . 38 (2): 656– 681. arXiv : 1609.00123 . doi : 10.1137/16m1090132. ISSN  0895-4798. S2CID  23983015.
  20. ^ Chiantini, L.; Ottaviani, G. (2012-01-01). «О общей идентифицируемости 3-тензоров малого ранга». SIAM Journal on Matrix Analysis and Applications . 33 (3): 1018– 1037. arXiv : 1103.2696 . doi : 10.1137/110829180. ISSN  0895-4798. S2CID  43781880.
  21. ^ ab Hauenstein, JD; Oeding, L.; Ottaviani, G.; Sommese, AJ (2016). «Гомотопические методы для разложения тензора и совершенной идентифицируемости». J. Reine Angew. Math . 2019 (753): 1– 22. arXiv : 1501.00090 . doi : 10.1515/crelle-2016-0067. S2CID  16324593.
  22. ^ Боччи, Кристиано; Кьянтини, Лука (2013). «Об идентифицируемости бинарных произведений Сегре». Журнал алгебраической геометрии . 22 (1): 1– 11. arXiv : 1105.3643 . doi : 10.1090/s1056-3911-2011-00592-4. ISSN  1056-3911. S2CID  119671913.
  23. ^ Доманов, Игнат; Латхауэр, Ливен Де (январь 2014). «Каноническое полиадическое разложение тензоров третьего порядка: редукция к обобщенному разложению по собственным значениям». SIAM Journal on Matrix Analysis and Applications . 35 (2): 636– 660. arXiv : 1312.2848 . doi : 10.1137/130916084. ISSN  0895-4798. S2CID  14851072.
  24. ^ Доманов, Игнат; Де Латхауэр, Ливен (январь 2017 г.). «Каноническое полиадическое разложение тензоров третьего порядка: ослабленные условия уникальности и алгебраический алгоритм». Линейная алгебра и ее приложения . 513 : 342–375 . arXiv : 1501.07251 . doi : 10.1016/j.laa.2016.10.019. ISSN  0024-3795. S2CID  119729978.
  25. ^ Faber, Nicolaas (Klaas) M.; Ferré, Joan; Boqué, Ricard (январь 2001 г.). «Метод обобщенного рангового уничтожения с итеративным перевесом». Chemometrics and Intelligent Laboratory Systems . 55 ( 1– 2): 67– 90. doi :10.1016/s0169-7439(00)00117-9. ISSN  0169-7439.
  26. ^ Leurgans, SE ; Ross, RT; Abel, RB (октябрь 1993 г.). «Разложение для трехмерных массивов». Журнал SIAM по матричному анализу и приложениям . 14 (4): 1064– 1083. doi :10.1137/0614071. ISSN  0895-4798.
  27. ^ Лорбер, Авраам. (Октябрь 1985). «Особенности количественной оценки химического состава из двумерного массива данных методом рангового аннигиляционного факторного анализа». Аналитическая химия . 57 (12): 2395– 2397. doi :10.1021/ac00289a052. ISSN  0003-2700.
  28. ^ Санчес, Эухенио; Ковальски, Брюс Р. (январь 1990 г.). «Тензорное разрешение: прямое трилинейное разложение». Журнал хемометрики . 4 (1): 29– 45. doi :10.1002/cem.1180040105. ISSN  0886-9383. S2CID  120459386.
  29. ^ Сэндс, Ричард; Янг, Форрест В. (март 1980 г.). «Компонентные модели для трехмерных данных: алгоритм альтернативных наименьших квадратов с оптимальными характеристиками масштабирования». Психометрика . 45 (1): 39–67 . doi :10.1007/bf02293598. ISSN  0033-3123. S2CID  121003817.
  30. ^ Бернарди, А.; Брачат, Дж.; Комон, П.; Моррен, Б. (май 2013 г.). «Общее тензорное разложение, матрицы моментов и приложения». Журнал символических вычислений . 52 : 51–71 . arXiv : 1105.1229 . doi : 10.1016/j.jsc.2012.05.012. ISSN  0747-7171. S2CID  14181289.
  31. ^ Бернарди, Алессандра; Далео, Ноа С.; Хауенштейн, Джонатан Д.; Моррен, Бернард (декабрь 2017 г.). «Тензорное разложение и гомотопическое продолжение». Дифференциальная геометрия и ее приложения . 55 : 78–105 . arXiv : 1512.04312 . doi :10.1016/j.difgeo.2017.07.009. ISSN  0926-2245. S2CID  119147635.
  32. ^ Anandkumar, Animashree; Ge, Rong; Hsu, Daniel; Kakade, Sham M; Telgarsky, Matus (2014). «Тензорные разложения для обучения моделей скрытых переменных». Журнал исследований машинного обучения . 15 (1): 2773–2832 .

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

  • Колда, Тамара Г.; Бадер, Бретт В. (2009). «Тензорные разложения и приложения». SIAM Rev. 51 ( 3): 455– 500. Bibcode :2009SIAMR..51..455K. CiteSeerX  10.1.1.153.2059 . doi :10.1137/07070111X. S2CID  16074195.
  • Ландсберг, Джозеф М. (2012). Тензоры: геометрия и приложения . AMS.
  • Учебное пособие PARAFAC
  • Параллельный факторный анализ (PARAFAC)
  • FactoMineR (бесплатное исследовательское программное обеспечение для многомерного анализа данных, связанное с R )
Retrieved from "https://en.wikipedia.org/w/index.php?title=Tensor_rank_decomposition&oldid=1260068127"