Greedy sparsity-constrained optimization

Finding optimal sparse solutions to estimation problems, particularly in underdetermined regimes has recently gained much attention. Most existing literature study linear models in which the squared error is used as the measure of discrepancy to be minimized. However, in many applications discrepancy is measured in more general forms such as log-likelihood. Regularization by ℓ1-norm has been shown to induce sparse solutions, but their sparsity level can be merely suboptimal. In this paper we present a greedy algorithm, dubbed Gradient Support Pursuit (GraSP), for sparsity-constrained optimization. Quantifiable guarantees are provided for GraSP when cost functions have the “Stable Hessian Property”.

• Publication year

  2011

• Venue

  Asilomar Conference on Signals, Systems and Computers

• Publication date

  2011-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.5555/2567709.2502607arXiv 1203.5483
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sparse Recovery Algorithms: Sufficient Conditions in Terms of RestrictedIsometry Constants

  2012cited by this paper
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems

  2012cited by this paper
• Fast global convergence of gradient methods for high-dimensional statistical recovery

  2011cited by this paper
• On Learning Discrete Graphical Models using Greedy Methods

  2011influential reference
• Group Orthogonal Matching Pursuit for Logistic Regression

  2011influential reference
• Greedy Algorithms for Structurally Constrained High Dimensional Problems

  2011cited by this paper
• Regularization Paths for Generalized Linear Models via Coordinate Descent.

  2010cited by this paper
• The Convex Geometry of Linear Inverse Problems

  2010cited by this paper
• Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints

  2010cited by this paper
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP

  2010cited by this paper
• Compressed Sensing with Nonlinear Observations

  2010influential reference
• User-Friendly Tail Bounds for Sums of Random Matrices

  2010cited by this paper
• Fast global convergence rates of gradient methods for high-dimensional statistical recovery

  2010influential reference
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  2009cited by this paper
• Large-scale sparse logistic regression

  2009cited by this paper
• Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity

  2009influential reference
• Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing

  2009cited by this paper
• A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

  2009influential reference
• SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR

  2008cited by this paper
• Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

  2008cited by this paper
• Iterative Hard Thresholding for Compressed Sensing

  2008influential reference
• Honest variable selection in linear and logistic regression models via $\ell_1$ and $\ell_1+\ell_2$ penalization

  2008influential reference
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

  2008influential reference
• Compressed sensing and best k-term approximation

  2008cited by this paper
• HIGH-DIMENSIONAL GENERALIZED LINEAR MODELS AND THE LASSO

  2008influential reference
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

  2007cited by this paper
• Compressed sensing

  2006cited by this paper
• The elements of statistical learning: data mining, inference and prediction

  2005cited by this paper
• Stable signal recovery from incomplete and inaccurate measurements

  2005influential reference
• Result Analysis of the NIPS 2003 Feature Selection Challenge

  2004cited by this paper
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization

  2003cited by this paper
• An Introduction to Generalized Linear Models

  2002influential reference
• Uncertainty principles and ideal atomic decomposition

  2001cited by this paper
• Empirical Processes in M-Estimation

  2001cited by this paper
• Empirical Processes in M-Estimation

  2000cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• Statistical learning theory

  1998cited by this paper
• Sparse Approximate Solutions to Linear Systems

  1995cited by this paper
• Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

  1993influential reference
• Presented by?????

  year unknowncited by this paper

• Stability of Constrained Optimization Models for Structured Signal Recovery

  2026cites this paper
• Optimality Conditions for Sparse Bilinear Least Squares Problems

  2026cites this paper
• Deep tobit model: an integrated framework for high-dimensional censored regression with variable selection

  2026influential citation
• Pseudo-inverse-based hard thresholding pursuit algorithm with momentum: An innovative second-order method for sparse signal recovery

  2026cites this paper
• Iterative mix thresholding algorithm with continuation technique for mix sparse optimization and application

  2025cites this paper
