From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images

DOI10.1137/060657704zbMath1178.68619OpenAlexW1976709621WikidataQ60547114 ScholiaQ60547114MaRDI QIDQ3614217

David L. Donoho, Alfred Marcel Bruckstein, Michael Elad

Publication date: 16 March 2009

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/63c53e35b25e09a3432e4f4dd786f5d539304f30

zbMATH Keywords

inverse problems compression underdetermined denoising sparse representation mutual coherence dictionary learning linear system of equations sparse coding matching pursuit basis pursuit redundant overcomplete sparse-land

Mathematics Subject Classification ID

Convex programming (90C25) Computing methodologies for image processing (68U10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Inverse problems in linear algebra (15A29) Linear equations (linear algebraic aspects) (15A06)

Related Items

Model recovery for multi-input signal-output nonlinear systems based on the compressed sensing recovery theory, Stable high-order cubature formulas for experimental data, A survey on some recent developments of alternating direction method of multipliers, A truncated Newton algorithm for nonconvex sparse recovery, High-dimensional change-point estimation: combining filtering with convex optimization, Nonmonotone diagonally scaled limited-memory BFGS methods with application to compressive sensing based on a penalty model, Principle component analysis: robust versions, A hybrid quasi-Newton method with application in sparse recovery, Gradient projection Newton pursuit for sparsity constrained optimization, The springback penalty for robust signal recovery, A solution approach for cardinality minimization problem based on fractional programming, An active set Newton-CG method for $\ell_1$ optimization, Simple structures in problems of control theory: formalization and synthesis, Randomization and entropy in machine learning and data processing, Entropy-randomized projection, Smoothing strategy along with conjugate gradient algorithm for signal reconstruction, Global sensitivity analysis for multivariate outputs using polynomial chaos-based surrogate models, Generalizing CoSaMP to signals from a union of low dimensional linear subspaces, A note on the spectral gradient projection method for nonlinear monotone equations with applications, Convex optimization in sums of Banach spaces, On description of dual frames, Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs, Sparse signal reconstruction via the approximations of $\ell_0$ quasinorm, A preconditioned conjugate gradient method with active set strategy for $\ell_1$-regularized least squares, A smoothing method for sparse optimization over convex sets, Iterative identification for multiple-input systems with time-delays based on greedy pursuit and auxiliary model, Basis adaptive sample efficient polynomial chaos (BASE-PC), A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions, Group sparse recovery in impulsive noise via alternating direction method of multipliers, Comparison of the performance and reliability between improved sampling strategies for polynomial chaos expansion, A perturbation analysis of nonconvex block-sparse compressed sensing, A Barzilai-Borwein gradient projection method for sparse signal and blurred image restoration, A new hybrid $l_p$-$l_2$ model for sparse solutions with applications to image processing, The effect of perturbations of frames and fusion frames on their redundancies, A safe reinforced feature screening strategy for Lasso based on feasible solutions, A two-stage method for spectral-spatial classification of hyperspectral images, On sparse recovery algorithms in unions of orthonormal bases, Lifted stationary points of sparse optimization with complementarity constraints, A superlinearly convergent $R$-regularized Newton scheme for variational models with concave sparsity-promoting priors, Autoregressive identification of Kronecker graphical models, Partial $S$-goodness for partially sparse signal recovery, A dual-primal balanced augmented Lagrangian method for linearly constrained convex programming, Optimal observations-based retrieval of topography in 2D shallow water equations using PC-EnKF, Mathematical programs with complementarity constraints and a non-Lipschitz objective: optimality and approximation, Signal separation under coherent dictionaries and $\ell_p$-bounded noise, On constrained optimization with nonconvex regularization, The complexity results of the sparse optimization problems and reverse convex optimization problems, A unifying representer theorem for inverse problems and machine learning, An efficient adaptive forward-backward selection method for sparse polynomial chaos expansion, Analysis of the maximum magnification by the scaled memoryless DFP updating formula with application to compressive sensing, An alternating direction method of multipliers for tensor complementarity problems, A hybrid sequential sampling strategy for sparse polynomial chaos expansion based on compressive sampling and Bayesian experimental design, A proximal fully parallel splitting method for stable principal component pursuit, Identification of alterations in the Jacobian of biochemical reaction networks from steady state covariance data at two conditions, The nonnegative zero-norm minimization under generalized $Z$-matrix measurement, Data-driven time-frequency analysis, Geometric separation by single-pass alternating thresholding, Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Convergence of a data-driven time-frequency analysis method, Solving $\ell_0$-penalized problems with simple constraints via the Frank-Wolfe reduced dimension method, Necessary and sufficient conditions of solution uniqueness in 1-norm minimization, A general self-adaptive relaxed-PPA method for convex programming with linear constraints, Sparse identification of nonlinear dynamical systems via reweighted $\ell_1$-regularized least squares, Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems, Alternating direction method for covariance selection models, Statistical Methods in Imaging, A dual symmetric Gauss-Seidel alternating direction method of multipliers for hyperspectral sparse unmixing, A second-order adaptive Douglas-Rachford dynamic method for maximal $\alpha$-monotone operators, Resolution Analysis of Imaging with $\ell_1$ Optimization, An augmented memoryless BFGS method based on a modified secant equation with application to compressed sensing, Fourier Operators in Applied Harmonic Analysis, On the Minimization Over Sparse Symmetric Sets: Projections, Optimality Conditions, and Algorithms, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Nonconvex sorted $\ell_1$ minimization for sparse approximation, A modulus-based iterative method for sparse signal recovery, An augmented Lagrangian proximal alternating method for sparse discrete optimization problems, A first approach to learning a best basis for gravitational field modelling, A perturbation analysis of block-sparse compressed sensing via mixed ℓ2/ℓ1 minimization, An offline/online procedure for dual norm calculations of parameterized functionals: empirical quadrature and empirical test spaces, A new generalized projection and its application to acceleration of audio declipping, An active set Barzilar-Borwein algorithm for $l_0$ regularized optimization, An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge, A linearly convergent algorithm without prior knowledge of operator norms for solving $\ell_1 - \ell_2$ minimization, Data-driven compressive sensing and applications in uncertainty quantification, A note on block-sparse signal recovery with coherent tight frames, Optimal subgradient methods: computational properties for large-scale linear inverse problems, Sparse reconstruction with multiple Walsh matrices, Overcomplete representation in a hierarchical Bayesian framework, EXACT LOW-RANK MATRIX RECOVERY VIA NONCONVEX SCHATTEN p-MINIMIZATION, Ensemble Kalman inversion for sparse learning of dynamical systems from time-averaged data, A Peaceman-Rachford splitting method with monotone plus skew-symmetric splitting for nonlinear saddle point problems, Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems, Convergence properties of monotone and nonmonotone proximal gradient methods revisited, Alternating direction method of multipliers for solving dictionary learning models, Theory and applications of compressed sensing, Greedy signal space methods for incoherence and beyond, Finding sparse solutions of systems of polynomial equations via group-sparsity optimization, An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization, Sparse regularization via bidualization, Dai-Liao extensions of a descent hybrid nonlinear conjugate gradient method with application in signal processing, Computing and analyzing recoverable supports for sparse reconstruction, Sparse signals recovered by non-convex penalty in quasi-linear systems, Wavelet inpainting with the $\ell_{0}$ sparse regularization, Relationship between the optimal solutions of least squares regularized with $\ell_{0}$-norm and constrained by $k$-sparsity, Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets, A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron, Sparse solutions of linear complementarity problems, Non-convex sparse regularisation, Convex optimization of measurement allocation for magnetic tracking systems, Split Bregman algorithms for sparse group lasso with application to MRI reconstruction, 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory, Equiangular tight frames that contain regular simplices, Robust classifier using distance-based representation with square weights, Tomographic image reconstruction using training images, Reweighted $\ell_1$ minimization method for stochastic elliptic differential equations, A weighted $\ell_1$-minimization approach for sparse polynomial chaos expansions, Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies, A variational approach of the rank function, Prior model identification during subsurface flow data integration with adaptive sparse representation techniques, An efficient sparse channel estimator combining time-domain LS and iterative shrinkage for OFDM systems with IQ-imbalances, The sparsity of underdetermined linear system via $l_p$ minimization for $0 < p < 1$, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays, Peaceman-Rachford splitting for a class of nonconvex optimization problems, Sparse causality network retrieval from short time series, Restricted normal cones and sparsity optimization with affine constraints, Approximating sampled sinusoids and multiband signals using multiband modulated DPSS dictionaries, Sparse conjugate directions pursuit with application to fixed-size kernel models, Sampling in the analysis transform domain, On the representation of functions with Gaussian wave packets, Phase transitions for greedy sparse approximation algorithms, Sparse representations and approximation theory, Verifiable conditions of $\ell_{1}$-recovery for sparse signals with sign restrictions, An iterative algorithm for sparse and constrained recovery with applications to divergence-free current reconstructions in magneto-encephalography, A two-level method for sparse time-frequency representation of multiscale data, Sparse signal recovery via ECME thresholding pursuits, Restricted $p$-isometry properties of partially sparse signal recovery, A note on the complexity of $L _{p }$ minimization, An inverse problem in reaction kinetics, Sparse fusion frames: existence and construction, New bounds for RIC in compressed sensing, Entropy dimension reduction method for randomized machine learning problems, Solve exactly an under determined linear system by minimizing least squares regularized with an $\ell_0$ penalty, The nonlocal sparse reconstruction algorithm by similarity measurement with shearlet feature vector, An infeasible-point subgradient method using adaptive approximate projections, The smoothing FR conjugate gradient method for solving a kind of nonsmooth optimization problem with $l_1$-norm, Total variation image restoration method based on subspace optimization, Analysis sparse representation for nonnegative signals based on determinant measure by DC programming, Sparse recovery on Euclidean Jordan algebras, Coupled model and grid adaptivity in hierarchical reduction of elliptic problems, Sparse time-frequency representation of nonlinear and nonstationary data, A new piecewise quadratic approximation approach for $L_0$ norm minimization problem, On Glowinski's open question on the alternating direction method of multipliers, A variable fixing version of the two-block nonlinear constrained Gauss-Seidel algorithm for $\ell_1$-regularized least-squares, Equivalence and strong equivalence between the sparsest and least $\ell _1$-norm nonnegative solutions of linear systems and their applications, Analysis of convergence for the alternating direction method applied to joint sparse recovery, Blind identification of fully observed linear time-varying systems via sparse recovery, Learning semidefinite regularizers, Disjoint sparsity for signal separation and applications to hybrid inverse problems in medical imaging, Sparsity-promoting elastic net method with rotations for high-dimensional nonlinear inverse problem, Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery, A modified greedy analysis pursuit algorithm for the cosparse analysis model, DC formulations and algorithms for sparse optimization problems, Dictionary evaluation and optimization for sparse coding based speech processing, Sparse decomposition by iterating Lipschitzian-type mappings, Image reconstruction using analysis model prior, Sparse signal recovery using a new class of random matrices, Iterative reweighted methods for $\ell _1-\ell _p$ minimization, Spectral dynamics and regularization of incompletely and irregularly measured data, A quantitative notion of redundancy for finite frames, The null space property for sparse recovery from multiple measurement vectors, The projected GSURE for automatic parameter tuning in iterative shrinkage methods, Observability for initial value problems with sparse initial data, Identification of switched linear systems via sparse optimization, Non-smooth equations based method for $\ell_1$-norm problems with applications to compressed sensing, A non-adapted sparse approximation of PDEs with stochastic inputs, A semidefinite programming study of the Elfving theorem, Sparse approximate solution of partial differential equations, Adaptive algorithms for sparse system identification, Smoothing methods for nonsmooth, nonconvex minimization, Concave programming for minimizing the zero-norm over polyhedral sets, Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach, A tensor-based dictionary learning approach to tomographic image reconstruction, Enhancing sparsity of Hermite polynomial expansions by iterative rotations, Sparse feedback design in discrete-time linear systems, An efficient algorithm for learning dictionary under coherence constraint, On some deterministic dictionaries supporting sparsity, Iterative hard thresholding based on randomized Kaczmarz method, Learning sparse FRAME models for natural image patterns, Structured overcomplete sparsifying transform learning with convergence guarantees and applications, The Little Engine that Could: Regularization by Denoising (RED), A constrained optimization reformulation and a feasible descent direction method for $L_{1/2}$ regularization, Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach, Column subset selection via sparse approximation of SVD, Theoretical guarantees for graph sparse coding, Mini-workshop: Algebraic, geometric, and combinatorial methods in frame theory. Abstracts from the mini-workshop held September 30 -- October 6, 2018, Analysis of a nonsmooth optimization approach to robust estimation, Nomonotone spectral gradient method for sparse recovery, Redundancy of fusion frames in Hilbert spaces, Horseshoe Priors for Edge-Preserving Linear Bayesian Inversion, Second order self-adaptive dynamical system for sparse signal reconstruction and applications to image recovery, A non-convex piecewise quadratic approximation of $\ell_0$ regularization: theory and accelerated algorithm, First-order methods for convex optimization, Reconstruction of sparse recurrent connectivity and inputs from the nonlinear dynamics of neuronal networks, An approximate Newton-type proximal method using symmetric rank-one updating formula for minimizing the nonsmooth composite functions, Sparsity-Inducing Nonconvex Nonseparable Regularization for Convex Image Processing, On sparsity‐inducing methods in system identification and state estimation, A Lorentzian-$\ell_p$ norm regularization based algorithm for recovering sparse signals in two types of impulsive noise, A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions, A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems, Entropic Regularization of the ℓ 0 Function, Average Performance of the Sparsest Approximation Using a General Dictionary, A General Framework of Rotational Sparse Approximation in Uncertainty Quantification, Asymptotic behaviour of a nonautonomous evolution equation governed by a quasi-nonexpansive operator, Sparsity Based Methods for Overparameterized Variational Problems, Efficient Blind Compressed Sensing Using Sparsifying Transforms with Convergence Guarantees and Application to Magnetic Resonance Imaging, Global optimization for sparse solution of least squares problems, Constructing Surrogate Models of Complex Systems with Enhanced Sparsity: Quantifying the Influence of Conformational Uncertainty in Biomolecular Solvation, Regularized sparse representation for image deconvolution, Discriminative Sparse Representations, Boosting of Image Denoising Algorithms, A Dynamical Splitting Method for Minimizing the Sum of Three Convex Functions, An L p Norm Relaxation Approach to Positive Influence Maximization in Social Network under the Deterministic Linear Threshold Model, Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps, A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems, Performance analysis for unconstrained analysis based approaches*, Nonexpansiveness of a linearized augmented Lagrangian operator for hierarchical convex optimization, FRIST—flipping and rotation invariant sparsifying transform learning and applications, Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound, Heuristics for Finding Sparse Solutions of Linear Inequalities, Smoothing neural network for $L_0$ regularized optimization problem with general convex constraints, An inexact quasi-Newton algorithm for large-scale $\ell_1$ optimization with box constraints, Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka–Łojasiewicz Property Without Global Lipschitz Assumptions, A novel sparse polynomial chaos expansion technique with high adaptiveness for surrogate modelling, Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization, Sparse signal reconstruction via recurrent neural networks with hyperbolic tangent function, Image Denoising: The Deep Learning Revolution and Beyond—A Survey Paper, Lasso trigonometric polynomial approximation for periodic function recovery in equidistant points, Nonmonotone quasi-Newton-based conjugate gradient methods with application to signal processing, Accelerated smoothing hard thresholding algorithms for $\ell_0$ regularized nonsmooth convex regression problem, Optimal arrangements of classical and quantum states with limited purity, An Augmented Lagrangian Method for Non-Lipschitz Nonconvex Programming, A wonderful triangle in compressed sensing, Classifier-based adaptive polynomial chaos expansion for high-dimensional uncertainty quantification, Linear inverse problems with Hessian-Schatten total variation, A continuous dynamical splitting method for solving ‘strongly+weakly’ convex programming problems, DRIP: deep regularizers for inverse problems, Sum-of-squares relaxations in robust DC optimization and feature selection, A NONMONOTONE ADMM-BASED DIAGONAL QUASI-NEWTON UPDATE WITH APPLICATION TO THE COMPRESSIVE SENSING PROBLEM, On optimal solutions of the constrained ℓ ₀ regularization and its penalty problem, CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, A null-space-based weightedl₁minimization approach to compressed sensing, Gradient-based method with active set strategy for $\ell _1$ optimization, Proximal Mapping for Symmetric Penalty and Sparsity, Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification, Sparse Support Vector Machines in Reproducing Kernel Banach Spaces, Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets, A gradient projection method for the sparse signal reconstruction in compressive sensing, Calibration of reduced-order model for a coupled Burgers equations based on PC-EnKF, Generalized Mercer Kernels and Reproducing Kernel Banach Spaces, Hierachical Bayesian models and sparsity: ℓ ₂ -magic, A Clustering Approach to Constrained Binary Matrix Factorization, Кросс-энтропийная редукции матрицы данных с ограничением информационной емкости матриц-проекторов и их норм, Statistical mechanics of complex neural systems and high dimensional data, Sparsity Promoting Hybrid Solvers for Hierarchical Bayesian Inverse Problems, Non-convex Optimization via Strongly Convex Majorization-minimization, Microlocal Analysis of the Geometric Separation Problem, The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty, Sparse Solutions of Linear Diophantine Equations, Penalty Methods for a Class of Non-Lipschitz Optimization Problems, Gauss–Newton Methods for Robust Parameter Estimation, Linearized Bregman iterations for compressed sensing, Using automatic differentiation for compressive sensing in uncertainty quantification, A Multiple Measurement Vector Approach to Synthetic Aperture Radar Imaging, Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere, Blind Source Separation with Outliers in Transformed Domains, New Upper Bounds for Equiangular Lines by Pillar Decomposition, Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems, Data-Driven Nonsmooth Optimization, Computation of second-order directional stationary points for group sparse optimization, Generalized Conjugate Gradient Methods for ℓ₁ Regularized Convex Quadratic Programming with Finite Convergence, Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction, Imaging with highly incomplete and corrupted data, Sparsity promoting regularization for effective noise suppression in SPECT image reconstruction, Concave programming for finding sparse solutions to problems with convex constraints, Solving inverse problems using data-driven models, ADAPTIVE DATA ANALYSIS VIA SPARSE TIME-FREQUENCY REPRESENTATION, A Greedy Approach to $\ell_{0,\infty}$-Based Convolutional Sparse Coding, Sparse Bayesian Imaging of Solar Flares, A fast conjugate gradient algorithm with active set prediction for ℓ₁ optimization, Sparse Solutions by a Quadratically Constrained ℓq (0 <q< 1) Minimization Model, Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark, Sparse recovery with general frame via general-dual-based analysis Dantzig selector, Principles and Typical Computational Limitations of Sparse Speaker Separation Based on Deterministic Speech Features, Uniqueness Conditions for A Class of ℓ₀-Minimization Problems, Unnamed Item, Sampling in Image Representation and Compression, Unnamed Item, Group Sparse Optimization for Images Recovery Using Capped Folded Concave Functions, Regularization by Denoising via Fixed-Point Projection (RED-PRO), A New Computational Method for the Sparsest Solutions to Systems of Linear Equations, A non-convex regularization approach for stable estimation of loss development factors, An Overview of Computational Sparse Models and Their Applications in Artificial Intelligence, Sparse Solutions of a Class of Constrained Optimization Problems, Compressive Sensing-Based Computed Tomography Imaging: An effective approach for COVID-19 Detection, Data-Driven Reconstruction and Encoding of Sparse Stimuli across Convergent Sensory Layers from Downstream Neuronal Network Dynamics, A penalty PALM method for sparse portfolio selection problems, Multi-Layer Sparse Coding: The Holistic Way