Recovering Low-Rank Matrices From Few Coefficients in Any Basis

Abstract

We present novel techniques for analyzing the problem of low-rank matrix\nrecovery. The methods are both considerably simpler and more general than\nprevious approaches. It is shown that an unknown (n x n) matrix of rank r can\nbe efficiently reconstructed from only O(n r nu log^2 n) randomly sampled\nexpansion coefficients with respect to any given matrix basis. The number nu\nquantifies the "degree of incoherence" between the unknown matrix and the\nbasis. Existing work concentrated mostly on the problem of "matrix completion"\nwhere one aims to recover a low-rank matrix from randomly selected matrix\nelements. Our result covers this situation as a special case. The proof\nconsists of a series of relatively elementary steps, which stands in contrast\nto the highly involved methods previously employed to obtain comparable\nresults. In cases where bounds had been known before, our estimates are\nslightly tighter. We discuss operator bases which are incoherent to all\nlow-rank matrices simultaneously. For these bases, we show that O(n r nu log n)\nrandomly sampled expansion coefficients suffice to recover any low-rank matrix\nwith high probability. The latter bound is tight up to multiplicative\nconstants.\n

Affiliated Institutions

• Leibniz University Hannover DE
• ETH Zurich CH

Related Publications