A Well-Tempered Landscape for Non-convex Robust Subspace Recovery

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).

58 pages, 6 figures, 1 table

References in corpus (6)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• An Overview of Robust Subspace Recovery
• Non-convex Robust PCA
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• RANSAC Algorithms for Subspace Recovery and Subspace Clustering
• The Grassmannian of affine subspaces

Cited by in corpus (8)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• An Overview of Robust 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 $\mathrm{SO}(D)$