Алгоритм дополнения матриц
| Алгоритм дополнения матриц | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(|\Omega|r^2) }[/math] |
| Объём входных данных | [math]\displaystyle{ |\Omega| }[/math] |
| Объём выходных данных | [math]\displaystyle{ 2nr }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ const }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ const }[/math] |
Свойства и структура алгоритма[править]
Общее описание алгоритма[править]
Определим задачу заполнения неизвестных значений матрицы.
Задача: восстановить матрицу, имеющую малый (известный алгоритму) ранг, по некоторому подмножеству ее элементов.
Будем оптимизировать норму ошибки на известных элементах с помощью аналога градиентного спуска. После каждого шага будем возвращаться в множество матриц фиксированного ранга, так же как и в случае обычного градиентного спуска (проектором может служить, например, SVD разложение).
Однако такой алгоритм обладает рядом недостатков, самый существенный из которых - высокая сложность работы. Для SVD разложения необходимо совершить [math]\displaystyle{ O(n^3) }[/math] действий.
Исправить эту ошибку призван следующий подход. Будем рассматривать матрицы фиксированного ранга как гладкое риманово многообразие. К каждому элементу этого многообразия зададим касательное пространство. Перед тем, как вычесть градиент из текущего приближения, сначала спроектируем его на касательное пространство к текущему приближению. Благодаря этому матрица, полученная после совершения градиентного шага будет иметь ранг не выше [math]\displaystyle{ 2r }[/math] (если считать, что исходный ранг был [math]\displaystyle{ r }[/math]). Теперь от этой матрицы не сложно сделать SVD разложение, потому что она имеет небольшие размеры.
Математическое описание алгоритма[править]
[math]\displaystyle{ M }[/math] - матрица, известная нам только на заданном множестве индексов (по-сути мы знаем только [math]\displaystyle{ P_{\Omega}(M) }[/math]).
Введем оператор [math]\displaystyle{ P_{\Omega}(X)_{i, j} = X_{i, j} }[/math] если [math]\displaystyle{ {i, j} \in \Omega }[/math], иначе 0.
Множество матриц с рангом r будем обозначать [math]\displaystyle{ M_r }[/math], касательное пространство к матрице [math]\displaystyle{ X \in M_r }[/math] - [math]\displaystyle{ T_x M_r }[/math]. Введем так же проектор на касательное пространство.Пусть [math]\displaystyle{ X_i = U \Sigma V_T }[/math]. Тогда [math]\displaystyle{ P_{T_x M_r}(Z) = P_{U}ZP_{V} + P_{U^\perp}ZP_{V} + P_{U}ZP_{V^\perp} }[/math].
Запишем алгоритм:
WHILE([math]\displaystyle{ ||P_{\Omega}(X_{t} - M)|| \geq \varepsilon }[/math]) do
[math]\displaystyle{ X_{t+1} = SVD(X_{t} - \alpha_t P_{T_x M_r} P_{\Omega}(X_{t} - M)) }[/math]
end
Макроструктура алгоритма[править]
Схема реализации последовательного алгоритма[править]
Последовательная сложность алгоритма[править]
Информационный граф[править]
Ресурс параллелизма алгоритма[править]
Входные и выходные данные алгоритма[править]
Свойства алгоритма[править]
Программная реализация алгоритма[править]
Особенности реализации последовательного алгоритма[править]
Локальность данных и вычислений[править]
Локальность реализации алгоритма[править]
Структура обращений в память и качественная оценка локальности[править]
Количественная оценка локальности[править]
Возможные способы и особенности параллельной реализации алгоритма[править]
Масштабируемость алгоритма и его реализации[править]
Масштабируемость алгоритма[править]
Масштабируемость реализации алгоритма[править]
Динамические характеристики и эффективность реализации алгоритма[править]
Выводы для классов архитектур[править]
Существующие реализации алгоритма[править]
Литература[править]
[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