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

Восстановление матриц
Последовательный алгоритм
Последовательная сложность	$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 \ms{n_1}{n_2} - }[/math] неизвестная малоранговая матрица. Нашей целью является восполнение матрицы [math]\displaystyle{ X }[/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