Завершение матрицы

Заполнение матрицы частично раскрытой матрицы 5 на 5 с рангом-1. Слева: наблюдаемая неполная матрица; Справа: результат завершения матрицы.

Заполнение матрицы — это задача заполнения недостающих записей частично наблюдаемой матрицы, что эквивалентно выполнению вменения данных в статистике. Широкий спектр наборов данных естественным образом организован в матричной форме. Одним из примеров является матрица рейтингов фильмов, как это показано в задаче Netflix : дана матрица рейтингов, в которой каждая запись $(i,j)$ представляет рейтинг фильма $j$ клиентом $i$, если клиент $i$ посмотрел фильм $j$ а в противном случае отсутствует, мы хотели бы спрогнозировать оставшиеся записи, чтобы дать клиентам хорошие рекомендации о том, что смотреть дальше. Другим примером является матрица терминов документа : частоты слов, используемых в коллекции документов, могут быть представлены в виде матрицы, где каждая запись соответствует количеству раз, когда соответствующий термин появляется в указанном документе.

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

Например, можно предположить, что матрица имеет структуру низкого ранга, а затем попытаться найти матрицу наименьшего ранга или, если известен ранг завершенной матрицы, матрицу ранга $r$ который соответствует известным записям. На иллюстрации показано, что частично раскрытая матрица ранга 1 (слева) может быть заполнена с нулевой ошибкой (справа), поскольку все строки с пропущенными элементами должны быть такими же, как третья строка. В случае с Netflix ожидается, что матрица рейтингов будет низкоранговой, поскольку предпочтения пользователей часто можно описать несколькими факторами, такими как жанр фильма и время выпуска. Другие приложения включают компьютерное зрение, где необходимо восстановить недостающие пиксели в изображениях, определение глобального положения датчиков в сети на основе информации о частичном расстоянии и многоклассовое обучение . Проблема пополнения матрицы в целом является NP-трудной , но при дополнительных предположениях существуют эффективные алгоритмы, которые обеспечивают точное восстановление с высокой вероятностью.

С точки зрения статистического обучения проблема пополнения матрицы представляет собой применение матричной регуляризации , которая является обобщением векторной регуляризации . Например, в задаче пополнения матрицы низкого ранга можно применить штраф за регуляризацию, принимающий форму ядерной нормы $R(X)=\lambda \|X\|_{*}$

Завершение матрицы низкого ранга

Один из вариантов задачи пополнения матрицы — найти наименьшего ранга . матрицу $X$ что соответствует матрице $M$, который мы хотим восстановить, для всех записей в наборе $E$ наблюдаемых записей. Математическая формулировка этой задачи такова:

${\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}$

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

Эквивалентная формулировка, учитывая, что матрица $M$ известно, что подлежащий восстановлению имеет ранг $r$, состоит в том, чтобы решить $X$ где $X_{ij}=M_{ij}\;\;\forall i,j\in E$

Предположения

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

Равномерная выборка наблюдаемых записей

Чтобы сделать анализ более понятным, часто предполагается, что множество $E$ наблюдаемых записей и фиксированной мощности выбирается равномерно случайным образом из совокупности всех подмножеств записей мощности $|E|$. Для дальнейшего упрощения анализа вместо этого предполагается, что $E$ строится методом выборки Бернулли , т.е. каждая запись наблюдается с вероятностью $p$. Если $p$ установлено на ${\frac {N}{mn}}$ где $N$ желаемая мощность ожидаемая $E$, и $m,\;n$ – размеры матрицы (пусть $m<n$ без потери общности), $|E|$ находится внутри $O(n\log n)$ из $N$ с высокой вероятностью, поэтому выборка Бернулли является хорошим приближением для равномерной выборки. Еще одно упрощение — предположить, что выборка записей осуществляется независимо и с заменой.

Нижняя граница количества наблюдаемых записей

Предположим, $m$ к $n$ матрица $M$ (с $m<n$) пытаемся восстановить имеет ранг $r$. Существует теоретико-информационная нижняя граница того, сколько записей необходимо просмотреть, прежде чем $M$ могут быть однозначно реконструированы. Набор $m$ к $n$ матрицы с рангом меньшим или равным $r$ является алгебраическим многообразием в ${\mathbb {C} }^{m\times n}$с размером $(n+m)r-r^{2}$.Используя этот результат,это можно показать по крайней мере $4nr-4r^{2}$записи должны быть соблюдены для завершения матрицы в ${\mathbb {C} }^{n\times n}$иметь уникальное решение когда $r\leq n/2$.

