Уровень алгоритма

Восполнение матриц с дополнительной информацией: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
(не показаны 4 промежуточные версии этого же участника)
Строка 12: Строка 12:
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Пусть <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>), то задача сводиться к задаче обычного восполнения матриц.
+
Пусть <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>.
 
Для решения этой задачи применяется итеративный метод 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>, а именно:
+
Нам известно, что <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%">
 
<table style="width:100%">
Строка 26: Строка 26:
 
<math>\Omega \subset [n_1] \times [n_2] - </math> множество известных нам индексов, а <math>\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X</math> - проектор на это множество.
 
<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>.
+
Пусть решением этой задачи является матрица <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%">
 
<table style="width:100%">
 
   <tr>
 
   <tr>
Строка 32: Строка 32:
 
   </tr>
 
   </tr>
 
</table>
 
</table>
Найдя формулу сопряженного оператора: <math>\mathcal{A^*}(X) = A^T \, \cP_{\Omega}(X)B </math> получим алгоритм:
+
где <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%">
 
<table style="width:100%">
 
   <tr>
 
   <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>
+
   <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>
 
   </tr>
 
</table>
 
</table>
Строка 88: Строка 90:
 
[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
+
[2] Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. M Xu, R Jin, ZH Zhou
  
 
[[en:Matrix completion]]
 
[[en:Matrix completion]]
  
[[Категория:Восстановление матриц]]
+
[[Категория:Восполнение матриц]]

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


Восстановление матриц
Последовательный алгоритм
Последовательная сложность $O(n^3)$
Объём входных данных [math]\frac{n (n + 1)}{2}[/math]
Объём выходных данных [math]\frac{n (n + 1)}{2}[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(n)[/math]
Ширина ярусно-параллельной формы [math]O(n^2)[/math]


Содержание

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

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

Пусть [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].

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

Нам известно, что [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] имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

[math]\min_{Z} f(Z) = \frac{1}{2} ||\mathcal{P}_{\Omega}(AZB^T - X)||^2_2, \; \; rank(Z) \leq r, \text{ где } [/math]

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

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

где [math]\mathcal{P}_r - [/math] проектор на множество матриц ранга не выше [math]r[/math] (SVD).

Найдя формулу сопряженного оператора: [math]\mathcal{A^*}(X) = A^T \, \mathcal{P}_{\Omega}(X)B [/math] получим алгоритм:

[math]Z_{t+1} = \mathcal{P}_r[Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZ_tB^T - X)B] [/math]

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] Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. M Xu, R Jin, ZH Zhou