Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints

2014/07/01 by Nam H. Nguyen, Nguyen, Nam, Deanna Needell +3 · 3 citations
Computer Science · Engineering · #41A46 #52A99 #60G99 #62L20 #65B99 #68Q25 #68W20 #90C27 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1407.0088

openalex publication_date 2014/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.

Citations

• Large-Scale Convex Minimization with a Low-Rank Constraint
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Stable signal recovery from incomplete and inaccurate measurements
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Decoding by Linear Programming
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized\n Kaczmarz algorithm
• Iterative hard thresholding for compressed sensing

Cited by

• Normalized Iterative Hard Thresholding for Tensor Recovery
• On The Projection Operator to A Three-view Cardinality Constrained Set
• WeightLoRA: Keep Only Necessary Adapters

Related

• A New Analysis of Compressive Sensing by Stochastic Proximal Gradient Descent
• Sparse recovery by reduced variance stochastic approximation
• Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Approximate and Stochastic Greedy Optimization