Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
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\"{o}m methods, numerical experiments indicate that the proposed nonconvex optimization approach yields more stable results in both low-rank approximation and clustering.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringDimensionality ReductionMatrix CompletionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for…
Matrix CompletionA Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery
We propose a primal-dual based framework for analyzing the global optimality of nonconvex low-rank matrix recovery. Our analysis are based on the restricted strongly convex and smooth conditions, which can be verifi…
Matrix CompletionNonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonco…
Matrix CompletionRetrievalNonconvex Matrix Completion with Linearly Parameterized Factors
Techniques of matrix completion aim to impute a large portion of missing entries in a data matrix through a small portion of observed ones. In practice including collaborative filtering, prior information and special str…
Collaborative FilteringMatrix CompletionMatrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
Matrix completion has attracted much interest in the past decade in machine learning and computer vision. For low-rank promotion in matrix completion, the nuclear norm penalty is convenient due to its convexity but has a…
Matrix Completion