Во-вторых, в каждой строке и столбце должна быть хотя бы одна наблюдаемая запись. $M$. Разложение сингулярным значениям по $M$ дается $U\Sigma V^{\dagger }$. Если строка $i$ не наблюдается, легко увидеть $i^{\text{th}}$ правый сингулярный вектор $M$, $v_{i}$, можно изменить на какое-то произвольное значение и при этом получить матрицу, соответствующую $M$ по набору наблюдаемых записей. Аналогично, если столбец $j$ остается незамеченным, т. $j^{\text{th}}$ левый сингулярный вектор $M$, $u_{i}$ может быть произвольным. Если мы предположим, что выборка Бернулли из набора наблюдаемых записей, эффект сборщика купонов подразумевает, что записи порядка $O(n\log n)$ необходимо наблюдать, чтобы обеспечить наличие наблюдения из каждой строки и столбца с высокой вероятностью.

Объединив необходимые условия и полагая, что $r\ll m,n$ (действительное предположение для многих практических приложений), нижняя граница числа наблюдаемых записей, необходимых для предотвращения недоопределенности проблемы завершения матрицы, имеет порядок $nr\log n$.

непоследовательность

Концепция некогерентности возникла в сжатом восприятии . Он вводится в контексте пополнения матрицы, чтобы обеспечить сингулярность векторов $M$ не слишком «разрежены» в том смысле, что все координаты каждого сингулярного вектора имеют сопоставимую величину, а не только несколько координат, имеющих значительно большие величины. В этом случае стандартные базисные векторы нежелательны как сингулярные векторы, а вектор ${\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}$ в $\mathbb {R} ^{n}$ желательно. В качестве примера того, что может пойти не так, если сингулярные векторы достаточно «разрежены», рассмотрим $m$ к $n$ матрица ${\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}$ с разложением по сингулярным значениям $I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}$. Почти все записи $M$ необходимо провести выборку, прежде чем ее можно будет реконструировать.

Кандес и право определить связность матрицы $U$ с столбца пространством $r-$размерное подпространство $\mathbb {R} ^{n}$ как $\mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}$, где $P_{U}$ ортогональная проекция на $U$. Тогда некогерентность утверждает, что с учетом разложения по сингулярным значениям $U\Sigma V^{\dagger }$ принадлежащий $m$ к $n$ матрица $M$,

1. $\mu (U),\;\mu (V)\leq \mu _{0}$
2. Записи $\sum _{k}u_{k}v_{k}^{\dagger }$ имеют величины, ограниченные сверху $\mu _{1}{\sqrt {\frac {r}{mn}}}$

для некоторых $\mu _{0},\;\mu _{1}$.

Заполнение матрицы низкого ранга с шумом

В реальных приложениях часто можно наблюдать лишь несколько записей, искаженных хотя бы небольшим количеством шума. Например, в проблеме Netflix рейтинги неопределенны. Кандес и План показал, что можно заполнить многие недостающие элементы больших матриц низкого ранга всего из нескольких зашумленных выборок путем минимизации ядерной нормы. Шумная модель предполагает, что мы наблюдаем

$Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,$

где ${Z_{ij}:(i,j)\in \Omega }$ это шумовой термин. Обратите внимание, что шум может быть стохастическим или детерминированным. В качестве альтернативы модель может быть выражена как

$P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),$

где $Z$ это $n\times n$ матрица с записями $Z_{ij}$ для $(i,j)\in \Omega$ предполагая, что $\|P_{\Omega }(Z)\|_{F}\leq \delta$ для некоторых $\delta >0$ .Чтобы восстановить неполную матрицу, попытаемся решить следующую оптимизационную задачу:

${\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}$

Среди всех матриц, соответствующих данным, найти матрицу с минимальной ядерной нормой. Кандес и План показали, что эта реконструкция точна. Они доказали, что когда происходит идеальное бесшумное восстановление, пополнение матрицы устойчиво к возмущениям. Ошибка пропорциональна уровню шума $\delta$. Следовательно, когда уровень шума мал, ошибка мала. Здесь проблема пополнения матрицы не подчиняется свойству ограниченной изометрии (RIP). Для матриц RIP предполагает, что оператор выборки подчиняется

