Matrix Completion and Related Problems via Strong Duality
arXiv:1704.08683
Abstract
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and show that under certain dual conditions, the optimal solution of the matrix factorization program is the same as its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization problems are hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly. We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis (PCA). These are examples of efficiently recovering a hidden matrix given limited reliable observations of it. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity guarantees for matrix completion and robust PCA.
37 pages, 4 figures
References in corpus (10)
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- How to Escape Saddle Points Efficiently
- Matrix Completion has No Spurious Local Minimum
- Fast Algorithms for Robust PCA via Gradient Descent
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Convex Sparse Matrix Factorizations
- Fast matrix completion without the condition number
- Deep Learning without Poor Local Minima
- Matrix Completion from Samples in Linear Time
- A Unified Framework for Low-Rank plus Sparse Matrix Recovery