Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
This work addresses matrix completion and kernel PCA for machine learning applications, offering incremental improvements in theoretical guarantees and stability.
The paper tackles low-rank approximation of positive semidefinite matrices from partial entries via nonconvex optimization, characterizing local minima without assumptions on rank-matching or condition numbers, and applies it to memory-efficient Kernel PCA, showing more stable results than Nyström methods in experiments.
This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positive semidefinite matrix without any assumptions on the rank-matching, the condition number or eigenspace incoherence parameter. Furthermore, under certain assumptions on rank-matching and well-boundedness of condition numbers and eigenspace incoherence parameters, a corollary of our main theorem improves the state-of-the-art sampling rate results for nonconvex matrix completion with no spurious local minima in Ge et al. [2016, 2017]. In addition, we investigated when the proposed nonconvex optimization results in accurate low-rank approximations even in presence of large condition numbers, large incoherence parameters, or rank mismatching. We also propose to apply the nonconvex optimization to memory-efficient Kernel PCA. Compared to the well-known Nyström methods, numerical experiments indicate that the proposed nonconvex optimization approach yields more stable results in both low-rank approximation and clustering.