$(1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}$

для всех матриц $X$ достаточно малого ранга и $\delta <1$ достаточно мал.Эти методы также применимы к задачам восстановления разреженных сигналов, в которых RIP не соблюдается.

Завершение матрицы высокого ранга

Заполнение матрицы высокого ранга в целом является NP-Hard . Однако при определенных допущениях может быть заполнена некоторая неполная матрица высокого ранга или даже матрица полного ранга.

Эрикссон, Бальзано и Новак рассмотрели проблему дополнения матрицы в предположении, что столбцы матрицы принадлежат объединению нескольких подпространств низкого ранга. Поскольку столбцы принадлежат объединению подпространств, проблему можно рассматривать как версию проблемы кластеризации подпространств с недостатком данных . Позволять $X$ быть $n\times N$ матрица, (полные) столбцы которой лежат в объединении не более $k$ подпространства, каждое из $rank\leq r<n$и предположим $N\gg kn$. Эрикссон, Бальзано и Новак показали, что при мягких предположениях каждый столбец $X$ могут быть с высокой вероятностью полностью восстановлены из неполной версии, если хотя бы $CrN\log ^{2}(n)$ записи $X$ наблюдаются равномерно случайным образом, причем $C>1$ константа, зависящая от обычных условий некогерентности, геометрического расположения подпространств и распределения столбцов по подпространствам.

Алгоритм включает в себя несколько шагов: (1) локальные окрестности; (2) локальные подпространства; (3) уточнение подпространства; (4) полное завершение матрицы. Этот метод можно применять для заполнения матрицы расстояний в Интернете и идентификации топологии.

Алгоритмы завершения матрицы низкого ранга

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

Выпуклая релаксация

Задача минимизации ранга NP-трудна . Один из подходов, предложенный Кандесом и Рехтом, состоит в том, чтобы сформировать выпуклую релаксацию задачи и минимизировать ядерную норму. $\|M\|_{*}$ (что дает сумму значений сингулярных $M$) вместо ${\text{rank}}(M)$ (который подсчитывает количество ненулевых сингулярных значений $M$). Это аналогично минимизации L1- нормы , а не L0- нормы для векторов. Выпуклую (SDP), заметив , релаксацию можно решить с помощью полуопределенного программирования что задача оптимизации эквивалентна

${\begin{aligned}&{\underset {W_{1},W_{2}}{\text{min}}}&&{\text{trace}}(W_{1})+{\text{trace}}(W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}$

Сложность использования SDP для решения выпуклой релаксации составляет $O({\text{max}}(m,n)^{4})$. Современные решатели, такие как SDPT3, могут обрабатывать только матрицы размером до 100 на 100. Альтернативным методом первого порядка, который приближенно решает проблему выпуклой релаксации, является алгоритм определения порога сингулярного значения, предложенный Каем, Кандесом и Шеном.

Кандес и Рехт показывают, используя исследование случайных величин в банаховых пространствах , что если число наблюдаемых записей порядка $\max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n$ (предположим без ограничения общности $m<n$), задача минимизации ранга имеет единственное решение, которое также является решением ее выпуклой релаксации с вероятностью $1-{\frac {c}{n^{3}}}$ для некоторой константы $c$. Если ранг $M$ маленький( $r\leq {\frac {n^{0.2}}{\mu _{0}}}$), размер множества наблюдений уменьшается до порядка $\mu _{0}n^{1.2}r\log n$. Эти результаты близки к оптимальным, поскольку минимальное количество записей, которое необходимо соблюдать, чтобы проблема пополнения матрицы не была недоопределенной, имеет порядок $nr\log n$.

Этот результат был улучшен Кандесом и Тао. Они достигают границ, которые отличаются от оптимальных границ только полилогарифмическими коэффициентами за счет усиления предположений. Вместо свойства некогерентности они предполагают свойство сильной некогерентности с параметром $\mu _{3}$. В этом свойстве указано, что:

1. $|\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}$ для $a,a'\leq m$ и $|\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}$ для $b,b'\leq n$
2. Записи $\sum _{i}u_{i}v_{i}^{\dagger }$ ограничены по величине $\mu _{3}{\sqrt {\frac {r}{mn}}}$

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

