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

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

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

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

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

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

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

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

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