• Foundations of Top-k Decoding For Language Models

  2025cites this paper
• Sparse Quadratically Constrained Quadratic Programming via Semismooth Newton Method

  2025cites this paper
• Unified sparse optimization via quantum architectures and hybrid techniques

  2025cites this paper
• Brief introduction in greedy approximation

  2025cites this paper
• Sparse Wasserstein Barycenters and Application to Reduced Order Modeling

  2025cites this paper
• Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization

  2024cites this paper
• skscope: Fast Sparsity-Constrained Optimization in Python

  2024cites this paper
• Fast Recursive Greedy Methods for Sparse Signal Recovery

  2024cites this paper
• Automatic Hypergraph Generation for Enhancing Recommendation With Sparse Optimization

  2024cites this paper
• Separable Bregman Framework for Sparsity Constrained Nonlinear Optimization

  2024cites this paper
• The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information

  2024cites this paper
• Approximation and Structured Prediction with Sparse Wasserstein Barycenters

  2023cites this paper
• A Greedy Newton-Type Method for Multiple Sparse Constraint Problem

  2023influential citation
• Group variable selection via group sparse neural network

  2023cites this paper
• Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique

  2023cites this paper
• Revisiting $L_q(0\leq q<1)$ Norm Regularized Optimization

  2023influential citation
• Clean processing for direct signal cancellation using sparse representation in passive synthetic Aperture Radar based on DVB-T Signal

  2023cites this paper
• A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models

  2023cites this paper
• Exponential Generalization Bounds with Near-Optimal Rates for $L_q$-Stable Algorithms

  2023cites this paper
• Learning Large Scale Sparse Models

  2023cites this paper
• Private Stochastic Convex Optimization and Sparse Learning with Heavy-tailed Data Revisited

  2022cites this paper
• Gradient Properties of Hard Thresholding Operator

  2022cites this paper
• Fast Feature Selection with Fairness Constraints

  2022cites this paper
• Fast Sparse Classification for Generalized Linear and Additive Models

  2022cites this paper
• Sparse least squares solutions of multilinear equations

  2022cites this paper
• Accelerated Projected Gradient Algorithms for Sparsity Constrained Optimization Problems

  2022cites this paper
• Convergence of the mini-batch SIHT algorithm

  2022cites this paper
• A globally convergent approximate Newton method for non-convex sparse learning

  2022cites this paper
• Gradient Projection Newton Pursuit for Sparsity Constrained Optimization

  2022influential citation
• Towards Lightweight Super-Resolution With Dual Regression Learning

  2022cites this paper
• Iterative Thresholding and Projection Algorithms and Model-Based Deep Neural Networks for Sparse LQR Control Design

  2022cites this paper
• Stability and Risk Bounds of Iterative Hard Thresholding

  2022influential citation
• A Local MM Subspace Method for Solving Constrained Variational Problems in Image Recovery

  2022cites this paper
• Stochastic privacy-preserving methods for nonconvex sparse learning

  2022cites this paper
• A nonlinear sparse neural ordinary differential equation model for multiple functional processes

  2021influential citation
• A Data-Driven Line Search Rule for Support Recovery in High-dimensional Data Analysis

  2021cites this paper
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data

  2021cites this paper
• Gradient projection Newton algorithm for sparse collaborative learning using synthetic and real datasets of applications

  2021cites this paper
• Cardinality Minimization, Constraints, and Regularization: A Survey

  2021cites this paper
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets

  2021cites this paper
• Subspace quadratic regularization method for group sparse multinomial logistic regression

  2021cites this paper
• Efficient Gradient Support Pursuit With Less Hard Thresholding for Cardinality-Constrained Learning

  2021influential citation
• Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence

  2021cites this paper
• Double fused Lasso regularized regression with both matrix and vector valued predictors

  2021influential citation
• Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective

  2021cites this paper
• Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method

  2021cites this paper
