Алговики - Вклад [ru]

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

2021-10-26T18:55:41Z

Мордвинцев Михаил: /* Математическое описание алгоритма */

{{algorithm
| name = Восстановление матриц с использованием оптимизации на римановых многообразиях
| serial_complexity = <math>O(|\Omega|r^2)</math>
| pf_height = <math>const</math>
| pf_width = <math>const</math>
| input_data = <math>|\Omega|</math>
| output_data = <math>2nr</math>
}}

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

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

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

Будем оптимизировать норму ошибки на известных элементах с помощью аналога градиентного спуска. После каждого шага будем возвращаться в множество матриц фиксированного ранга, так же как и в случае обычного градиентного спуска (проектором может служить, например, 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

[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

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]

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

2021-10-26T18:27:45Z

Мордвинцев Михаил:

{{algorithm
| name = Восстановление матриц с использованием оптимизации на римановых многообразиях
| serial_complexity = <math>O(|\Omega|r^2)</math>
| pf_height = <math>const</math>
| pf_width = <math>const</math>
| input_data = <math>|\Omega|</math>
| output_data = <math>2nr</math>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

[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

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]

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

2021-10-26T18:26:18Z

Мордвинцев Михаил: /* Общее описание алгоритма */

{{algorithm
| name = Восстановление матриц
| serial_complexity = <math>O(|\Omega|r^2)</math>
| pf_height = <math>const</math>
| pf_width = <math>const</math>
| input_data = <math>|\Omega|</math>
| output_data = <math>2nr</math>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

[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

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]

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

2021-10-26T18:04:23Z

Мордвинцев Михаил:

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

2021-10-26T18:03:30Z

Мордвинцев Михаил:

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

2021-10-26T17:59:26Z

Мордвинцев Михаил: /* Литература */

{{algorithm
| name = Восстановление матриц
| serial_complexity = <math>O(n^3)</math>
| pf_height = <math>O(n)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n (n + 1)}{2}</math>
| output_data = <math>\frac{n (n + 1)}{2}</math>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

[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

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]

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

2021-10-26T17:58:52Z

Мордвинцев Михаил: /* Литература */

{{algorithm
| name = Восстановление матриц
| serial_complexity = <math>O(n^3)</math>
| pf_height = <math>O(n)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n (n + 1)}{2}</math>
| output_data = <math>\frac{n (n + 1)}{2}</math>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

[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

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]

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

2021-10-21T16:23:53Z

Мордвинцев Михаил: Новая страница: «{{algorithm | name = Восстановление матриц | serial_complexity = <math>O(n^3)</math> | pf_height = <math>O(n)</math> | pf...»

{{algorithm
| name = Восстановление матриц
| serial_complexity = <math>O(n^3)</math>
| pf_height = <math>O(n)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n (n + 1)}{2}</math>
| output_data = <math>\frac{n (n + 1)}{2}</math>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

<references \>

[[en:Matrix completion]]

[[Категория:Восстановление матриц]]