A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
arXiv:1706.03896
Abstract
We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).
arXiv comment58 pages, 6 figures, 1 table
References in corpus (17)
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- A geometric analysis of subspace clustering with outliers
- Geometric median and robust estimation in Banach spaces
- Nonconvex phase synchronization
- Median K-flats for hybrid linear modeling with many outliers
- Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
- An Overview of Robust Subspace Recovery
- Non-convex Robust PCA
- When Are Nonconvex Problems Not Scary?
- A Novel M-Estimator for Robust PCA
- Spectral clustering based on local linear approximations
- On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
- Fast, Robust and Non-convex Subspace Recovery
- Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
- lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
- RANSAC Algorithms for Subspace Recovery and Subspace Clustering
- The Grassmannian of affine subspaces
Cited by in corpus (9)
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- An Overview of Robust Subspace Recovery
- Fast, Robust and Non-convex Subspace Recovery
- Robust Subspace Recovery Layer for Unsupervised Anomaly Detection
- Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning
- Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
- Novelty Detection via Robust Variational Autoencoding
- Maximizing robustness of point-set registration by leveraging non-convexity
- Depth Descent Synchronization in