Optimization Algorithms on Subspaces: Revisiting Missing Data Problem in Low-Rank Matrix

Abstract Low-rank matrix approximation has applications in many fields, such as 3D reconstruction from an image se-quence and 2D filter design. In this paper, one issue with low-rank matrix approximation is re-investigated: the miss-ing data problem. Much effort was devoted to this prob-lem, and the Wiberg algorithm or the damped Newton algo-rithm were recommended in previous studies. However, the Wiberg or damped Newton algorithms do not suit for large (especially “long”) matrices, because one needs to solve a large linear system in every iteration. In this paper, we revi-talize the usage of the Levenberg-Marquardt algorithm for solving the missing data problem, by utilizing the prop-erty that low-rank approximation is a minimization prob-lem on subspaces. In two proposed implementations of the Levenberg-Marquardt algorithm, one only needs to solve a much smaller linear system in every iteration, especially for “long ” matrices. Simulations and experiments on real data show the superiority of the proposed algorithms. Though the proposed algorithms achieve a high success rate in estimat-ing the optimal solution by random initialization, as illus-trated by real examples; it still remains an open issue how to properly do the initialization in a severe situation (that is, a large amount of data is missing and with high-level noise)