Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate
This paper is concerned with low-rank matrix optimization, which has found a wide range of applications in machine learning. This problem in the special case of matrix sensing has been studied extensively through the notion of Restricted Isometry Property (RIP), leading to a wealth of results on the geometric landscape of the problem and the convergence rate of common algorithms. However, the existing results can handle the problem in the case with a general objective function subject to noisy data only when the RIP constant is close to 0. In this paper, we develop a new mathematical framework to solve the above-mentioned problem with a far less restrictive RIP constant. We prove that as long as the RIP constant of the noiseless objective is less than $1/3$, any spurious local solution of the noisy optimization problem must be close to the ground truth solution. By working through the strict saddle property, we also show that an approximate solution can be found in polynomial time. We characterize the geometry of the spurious local minima of the problem in a local region around the ground truth in the case when the RIP constant is greater than $1/3$. Compared to the existing results in the literature, this paper offers the strongest RIP bound and provides a complete theoretical analysis on the global and local optimization landscapes of general low-rank optimization problems under random corruptions from any finite-variance family.
Code (1)
Similar Papers 제목 키워드 기반
Parameter Estimation for Generalized Low-Rank Matrix Sensing by Learning on Riemannian Manifolds
We prove convergence guarantees for generalized low-rank matrix sensing -- i.e., where matrix sensing where the observations may be passed through some nonlinear link function. We focus on local convergence of the optima…
parameter estimationCan Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?
We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a $d_1\times d_2$ matrix $X^\star$ with rank $r$ from $m$ linear measurements, some potentially noisy. When the noise is distributed …
Matrix CompletionGuaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold
Recovering a low-CP-rank tensor from noisy linear measurements is a central challenge in high-dimensional data analysis, with applications spanning tensor PCA, tensor regression, and beyond. We exploit the intrinsic geom…
Guaranteed Matrix Completion via Non-convex Factorization
Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice. However, due to …
Matrix Completion1-Bit Matrix Completion under Exact Low-Rank Constraint
We consider the problem of noisy 1-bit matrix completion under an exact rank constraint on the true underlying matrix $M^*$. Instead of observing a subset of the noisy continuous-valued entries of a matrix $M^*$, we obse…
Matrix Completion