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

Восстановление матриц
Последовательный алгоритм
Последовательная сложность	$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 = 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\

\]

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