Алгоритм дополнения матриц

Восстановление матриц
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(|\Omega|r^2) }[/math]
Объём входных данных	[math]\displaystyle{ |\Omega| }[/math]
Объём выходных данных	[math]\displaystyle{ 2nr }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ const }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ const }[/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