• Phase retrieval and design with automatic differentiation: tutorial

  2021cites this paper
• A majorization penalty method for SVM with sparse constraint

  2021cites this paper
• A Lagrange–Newton algorithm for sparse nonlinear programming

  2020cites this paper
• Newton method for ℓ0-regularized optimization

  2020cites this paper
• Statistical Computational Learning

  2020cites this paper
• Pruning Deep Convolutional Neural Networks via Gradient Support Pursuit

  2020cites this paper
• A Gradient Projection Algorithm with a New Stepsize for Nonnegative Sparsity-Constrained Optimization

  2020cites this paper
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint

  2020cites this paper
• Nonlinear Variable Selection via Deep Neural Networks

  2020influential citation
• Weighted thresholding homotopy method for sparsity constrained optimization

  2020influential citation
• Subspace Newton method for the $\ell_0$-regularized optimization

  2020cites this paper
• Stochastic Recursive Gradient Support Pursuit and Its Sparse Representation Applications

  2020influential citation
• Greedy Projected Gradient-Newton Method for Sparse Logistic Regression

  2020influential citation
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

  2020cites this paper
• Sparsifying Dictionary Learning for Beamspace Channel Representation and Estimation in Millimeter-Wave Massive MIMO

  2020cites this paper
• Bayesian Coresets: An Optimization Perspective

  2020cites this paper
• Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding

  2020cites this paper
• Discrimination-Aware Network Pruning for Deep Model Compression

  2020cites this paper
• Generalized greedy alternatives

  2020influential citation
• Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

  2020influential citation
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions

  2020cites this paper
• Dual Iterative Hard Thresholding

  2020influential citation
• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery

  2020cites this paper
• Model-Free Optimal Control of Linear Multiagent Systems via Decomposition and Hierarchical Approximation

  2020cites this paper
• Federated Nonconvex Sparse Learning

  2020cites this paper
• A Survey on Compressive Sensing: Classical Results and Recent Advancements

  2019cites this paper
• Game-Theoretic Mixed H2/H∞ Control with Sparsity Constraint for Multi-agent Networked Control Systems

  2019cites this paper
• Gradient Pursuit-Based Channel Estimation for MmWave Massive MIMO Systems with One-Bit ADCs

  2019influential citation
• Analysis of stress-strain states of casting crane traverse

  2019cites this paper
• Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit

  2019influential citation
• Fast Newton Method for Sparse Logistic Regression

  2019influential citation
• An extended Newton-type algorithm for ℓ2-regularized sparse logistic regression and its efficiency for classifying large-scale datasets

  2019influential citation
• Channel estimation via gradient pursuit for mmWave massive MIMO systems with one-bit ADCs

  2019cites this paper
• Model Reduction for Interactive Geometry Processing

  2019cites this paper
• Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning

  2019cites this paper
• Exact Support and Vector Recovery of Constrained Sparse Vectors via Constrained Matching Pursuit

  2019influential citation
• Getting Started with RapidMiner

  2019cites this paper
• Loopless Semi-Stochastic Gradient Descent with Less Hard Thresholding for Sparse Learning

  2019cites this paper
• OpenMendel: a cooperative programming project for statistical genetics

  2019cites this paper
• Quadratic Approximation Greedy Pursuit for Cardinality-Constrained Sparse Learning

  2019cites this paper
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization

  2019influential citation
• Optimality Conditions for Rank-Constrained Matrix Optimization

  2019cites this paper
• On Sparse Linear Regression in the Local Differential Privacy Model

  2019cites this paper
• Provable convergence for accelerated Iterative Hard Thresholding

  2019cites this paper
• Optimality Conditions for Rank-Constrained Matrix Optimization

  2019cites this paper
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization

  2019cites this paper
• Efficient projected gradient methods for cardinality constrained optimization

  2018cites this paper
• Frontiers of Multimedia Research

  2018cites this paper
• Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery

  2018cites this paper