Universal Matrix Completion

By Srinadh Bhojanapalli, Prateek Jain. 2014

106 citations recorded by the source corpus.

The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled afresh. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties. Moreover, we also show that under certain stricter incoherence conditions, $O(nr^2)$ uniformly sampled entries are enough to recover any rank-$r$ $n\times n$ matrix, in contrast to the $O(nr\log n)$ sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Optimization, Numerical Methods & Scientific Computing, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Optimization

In Numerical Methods & Scientific Computing

In Signal Processing

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “The full details are included in the appendix.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “We will establish a local geometrical property of a regularized objective such that any stationary point in a local region is globally optimal.”
Non-convex Optimization for Machine Learning (2017, background): “…of the condition number of the problem [Hardt and Wootters, 2014, Jain and Netrapalli, 2015], designing universal sampling schemes for recovery [Bhojanapalli and Jain, 2014], as well as tackling settings where some of the revealed entries of the matrix may be corrupted [Chen et al., 2016,…”
Optimum Co-Design for Spectrum Sharing between Matrix Completion Based MIMO Radars and a MIMO Communication System (2015, background): “One good candidate for Ω0 would be a uniformly random sampling matrix, as such matrix exhibit large spectral gap with high probability [34].”