Кандес и Тао обнаруживают это, когда $r$ является $O(1)$ и количество наблюдаемых записей порядка $\mu _{3}^{4}n(\log n)^{2}$, задача минимизации ранга имеет единственное решение, которое также является решением ее выпуклой релаксации с вероятностью $1-{\frac {c}{n^{3}}}$ для некоторой константы $c$. Для произвольного $r$, количество наблюдаемых записей, достаточное для справедливости этого утверждения, порядка $\mu _{3}^{2}nr(\log n)^{6}$

Другой подход выпуклой релаксации заключается в минимизации квадрата нормы Фробениуса при ограничении ранга. Это эквивалентно решению

${\begin{aligned}&{\underset {X}{\text{min}}}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{Rank}}(X)\leq k.\end{aligned}}$

Введя матрицу ортогонального проектирования $Y$ (значение $Y^{2}=Y,Y=Y'$) для моделирования ранга $X$ с помощью $X=YX,{\text{trace}}(Y)\leq k$ и взяв выпуклую релаксацию этой задачи, получим следующую полуопределенную программу

${\begin{aligned}&{\underset {X,Y,\theta }{\text{min}}}&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{trace}}(Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}$

Если Y является матрицей проекции (т. е. имеет двоичные собственные значения) в этой релаксации, то релаксация является жесткой. В противном случае это дает действительную нижнюю границу общей цели. Более того, его можно преобразовать в осуществимое решение с (немного) большей целью, жадно округлив собственные значения Y. Примечательно, что эту выпуклую релаксацию можно решить путем поочередной минимизации по X и Y без решения каких-либо SDP, и, таким образом, она масштабируется за пределы типичных числовых пределов современных решателей SDP, таких как SDPT3 или Mosek.

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

Градиентный спуск

Кешаван, Монтанари и О рассмотрим вариант пополнения матрицы, при ранг котором $m$ к $n$ матрица $M$, который необходимо восстановить, как известно, $r$. Они предполагают выборку записей по Бернулли, постоянное соотношение сторон. ${\frac {m}{n}}$, ограниченная величина записей $M$ (пусть верхняя граница будет $M_{\text{max}}$) и постоянное число обусловленности ${\frac {\sigma _{1}}{\sigma _{r}}}$ (где $\sigma _{1}$ и $\sigma _{r}$ являются наибольшим и наименьшим сингулярными значениями $M$ соответственно). Кроме того, они предполагают, что два условия некогерентности удовлетворяются $\mu _{0}$ и $\mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}$ где $\mu _{0}$ и $\mu _{1}$ являются константами. Позволять $M^{E}$ быть матрицей, которая соответствует $M$ на съемочной площадке $E$ наблюдаемых записей и равно 0 в других местах. Далее они предлагают следующий алгоритм:

1. Подрезать $M^{E}$ удалив все наблюдения из столбцов со степенью больше, чем ${\frac {2|E|}{n}}$ установив записи в столбцах на 0. Аналогичным образом удалите все наблюдения из строк со степенью больше, чем ${\frac {2|E|}{n}}$.
2. Проект $M^{E}$ на свой первый $r$ основные компоненты . Вызовите полученную матрицу ${\text{Tr}}(M^{E})$.
3. Решать $\min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)$ где $G(X,Y)$ — это некоторая регуляризации функция градиентным спуском с поиском по строке . Инициализировать $X,\;Y$ в $X_{0},\;Y_{0}$ где ${\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }$. Набор $G(X,Y)$ как некоторая функция, заставляющая $X,\;Y$ оставаться некогерентным на протяжении всего градиентного спуска, если $X_{0}$ и $Y_{0}$ являются бессвязными.
4. Вернуть матрицу $XSY^{\dagger }$.

Шаги 1 и 2 алгоритма дают матрицу ${\text{Tr}}(M^{E})$ очень близко к истинной матрице $M$ (измеряемая среднеквадратической ошибкой (RMSE) ) с высокой вероятностью. В частности, с вероятностью $1-{\frac {1}{n^{3}}}$, ${\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}$ для некоторой константы $C$. $\|\cdot \|_{F}$ Фробениуса обозначает норму . Обратите внимание, что для выполнения этого результата не требуется полного набора предположений. Например, условие некогерентности вступает в силу только при точной реконструкции. Наконец, хотя обрезка может показаться нелогичной, поскольку она предполагает выбрасывание информации, она обеспечивает проецирование $M^{E}$ на свой первый $r$ Основные компоненты дают больше информации о базовой матрице $M$ чем о наблюдаемых записях.

