Алгоритм дополнения матриц

Восстановление матриц с использованием оптимизации на римановых многообразиях
Последовательный алгоритм
Последовательная сложность	$O(|\Omega|r^2)$
Объём входных данных	$|\Omega|$
Объём выходных данных	$2nr$
Параллельный алгоритм
Высота ярусно-параллельной формы	$const$
Ширина ярусно-параллельной формы	$const$

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Определим задачу заполнения неизвестных значений матрицы.

Задача: восстановить матрицу, имеющую малый (известный алгоритму) ранг, по некоторому подмножеству ее элементов.

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

Однако такой алгоритм обладает рядом недостатков, самый существенный из которых - высокая сложность работы. Для SVD разложения необходимо совершить $O(n^3)$ действий.

Исправить эту ошибку призван следующий подход. Будем рассматривать матрицы фиксированного ранга как гладкое риманово многообразие. К каждому элементу этого многообразия зададим касательное пространство. Перед тем, как вычесть градиент из текущего приближения, сначала спроектируем его на касательное пространство к текущему приближению. Благодаря этому матрица, полученная после совершения градиентного шага будет иметь ранг не выше $2r$ (если считать, что исходный ранг был $r$). Теперь от этой матрицы не сложно сделать SVD разложение, потому что она имеет небольшие размеры.

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

$M$ - матрица, известная нам только на заданном множестве индексов (по-сути мы знаем только $P_{\Omega}(M)$).

Введем оператор $P_{\Omega}(X)_{i, j} = X_{i, j}$ если ${i, j} \in \Omega$, иначе 0.

Множество матриц с рангом r будем обозначать $M_r$, касательное пространство к матрице $X \in M_r$ - $T_x M_r$. Введем так же проектор на касательное пространство.Пусть $X_i = U \Sigma V_T$. Тогда $P_{T_x M_r}(Z) = P_{U}ZP_{V} + P_{U^\perp}ZP_{V} + P_{U}ZP_{V^\perp}$.

Запишем алгоритм:

WHILE($||P_{\Omega}(X_{t} - M)|| \geq \varepsilon$) do

$X_{t+1} = SVD(X_{t} - \alpha_t P_{T_x M_r} P_{\Omega}(X_{t} - M))$

end

3 Литература

[1] Guaranteed Rank Minimization via Singular Value Projection.Raghu Meka, Prateek Jain, Inderjit S. Dhillon // arXiv:0909.5457

[2] Low-rank matrix completion by Riemannian optimization. Bart Vandereycken // arXiv:0909.5457