Аппроксимация матрицы CUR

Аппроксимация матрицы CUR — это набор из трех матриц , которые при умножении вместе точно аппроксимируют данную матрицу. Приближение CUR можно использовать так же, как аппроксимацию низкого ранга сингулярного разложения (SVD). Приближения CUR менее точны, чем SVD, но они предлагают два ключевых преимущества, оба из которых связаны с тем, что строки и столбцы берутся из исходной матрицы (а не из левого и правого сингулярных векторов):

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

Формально, аппроксимация матрицы CUR матрицы A — это три матрицы C , U и R, такие, что C состоит из столбцов A , R состоит из строк A и что произведение CUR близко аппроксимирует A. , Обычно CUR выбирается как аппроксимация ранга - k , что означает, что содержит k столбцов A , R содержит k строк A , а U - матрица k -k C . Существует множество возможных аппроксимаций матрицы CUR и множество аппроксимаций матрицы CUR для данного ранга.

Приближение матрицы CUR часто используется вместо низкоранговой аппроксимации SVD в анализе главных компонент . CUR менее точен, но столбцы матрицы C берутся из A а строки R — из A. , В PCA каждый столбец A содержит выборку данных; таким образом, матрица C состоит из подмножества выборок данных. Это гораздо легче интерпретировать, чем левые сингулярные векторы SVD, которые представляют данные во повернутом пространстве. Аналогично, матрица R состоит из подмножества переменных, измеренных для каждой выборки данных. Это легче понять, чем правые сингулярные векторы SVD, которые представляют собой еще одно вращение данных в пространстве.

Математическое определение

Хамм и Хуанг дает следующую теорему, описывающую основы CUR-разложения матрицы $L$ со званием $r$:

Теорема: рассмотрим индексы строк и столбцов. $I,J\subseteq [n]$ с $|I|,|J|\geq r$.Обозначим подматрицы $C=L_{:,J},$ $U=L_{I,J}$ и $R=L_{I,:}$.Если ранг( $U$) = ранг( $L$), затем $L=CU^{+}R$, где $(\cdot )^{+}$ обозначает псевдообратную функцию Мура–Пенроуза .

Другими словами, если $L$ имеет низкий ранг, мы можем взять подматрицу $U=L_{I,J}$ одного и того же ранга вместе с некоторыми рядами $R$ и столбцы $C$ из $L$ и использовать их для восстановления $L$.

Алгоритмы

Приближение матрицы CUR не уникально, и существует несколько алгоритмов его вычисления. Один из них — АЛГОРИТМКУР.

Алгоритм «Линейное время CUR» просто выбирает J путем случайной выборки столбцов (с заменой) с вероятностью, пропорциональной нормам столбцов в квадрате, $\|L_{:,j}\|_{2}^{2}$; и аналогичным образом выборка I пропорциональна нормам квадратов строк, $\|L_{i}\|_{2}^{2}$.Авторы показывают, чтопринимая $|J|\approx k/\varepsilon ^{4}$ и $|I|\approx k/\varepsilon ^{2}$ где $0\leq \varepsilon$, алгоритм достигает границы ошибки Фробениуса $\|A-CUR\|_{F}\leq \|A-A_{k}\|_{F}+\varepsilon \|A\|_{F}$, где $A_{k}$ — оптимальное приближение ранга k .

Тензор

Разложение тензора-CURT является обобщением разложения матрицы по CUR. Формально тензорная аппроксимация CURT тензора A представляет собой три матрицы и (ядерный) тензор C , R , T и U такой, что C состоит из столбцов A , R состоит из строк A , T состоит из трубок A U(C,R, T и что произведение ) (где $i,j,l$-я запись это $\sum _{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'}$) близко приближается к A . Обычно CURT выбирается как аппроксимация ранга - k , что означает, что содержит k столбцов A , R содержит k строк A , T содержит трубки A и U собой k -k -k C представляет (ядро -)тензор.

См. также

• Уменьшение размерности