На этапе 3 пространство матриц-кандидатов $X,\;Y$ можно уменьшить, заметив, что внутренняя задача минимизации имеет то же решение для $(X,Y)$ что касается $(XQ,YR)$ где $Q$ и $R$ ортонормированы ​ $r$ к $r$ матрицы. Тогда градиентный спуск можно выполнить по векторному произведению двух многообразий Грассмана . Если $r\ll m,\;n$ и наблюдаемый набор записей имеет порядок $nr\log n$, матрица, возвращенная на шаге 3, в точности равна $M$. Тогда алгоритм является оптимальным по порядку, поскольку мы знаем, что для того, чтобы проблема пополнения матрицы не была недоопределенной, количество элементов должно быть порядка $nr\log n$.

Минимизация попеременных наименьших квадратов

Попеременная минимизация представляет собой широко применимый и эмпирически успешный подход для поиска матриц низкого ранга, которые лучше всего соответствуют заданным данным. Например, для задачи завершения матрицы низкого ранга этот метод считается одним из наиболее точных и эффективных и составляет основной компонент выигрышной записи в задаче Netflix. В подходе поочередной минимизации целевая матрица низкого ранга записывается в билинейной форме :

$X=UV^{T}$;

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

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

${\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}$

Алгоритм AltMinComplete, предложенный Джайном, Нетрапалли и Сангхави, указан здесь:

1. Входные данные : наблюдаемый набор $\Omega$, ценности $P_{\Omega }(M)$
2. Раздел $\Omega$ в $2T+1$ подмножества $\Omega _{0},\cdots ,\Omega _{2T}$ с каждым элементом $\Omega$ принадлежащий одному из $\Omega _{t}$ с равной вероятностью (выборка с заменой)
3. ${\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)$ то есть топ- $k$ левые сингулярные векторы ${\frac {1}{p}}P_{\Omega _{0}}(M)$
4. Обрезка : установите все элементы ${\hat {U}}^{0}$ которые имеют величину большую, чем ${\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}$ обнулить и ортонормировать столбцы ${\hat {U}}^{0}$
5. для $t=0,\cdots ,T-1$ делать
6. $\quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}$
7. $\quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}$
8. конец для
9. Возвращаться $X={\hat {U}}^{T}({\hat {V}}^{T})^{T}$

Они показали это, наблюдая $|\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))$ случайные элементы некогерентной матрицы $M$, алгоритм AltMinComplete может восстановить $M$ в $O(\log(1/\epsilon ))$ шаги. По сложности выборки ( $|\Omega |$), теоретически, попеременная минимизация может потребовать большего $\Omega$ чем выпуклая релаксация. Однако эмпирически это не так, а это означает, что границы сложности выборки могут быть еще более ужесточены. С точки зрения временной сложности они показали, что AltMinComplete требует времени.

$O(|\Omega |k^{2}\log(1/\epsilon ))$.

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

Приложения

Некоторые применения матричного завершения суммированы Кандесом и Планом. следующее:

Совместная фильтрация

Совместная фильтрация — это задача автоматического прогнозирования интересов пользователя путем сбора информации о вкусах от многих пользователей. Такие компании, как Apple, Amazon, Barnes and Noble и Netflix, пытаются предсказать предпочтения своих пользователей на основе частичных знаний. В такого рода задачах завершения матрицы неизвестная полная матрица часто считается низким рангом, поскольку лишь несколько факторов обычно влияют на вкусы или предпочтения человека.

Идентификация системы

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

${\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}$

к последовательности входов $u(t)\in \mathbb {R} ^{m}$ и результаты $y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N$. Вектор $x(t)\in \mathbb {R} ^{n}$ это состояние системы в момент времени $t$ и $n$ – это порядок модели системы. Из пары ввода/вывода хотелось бы восстановить матрицы $A,B,C,D$ и исходное состояние $x(0)$. Эту проблему также можно рассматривать как проблему завершения матрицы низкого ранга.

Локализация Интернета вещей (IoT)

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

Восстановление социальных сетей

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

См. также

• Регуляризация матрицы
• Премия Netflix
• Совместная фильтрация
• Идентификация системы
• Выпуклая оптимизация
• вменение