Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications

Abstract

The problem of finding the sparsest vector (direction) in a low dimensional subspace can be considered as a homogeneous variant of the sparse recovery problem, which finds applications in robust subspace recovery, dictionary learning, sparse blind deconvolution, and many other problems in signal processing and machine learning. However, in contrast to the classical sparse recovery problem, the most natural formulation for finding the sparsest vector in a subspace is usually nonconvex. In this paper, we overview recent advances on global nonconvex optimization theory for solving this problem, ranging from geometric analysis of its optimization landscapes, to efficient optimization algorithms for solving the associated nonconvex optimization problem, to applications in machine intelligence, representation learning, and imaging sciences. Finally, we conclude this review by pointing out several interesting open problems for future research.

QQ and ZZ contributed equally to the work. Invited review paper for IEEE Signal Processing Magazine Special Issue on non-convex optimization for signal processing and machine learning. This article contains 26 pages with 11 figures

References in corpus (26)

• Fast non-negative deconvolution for spike train inference from population calcium imaging
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Guaranteed Matrix Completion via Non-convex Factorization
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• An Overview of Robust Subspace Recovery
• When Are Nonconvex Problems Not Scary?
• A Novel M-Estimator for Robust PCA
• Complete Dictionary Recovery over the Sphere
• A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
• Escaping from saddle points on Riemannian manifolds
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Hyperplane Clustering Via Dual Principal Component Pursuit
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms
• A Brief Introduction to Manifold Optimization

Cited by in corpus (6)

• A Geometric Analysis of Neural Collapse with Unconstrained Features
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Optimal Spectral Recovery of a Planted Vector in a Subspace
• Convolutional Normalization: Improving Deep Convolutional Network Robustness and Training
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation