Nonconvex methods achieve near optimal matrix recovery from few samples
Near-Optimal Nonconvex Matrix Completion
Machine Learning
Summary
Filling in missing parts of large grids of numbers, known as matrix completion, helps in many tasks like recommendation systems. The authors looked at faster methods that don’t use complex math but still need more samples than ideal. They improved these methods by showing they can recover the full matrix with nearly the fewest samples possible. Their approach speeds up recovery and guarantees precise results with high chance.
What this means in practice
- •For data engineers: Efficiently reconstruct user preference matrices from limited observed entries to enhance recommendation systems using faster nonconvex optimization methods.
- •For signal processing teams: Improve signal recovery from incomplete measurements by applying near-optimal low-rank matrix reconstruction techniques from fewer observations.
Authors
Jian-Feng Cai, Xiliang Lu, Juntao You
Abstract
We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.