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

Восстановление матриц
Последовательный алгоритм
Последовательная сложность	$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$ существует представление: $X = AZB^T, Z \in \mathbb{R}^{s_1 \times s_2}$. Матрицы $X$ и $Z$ имеют взаимно однозначное соответствие, а матрица $Z$ имеет существенно меньшие размеры, поэтому мы будет решать некоторую оптимизационную задачу для неё:

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

$\Omega \subset [n_1] \times [n_2] -$ множество известных нам индексов, а $\mathcal{P}_{\Omega}(X) = 1[(i, j) \in \Omega] \circ X$ - проектор на это множество.

Пусть решением этой задачи является матрица $\tilde Z$. Тогда построим матрицу $\tilde X = A \tilde ZB^T$. Матрица $\tilde X$ и будем задачи матричного восполнения. Минимизировать этот функционал будем с помощью алгоритма SVP с оператором $\mathcal{A}(Z) = \mathcal{P}_\Omega(AZB^T)$.

$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)),$

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

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

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

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