Near-Optimal Weighted Matrix Completion
share
Recent work in the matrix completion literature has shown that prior knowledge of a matrix's row and column spaces can be successfully incorporated into reconstruction programs to substantially benefit matrix recovery. This paper proposes a general methodology related to many of these approaches, while introducing novel methods that exploit matrix structure to severely reduce the sampling complexity. The main result shows that a family of weighted nuclear norm minimization programs incorporating a γ r-dimensional subspace of n× n matrices (where 1 ≤γ≤ n) allow accurate approximation of a rank r matrix lying in the subspace from a near-optimal number of randomly observed entries (within a logarithmic factor of γ r log(n)). The result is robust, where the error is proportional to measurement noise, applies to full rank matrices, and reflects degraded output when erroneous subspaces are incorporated. Experiments are presented to explore and compare several of the weighted approaches numerically.
READ FULL TEXT