Алгоритм дополнения матриц: различия между версиями

[непроверенная версия]

Текущая версия на 21:55, 26 октября 2021

Восстановление матриц с использованием оптимизации на римановых многообразиях
Последовательный алгоритм
Последовательная сложность	[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 разложение, потому что она имеет небольшие размеры.

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

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

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

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

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

WHILE([math] ||P_{\Omega}(X_{t} - M)|| \geq \varepsilon [/math]) do

[math]X_{t+1} = SVD(X_{t} - \alpha_t P_{T_x M_r} P_{\Omega}(X_{t} - M)) [/math]

end

1.3 Макроструктура алгоритма

1.4 Схема реализации последовательного алгоритма

1.5 Последовательная сложность алгоритма

1.6 Информационный граф

1.7 Ресурс параллелизма алгоритма

1.8 Входные и выходные данные алгоритма

1.9 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

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

@@ Строка 1: / Строка 1: @@
 {{algorithm
-| name              = Восстановление матриц
+| name              = Восстановление матриц с использованием оптимизации на римановых многообразиях
-| serial_complexity = <math>O(n^3)</math>
+| serial_complexity = <math>O(|\Omega|r^2)</math>
-| pf_height         = <math>O(n)</math>
+| pf_height         = <math>const</math>
-| pf_width          = <math>O(n^2)</math>
+| pf_width          = <math>const</math>
-| input_data        = <math>\frac{n (n + 1)}{2}</math>
+| input_data        = <math>|\Omega|</math>
-| output_data       = <math>\frac{n (n + 1)}{2}</math>
+| output_data       = <math>2nr</math>
 }}
@@ Строка 12: / Строка 12: @@
 === Общее описание алгоритма ===
+Определим задачу заполнения неизвестных значений матрицы.
+Задача: восстановить матрицу, имеющую малый (известный алгоритму) ранг, по некоторому подмножеству ее элементов.
+Будем оптимизировать норму ошибки на известных элементах с помощью аналога градиентного спуска. После каждого шага будем возвращаться в множество матриц фиксированного ранга, так же как и в случае обычного градиентного спуска (проектором может служить, например, SVD разложение).
+Однако такой алгоритм обладает рядом недостатков, самый существенный из которых - высокая сложность работы. Для SVD разложения необходимо совершить  <math>O(n^3) </math> действий.
+Исправить эту ошибку призван следующий подход. Будем рассматривать матрицы фиксированного ранга как гладкое риманово многообразие. К каждому элементу этого многообразия зададим касательное пространство. Перед тем, как вычесть градиент из текущего приближения, сначала спроектируем его на касательное пространство к текущему приближению. Благодаря этому матрица, полученная после совершения градиентного шага будет иметь ранг не выше <math>2r</math> (если считать, что исходный ранг был  <math>r </math>). Теперь от этой матрицы не сложно сделать SVD разложение, потому что она имеет небольшие размеры.
 === Математическое описание алгоритма ===
+<math>M</math> - матрица, известная нам только на заданном множестве индексов (по-сути мы знаем только <math> P_{\Omega}(M) </math>).
+Введем оператор <math>P_{\Omega}(X)_{i, j} = X_{i, j}</math> если <math>{i, j} \in \Omega</math>, иначе 0.
+Множество матриц с рангом r будем обозначать <math>M_r</math>, касательное пространство к матрице <math>X \in M_r</math> - <math>T_x M_r</math>.
+Введем так же проектор на касательное пространство.Пусть <math>X_i = U \Sigma V_T</math>. Тогда <math> P_{T_x M_r}(Z) = P_{U}ZP_{V} +  P_{U^\perp}ZP_{V} +  P_{U}ZP_{V^\perp}</math>.
+Запишем алгоритм:
+WHILE(<math> ||P_{\Omega}(X_{t} - M)|| \geq \varepsilon </math>) do
+<math>X_{t+1} = SVD(X_{t} - \alpha_t P_{T_x M_r} P_{\Omega}(X_{t} - M)) </math>
+end
 === Макроструктура алгоритма ===
@@ Строка 63: / Строка 86: @@
 == Литература ==
-[1]Guaranteed Rank Minimization via Singular Value Projection.Raghu Meka, Prateek Jain, Inderjit S. Dhillon // arXiv:0909.5457
+[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