Sparse Approximate Solutions to Linear Systems

1995/04/01 by B. K. Natarajan · 123 citations
Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques #Computational Geometry and Mesh Generation

paper · doi:10.1137/s0097539792240406

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\n 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>ℓ</mml:mi><mml:mi>q</mml:mi></mml:msub></mml:math>-minimization for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.gif" overflow="scroll"><mml:mn>0</mml:mn><mml:mo>&lt;</mml:mo><mml:mi>q</mml:mi><mml:mo>⩽</mml:mo><mml:mn>1</mml:mn></mml:math>
• 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\n 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\n Algorithms, Tractability, and Hardness
• 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
• A Critical Review of LASSO and Its Derivatives for Variable Selection Under Dependence Among Covariates
• 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
• Lower bounds on the performance of polynomial-time algorithms for sparse\n linear regression
• Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
• Global optimization for low-dimensional switching linear regression and\n 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

Related

• For most large underdetermined systems of equations, the minimal 𝓁₁‐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