MC2: a two-phase algorithm for leveraged matrix completion

DOI10.1093/IMAIAI/IAX020MaRDI QIDQ5242856zbMATH OpenOpenAlexFDO

Authors Armin Eftekhari, Michael B. Wakin, Rachel Ward

Publication date 7 November 2019

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01795

zbMATH Keywords

coherenceleverage scoresmatrix completionnuclear norm minimization

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Analysis of algorithms (68W40)

Abstract: Leverage scores, loosely speaking, reflect the importance of the rows and columns of a matrix. Ideally, given the leverage scores of a rank-$r$ matrix $Minmathbb{R}^{nimesn}$, that matrix can be reliably completed from just $O(rnlo{g}^{2}n)$ samples if the samples are chosen randomly from a nonuniform distribution induced by the leverage scores. In practice, however, the leverage scores are often unknown a priori. As such, the sample complexity in uniform matrix completion---using uniform random sampling---increases to $O(eta(M)cdotrnlo{g}^{2}n)$, where $eta(M)$ is the largest leverage score of $M$. In this paper, we propose a two-phase algorithm called MC${}^2$ for matrix completion: in the first phase, the leverage scores are estimated based on uniform random samples, and then in the second phase the matrix is resampled nonuniformly based on the estimated leverage scores and then completed. For well-conditioned matrices, the total sample complexity of MC${}^2$ is no worse than uniform matrix completion, and for certain classes of well-conditioned matrices---namely, reasonably coherent matrices whose leverage scores exhibit mild decay---MC${}^2$ requires substantially fewer samples. Numerical simulations suggest that the algorithm outperforms uniform matrix completion in a broad class of matrices, and in particular, is much less sensitive to the condition number than our theory currently requires.

Recommendations

• A two-phase rank-based algorithm for low-rank matrix completion
• Relaxed leverage sampling for low-rank matrix completion
• Some empirical advances in matrix completion
• Matrix completion via an alternating direction method
• Matrix completion via minimizing an approximate rank
• An alternating minimization method for matrix completion problems
• scientific article; zbMATH DE number 7306912
• Matrix completion via max-norm constrained optimization
• Matrix Completion With Column Manipulation: Near-Optimal Sample-Robustness-Rank Tradeoffs

Cited in

(3)

• Relaxed leverage sampling for low-rank matrix completion
• Streaming principal component analysis from incomplete data
• Randomized approach to matrix completion: applications in recommendation systems and image inpainting

This page was built for publication: MC2: a two-phase algorithm for leveraged matrix completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5242856)