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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ 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]\displaystyle{ \mathcal{P}_r - }[/math] проектор на множество матриц ранга не выше [math]\displaystyle{ r }[/math] (SVD). Найдя формулу сопряженного оператора: [math]\displaystyle{ \mathcal{A^*}(X) = A^T \, mathcal{P}_{\Omega}(X)B }[/math] получим алгоритм:

[math]\displaystyle{ Z_{t+1} = \mathcal{P}_r(Z_{t} - \eta_t A^T\mathcal{P}_{\Omega}(AZB^T - X)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