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

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

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

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

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

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

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

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

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

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