Restricted strong convexity and weighted matrix completion: Optimal bounds with noise - Computer Science > Information Theory

Abstract: We consider the matrix completion problem under a form of row-column weightedentrywise sampling, including the case of uniform entrywise sampling as aspecial case. We analyze the associated random observation operator, and provethat with high probability, it satisfies a form of restricted strong convexitywith respect to weighted Frobenius norm. Using this property, we obtain ascorollaries a number of error bounds on matrix completion in the weightedFrobenius norm under noisy sampling and for both exact and near low-rankmatrices. Our results are based on measures of the -spikiness- and-low-rankness- of matrices that are less restrictive than the incoherenceconditions imposed in previous work. Our technique involves an $M$-estimatorthat includes controls on both the rank and spikiness of the solution, and weestablish non-asymptotic error bounds in weighted Frobenius norm for recoveringmatrices lying with $\ell q$-balls- of bounded spikiness. Usinginformation-theoretic methods, we show that no algorithm can achieve betterestimates up to a logarithmic factor over these same sets, showing that ourconditions on matrices and associated rates are essentially optimal.

Author: Sahand Negahban, Martin J. Wainwright

Source: https://arxiv.org/