Sparse Approximate Solutions to Linear Systems

1995/04/01 by B. K. Natarajan · 2,832 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Geometry #Greedy algorithm #Inverse #Mathematics #Matrix (chemical analysis) #Norm (philosophy) #Row #Row and column spaces #Sparse and Compressive Sensing Techniques #Zero (linguistics)

paper · doi:10.1137/s0097539792240406

published in SIAM Journal on Computing 24(2), 227-234 (Society for Industrial and Applied Mathematics)

openalex publication_date 1995/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The following problem is considered: given a matrix A in \bf R^{m× n}, (m rows and n columns), a vector b in \bf R^m, and ε > 0, compute a vector x satisfying ‖Ax - b‖₂ ≤ ε if such exists, such that x has the fewest number of non-zero entries over all such vectors. It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most \lceil 18 Opt(ε/2)‖\bf A⁺‖₂² ln (‖ b ‖₂/ε)\rceil non-zero entries, where Opt(ε/2) is the optimum number of nonzero entries at error ε/2, A is the matrix obtained by normalizing each column of A with respect to the L₂ norm, and A⁺ is its pseudo-inverse.

Citations

• Approximation algorithms for combinatorial problems

Cited by

• Sparse Approximation by Semidefinite Programming
• Spatial Angular Pseudo-Derivative Search Algorithm: A Real-Time Single-Snapshot Super-Resolution Sparse DOA Scheme for Automotive Radar
• DataRater: Meta-Learned Dataset Curation
• From superposition to sparse codes: interpretable representations in neural networks
• Sparse System Identification in Pairs of FIR and TM Bases
• Randomized LU decomposition: An Algorithm for Dictionaries Construction
• Complexity of Unconstrained L₂-L_p Minimization
• Nonconvex fraction function recovery sparse signal by convex optimization algorithm
• Stepwise regression for unsupervised learning
• A general framework of rotational sparse approximation in uncertainty quantification
• Sparse Vector Recovery: Bernoulli-Gaussian Message Passing
• Image interpolation using Shearlet based iterative refinement
• Segment-Sliding Reconstruction of Pulsed Radar Echoes with Sub-Nyquist Sampling
• CLOT Norm Minimization for Continuous Hands-off Control
• Modified Frame Reconstruction Algorithm for Compressive Sensing
• A Cyclic Coordinate Descent Algorithm for lq Regularization
• Large-Scale Convex Minimization with a Low-Rank Constraint
• Variable Selection is Hard
• Stochastic collocation methods via minimization of Transformed L₁ penalty
• On-Off Random Access Channels: A Compressed Sensing Framework
• Perfect reconstruction of sparse signals using nonconvexity control and one-step RSB message passing
• Fast 2DGS: Efficient Image Representation with Deep Gaussian Prior
• Fast L1-L2 minimization via a proximal operator
• Optimal Solutions for Sparse Principal Component Analysis
• Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• Communication-Aware Dissipative Control for Networks of Heterogeneous Nonlinear Agents
• Dictionary Learning Phase Retrieval from Noisy Diffraction Patterns
• Effective sparse representation of X-Ray medical images
• From Cantilevers to Membranes: Advanced Scanning Protocols for Magnetic Resonance Force Microscopy
• Convex Relaxations for Subset Selection
• Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
• Minimization of the q-ratio sparsity with 1 < q ≤ ∞ for signal recovery
• Optimization landscape of ℓ₀-Bregman relaxations
• Sparse Linear Regression is Easy on Random Supports
• Sparsity via Hyperpriors: A Theoretical and Algorithmic Study under Empirical Bayes Framework
• Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training
• Atomic norm denoising with applications to line spectral estimation
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
• The Fine-Grained Hardness of Sparse Linear Regression
• A Unifying Framework for Sparsity Constrained Optimization
• A Minimum Description Length Approach to Multitask Feature Selection
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Atomic Norm Denoising With Applications to Line Spectral Estimation
• An iterative support shrinking algorithm for \ℓ_p-\ℓ_q\n minimization
• Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations
• The road to deterministic matrices with the restricted isometry property
• Ideal formulations for constrained convex optimization problems with indicator variables
• Fluorescence image deconvolution microscopy via generative adversarial learning (FluoGAN)
• Identifying Small Mean Reverting Portfolios
• Differentiable Causal Discovery Under Unmeasured Confounding
• Can Machine Learning Identify Governing Laws For Dynamics in Complex Engineered Systems ? : A Study in Chemical Engineering
• LASSO Methods for Gaussian Instrumental Variables Models
• Model compression as constrained optimization, with application to neural nets. Part I: general framework
• An Iteratively Reweighted Algorithm for Sparse Reconstruction of Subsurface Flow Properties from Nonlinear Dynamic Data
• Feature Gradients: Scalable Feature Selection via Discrete Relaxation
• Random projections for linear programming
• Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Distributionally Robust Feature Selection
• A Convexly Constrained LiGME Model and Its Proximal Splitting Algorithm
• Communication-Efficient Algorithms For Distributed Optimization
• Constrained Machine Learning: The Bagel Framework
• On the Complexity and Approximability of Optimal Sensor Selection for Kalman Filtering
• Multi-Slice Low-Rank Tensor Decomposition Based Multi-Atlas Segmentation: Application to Automatic Pathological Liver CT Segmentation
• Robust Compressed Sensing and Sparse Coding with the Difference Map
• Greedy Deep Dictionary Learning
• Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Most tensor problems are NP-hard
• Optimality and computational barriers in variable selection under dependence
• The Unseen Frontier: Pushing the Limits of LLM Sparsity with Surrogate-Free ADMM
• Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices
• Sketching Low-Rank Plus Diagonal Matrices
• Analysis of The Ratio of ℓ₁ and ℓ₂ Norms in Compressed Sensing
• Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
• Can we allow linear dependencies in the dictionary in the sparse synthesis framework?
• Exact Recovery Conditions for Sparse Representations with Partial Support Information
• Efficient Blind Compressed Sensing Using Sparsifying Transforms with Convergence Guarantees and Application to MRI
• Fast and General Model Selection using Data Depth and Resampling
• Signal Recovery in Uncorrelated and Correlated Dictionaries Using\n Orthogonal Least Squares
• Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
• Low-rank matrix recovery via iteratively reweighted least squares\n minimization
• Convex Optimization without Projection Steps
• A Scale Invariant Approach for Sparse Signal Recovery
• Hyperspectral Unmixing Overview: Geometrical, Statistical, and Sparse Regression-Based Approaches
• QWHA: Quantization-Aware Walsh-Hadamard Adaptation for Parameter-Efficient Fine-Tuning on Large Language Models
• Automated Constitutive Model Discovery by Pairing Sparse Regression Algorithms with Model Selection Criteria
• Probabilistic and nonlinear compressive sensing
• Face frontalization for Alignment and Recognition
• Explainability in music recommender systems
• Optimal k-thresholding algorithms for sparse optimization problems
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Metritocracy: Representative Metrics for Lite Benchmarks
• Analysis of Optimal Thresholding Algorithms for Compressed Sensing
• The convergence guarantee of the iterative thresholding algorithm with suboptimal feedbacks for large systems
• Beyond Moore-Penrose Part II: The Sparse Pseudoinverse
• Sparse Solutions to Nonnegative Linear Systems and Applications
• Variable Selection Using Relative Importance Rankings
• Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
• Convolutional Dictionary Learning in Hierarchical Networks
• Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance
• Functional Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
• Matrix sparsification and the sparse null space problem
• Rank-one Convexification for Sparse Regression
• Upper Bounds on the Error of Sparse Vector and Low-Rank Matrix Recovery
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• Local Search Algorithms for Rank-Constrained Convex Optimization
• Optimization Problems for Machine Learning: A Survey
• Cooperative Sparsity Pattern Recovery in Distributed Networks Via\n Distributed-OMP
• Compressive sensing: a paradigm shift in signal processing
• The Cramer-Rao Bound for Sparse Estimation
• Compressed Sensing: How sharp is the Restricted Isometry Property
• Hyperspectral Imaging and Analysis for Sparse Reconstruction and Recognition
• Adaptive support driven Bayesian reweighted algorithm for sparse signal recovery
• Lass-0: sparse non-convex regression by local search
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
• Global optimization for low-dimensional switching linear regression and bounded-error estimation
• Continuous Donoho-Elad Spark Uncertainty Principle
• Transfer Learning Using Feature Selection
• Nonlinear compressed sensing based on composite mappings and its pointwise linearization
• SparseStep: Approximating the Counting Norm for Sparse Regularization
• WEEP: A Differentiable Nonconvex Sparse Regularizer via Weakly-Convex Envelope
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• A new inexact iterative hard thresholding algorithm for compressed sensing
• Recovery of sparsest signals via ℓ^q-minimization
• Sparse Recovery from Group Orbits
• Density matrix and fidelity estimation of multiphoton entanglement via phaselift
• Photoacoustic Reconstruction Using Sparsity in Curvelet Frame: Image versus Data Domain
• Beyond Moore-Penrose Part I: Generalized Inverses that Minimize Matrix Norms
• Sparseness helps: Sparsity Augmented Collaborative Representation for Classification
• Estimating Traffic and Anomaly Maps via Network Tomography
• Stable image reconstruction using total variation minimization
• Computational Intractability of Dictionary Learning for Sparse Representation
• Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
• Restricted isometries for partial random circulant matrices
• Online Sparse Linear Regression
• Scalable Algorithms for the Sparse Ridge Regression
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• A critical review of LASSO and its derivatives for variable selection under dependence among covariates
• Equivalence of L0 and L1 Minimizations in Sudoku Problem
• Robust Sparse Analysis Regularization
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Variable Selection with Second-Generation P-Values
• Sublinear Time, Approximate Model-based Sparse Recovery For All
• EnTrans:Leveraging Kinetic Energy Harvesting Signal for Transportation Mode Detection
• An O(nlog(n)) Algorithm for Projecting Onto the Ordered Weighted ℓ₁ Norm Ball
• A greedy anytime algorithm for sparse PCA
• Hierarchical Recovery in Compressive Sensing
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• On Sparse Representation in Fourier and Local Bases
• The Nonconvex Geometry of Linear Inverse Problems
• Robust Node Localization for Rough and Extreme Deployment Environments
• A Theoretical Perspective of Solving Phaseless Compressed Sensing via Its Nonconvex Relaxation
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Concentration of the Frobenius norm of generalized matrix inverses
• On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
• Horseshoe Regularization for Feature Subset Selection
• Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization
• 1-norm minimization and minimum-rank structured sparsity for symmetric and ah-symmetric generalized inverses: rank one and two
• Solving OSCAR regularization problems by proximal splitting algorithms
• Phase Transitions for Greedy Sparse Approximation Algorithms
• Scalable Subset Selection in Linear Mixed Models
• Sparse and silent coding in neural circuits
• Checking the strict positivity of Kraus maps is NP-hard
• Non-Convex Compressed Sensing with Training Data
• Decoding by Linear Programming
• Sparse Representation of Gaussian Molecular Surface
• On a phase transition in general order spline regression
• Coherence-based Partial Exact Recovery Condition for OMP/OLS
• ADMM-MCP Framework for Sparse Recovery with Global Convergence
• Restoring STM images via Sparse Coding: noise and artifact removal
• Sampling Requirements and Accelerated Schemes for Sparse Linear Regression with Orthogonal Least-Squares
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Accelerated Search for Non-Negative Greedy Sparse Decomposition via Dimensionality Reduction
• Evaluating Sparse Autoencoders: From Shallow Design to Matching Pursuit
• Non-convexly constrained linear inverse problems
• A Risk Ratio Comparison of l₀ and l₁ Penalized Regression
• Fast thresholding algorithms with feedbacks for sparse signal recovery
• Nonparametric Sparse Representation
• RODEO: Robust DE-aliasing autoencOder for Real-time Medical Image Reconstruction
• Submodularity in Statistics: Comparing the Success of Model Selection Methods
• Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression
• Variable Selection in GLM and Cox Models with Second-Generation P-Values
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty
• Image denoising via K-SVD with primal-dual active set algorithm
• Tensor robust principal component analysis via the tensor nuclear over Frobenius norm
• Greedy Minimization of Weakly Supermodular Set Functions
• Blended Matching Pursuit
• From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit
• Sparsification of Matrices and Compressed Sensing
• Greedy recursion parameter selection for one-way spatial integration of hyperbolic equations
• Unique Reconstruction From Mean-Field Measurements
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
• Mallows-type model averaging: Non-asymptotic analysis and all-subset combination
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Optimal Sparse Linear Auto-Encoders and Sparse PCA
• DB-KSVD: Scalable Alternating Optimization for Disentangling High-Dimensional Embedding Spaces
• Analysis and algorithms for some compressed sensing models based on L1/L2 minimization
• Sparse Linear Surrogates for Interpretable Budget Allocation
• Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
• Efficient Projection Algorithms onto the Weighted l1 Ball
• Sharp Threshold for Multivariate Multi-Response Linear Regression via Block Regularized Lasso
• New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems
• A Scalable Gradient-Based Optimization Framework for Sparse Minimum-Variance Portfolio Selection
• Dictionary Identification - Sparse Matrix-Factorisation via ℓ₁-Minimisation
• Sparse Projections of Medical Images onto Manifolds
• Econométrie et Machine Learning
• Measurement of Multilayer Coating Thickness on Interwoven Carbon-Fiber-Reinforced Polymers Using the Terahertz PHASR Scanner
• Rank Awareness in Joint Sparse Recovery
• Automatic Basis Function Selection in Iterative Learning Control: A Sparsity-Promoting Approach Applied to an Industrial Printer
• Smoothed analysis in compressed sensing
• Coherence-Pattern Guided Compressive Sensing with Unresolved Grids
• ECME Thresholding Methods for Sparse Signal Reconstruction
• Attribute-Efficient Evolvability of Linear Functions
• Efficient Sparse Group Feature Selection via Nonconvex Optimization
• Label Embedded Dictionary Learning for Image Classification
• The finite steps of convergence of the fast thresholding algorithms with feedbacks
• Population-Robust Feature Selection via Generalized Welfare Optimization
• A Lagrange-Newton Algorithm for Sparse Nonlinear Programming
• Uniqueness Conditions for A Class of l0-Minimization Problems
• Equivalence and Strong Equivalence between Sparsest and Least ℓ₁-Norm Nonnegative Solutions of Linear Systems and Their Application
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• Optimal Sketching Bounds for Sparse Linear Regression
• A refined convergence analysis of pDCA_e with applications to simultaneous sparse recovery and outlier detection
• Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion
• Guessing Efficiently for Constrained Subspace Approximation
• Statistical-Physics-Based Reconstruction in Compressed Sensing
• Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices
• On the Computational Intractability of Exact and Approximate Dictionary Learning
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Data-Driven Stabilization of Periodic Orbits
• Accelerating E-Commerce Search Engine Ranking by Contextual Factor Selection
• Sparse Approximate Solution of Partial Differential Equations
• Scalable Data-Driven Basis Selection for Linear Machine Learning Interatomic Potentials
• A Fiber Measurement System with Approximate Deconvolution Based on the\n Analysis of Fault Clusters in Linearized Bregman Iterations
• Truncated Huber Penalty for Sparse Signal Recovery with Convergence Analysis
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing
• Global Sensitivity Analysis and Estimation of Model Error, Toward Uncertainty Quantification in Scramjet Computations
• Uncertainty Principle and Sparse Reconstruction in Pairs of Orthonormal Rational Function Bases
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Convolutional Sparse Coding Fast Approximation With Application to Seismic Reflectivity Estimation
• Revealing physical interaction networks from statistics of collective dynamics
• Learning Some Popular Gaussian Graphical Models without Condition Number\n Bounds
• Minimizing L 1 over L 2 norms on the gradient
• Exact sparse reconstruction form Vandermonde matrices
• Accelerated Linearized Bregman Method
• Interpreting latent variables in factor models via convex optimization
• A dedicated greedy pursuit algorithm for sparse spectral representation of music sound
• A regression algorithm for accelerated lattice QCD that exploits sparse inference on the D-Wave quantum annealer
• Communication-Efficient Distributed SGD With Compressed Sensing
• An Algorithm to Solve Cardinality Constrained Quadratic Optimization Problem with an Application to the Best Subset Selection in Regression
• A scalable mixed-integer conic optimization approach to cardinality-constrained Poisson regression with safe screening

Related

• For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution
• Sparse Solutions of a Class of Constrained Optimization Problems
• Sparse solution of overdetermined linear systems when the columns of A are orthogonal
• Sparse Approximation Over the Cube
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images