Приближенные алгоритмы малоранговой аппроксимации в задаче восполнения матрицы на случайном шаблоне

Изучается возможность ускорения алгоритма проектирования на старшие сингулярные пространства в задаче “восполнения” матрицы малого ранга по небольшому числу ее элементов. Идея работы состоит в замене процедуры поиска наилучшего приближения во фробениусовой норме на быстрые приближенные алгоритмы. Рассматриваются два метода вычисления таких приближенний: (а) проектирование на случайные подпространства; (б) метод крестовой аппроксимации. Доказаны теоремы о геометрической сходимости алгоритмов с приближенными проекциями. Проведены численные эксперименты, показывающие эффективность обоих вариантов по сравнению с точной проекцией.
Библ. 18. Фиг. 4.