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

Восполнение матриц с дополнительной информацией

2021-10-26T20:36:54Z

Михайлов Арсений: /* Литература */

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому их набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>, тогда <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> ортонормированные матрицы базисов этих пространств, соответственно. Для матрицы <math>X</math> существует представление: <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будем с помощью алгоритма SVP с оператором <math>\mathcal{A}(Z) = \mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).

Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[2] Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. M Xu, R Jin, ZH Zhou

[[en:Matrix completion]]

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

Восполнение матриц с дополнительной информацией

2021-10-26T20:32:19Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому их набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>, тогда <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> ортонормированные матрицы базисов этих пространств, соответственно. Для матрицы <math>X</math> существует представление: <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будем с помощью алгоритма SVP с оператором <math>\mathcal{A}(Z) = \mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).

Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:30:38Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>, тогда <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> ортонормированные матрицы базисов этих пространств, соответственно. Для матрицы <math>X</math> существует представление: <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будем с помощью алгоритма SVP с оператором <math>\mathcal{A}(Z) = \mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).

Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:23:33Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будет с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).

Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:21:20Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будет с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
где <math>\mathcal{P}_r - </math> проектор на множество матриц ранга не выше <math>r</math> (SVD).
Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, mathcal{P}_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZB^T - X)B, </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:16:56Z

Михайлов Арсений: /* Свойства и структура алгоритма */

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будет с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>
Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \cP_{\Omega}(X)B </math> получим алгоритм:
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZB^T - X)B, </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:11:56Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Пусть решением этой задачи является матрица <math>\tilde Z</math>. Тогда построим матрицу <math>\tilde X = A \tilde ZB^T</math>. Матрица <math>\tilde X</math> и будем задачи матричного восполнения. Минимизировать этот функционал будет с помощью алгоритма SVP с оператором <math>\mathcal{P}_\Omega(AZB^T)</math>.
<table style="width:100%">
<tr>
<td align="center" width="90%"><math>Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t \nabla f(Z_{t})) = \mathcal{P}_r(Z_{t} - \eta_t \mathcal{A^*}(\mathcal{A}(Z_{t}) - b)), </math></td>
</tr>
</table>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T20:02:49Z

Михайлов Арсений: /* Свойства и структура алгоритма */

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<table style="width:100%">
<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } </math></td>
</tr>
</table>
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega} = \mathds{1}[(i, j) \in \Omega] \circ X</math> - проектор на это множество.

Эта задача эквивалента задачи восполнения <math>X</math>, если <math>X</math> единственная матрица ранга не выше <math>r</math>, для которой \mathcal{P}_{\Omega}(X) совпадает с известными нам элементами, и для которой столбцы и строки лежат в <math>L_A</math> и <math>L_B</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-26T19:45:25Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<tr>
<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r\</math></td>
</tr>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T19:43:56Z

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

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

<td align="center" width="90%"><math>\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r\</math></td>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T19:38:57Z

Михайлов Арсений: /* Свойства и структура алгоритма */

{{algorithm
| name = Восстановление матриц
| serial_complexity = $O(n^3)$
| 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>
}}

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

=== Общее описание алгоритма ===
Пусть <math>X \in \mathbb{R}^{n_1 \times n_2} - </math> неизвестная малоранговая матрица. Нашей целью является восполнение матрицы <math>X</math>, то есть нахождение всех её элементов, по некоторому малому набору и дополнительной информации. Под дополнительной информацией понимаются линейные пространства <math>L_A</math> и <math>L_B</math>, содержащие столбцы и строки матрицы <math>X</math> соответственно. Если <math>L_A</math> и <math>L_B</math> тривиальные (то есть совпадают с <math>\mathbb{R}^{n_1}</math> и <math>\mathbb{R}^{n_2}</math>), то задача сводиться к задаче обычного восполнения матриц.

Для решения этой задачи применяется итеративный метод SVPWS, который является глубокой модификацией метода SVP. На каждой итерации мы будем делать градиентный шаг и проектироваться обратно на множество матриц малого ранга (с помощью SVD), получая тем самым очередное приближение к исходной неизвестной матрице <math>X</math>.

=== Математическое описание алгоритма ===
Нам известно, что <math>Im(X) \subset L_A, \ Im(X^T) \subset L_B </math>. Пусть <math>dim(L_A) = s_1, \ dim (L_B) = s_2</math>. Зададим ортонормированные матрицы <math>A \in \mathbb{R}^{n_1 \times s_1}</math> и <math>B \in \mathbb{R}^{n_2 \times s_2}</math> <math>-</math> базисы этих пространств, соответственно. Тогда <math>X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}</math>. Матрицы <math>X</math> и <math>Z</math> имеют взаимно однозначное соответствие, а матрица <math>Z</math> имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для матрицы <math>Z</math>, а именно:

\[\label{pr:Z}
\min_{Z} f(Z) = \frac{1}{2} ||\cPo(AZB^T - X)||^2_2, \; \; rank(Z) \leq r\
\]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-26T19:33:34Z

Михайлов Арсений: /* Свойства и структура алгоритма */

Восполнение матриц с дополнительной информацией

2021-10-26T19:27:39Z

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

Восполнение матриц с дополнительной информацией

2021-10-26T19:16:27Z

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

Восполнение матриц с дополнительной информацией

2021-10-26T19:06:40Z

Михайлов Арсений:

Восполнение матриц с дополнительной информацией

2021-10-26T18:57:23Z

Михайлов Арсений:

Восполнение матриц с дополнительной информацией

2021-10-26T18:04:45Z

Михайлов Арсений:

Восполнение матриц с дополнительной информацией

2021-10-26T18:04:03Z

Михайлов Арсений: Новая страница: «{{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>
}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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]]

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