For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
From MaRDI portal
Publication:5471032
DOI10.1002/CPA.20132zbMath1113.15004OpenAlexW2050834445WikidataQ29392029 ScholiaQ29392029MaRDI QIDQ5471032
Publication date: 6 June 2006
Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/cpa.20132
eigenvalues of random matricesgreedy algorithmsmatching pursuitbasis pursuitovercomplete representationsalmost-Euclidean sections of Banach spacesminimum \(l_1\)-decompositionsign-embeddings in Banach spacessolution of underdetermined linear systemssparse representation problem
Computational methods for sparse matrices (65F50) Geometric probability and stochastic geometry (60D05) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Quadratic programming (90C20) Convex functions and convex programs in convex geometry (52A41) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Linear equations (linear algebraic aspects) (15A06)
Related Items (only showing first 100 items - show all)
A regularized interior-point method for constrained linear least squares ⋮ Gibbs phenomena for Lq-best approximation in finite element spaces ⋮ Convergence and regularization results for optimal control problems with sparsity functional ⋮ A general theory for subspace-sparse recovery ⋮ Compressive Sensing with Cross-Validation and Stop-Sampling for Sparse Polynomial Chaos Expansions ⋮ Efficient Blind Compressed Sensing Using Sparsifying Transforms with Convergence Guarantees and Application to Magnetic Resonance Imaging ⋮ The asymptotic distribution and Berry-Esseen bound of a new test for independence in high dimension with an application to stochastic optimization ⋮ Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction ⋮ A component lasso ⋮ Model Selection With Lasso-Zero: Adding Straw to the Haystack to Better Find Needles ⋮ Unnamed Item ⋮ Fiber Orientation Distribution Estimation Using a Peaceman--Rachford Splitting Method ⋮ Classifiers of support vector machine type with \(\ell_1\) complexity regularization ⋮ Sparsity Constrained Estimation in Image Processing and Computer Vision ⋮ A Continuous Exact $\ell_0$ Penalty (CEL0) for Least Squares Regularized Problem ⋮ Extracting Sparse High-Dimensional Dynamics from Limited Data ⋮ Unnamed Item ⋮ Nonlinear regularization techniques for seismic tomography ⋮ Error bounds for compressed sensing algorithms with group sparsity: A unified approach ⋮ A microscopic-view infection model based on linear systems ⋮ An inexact continuation accelerated proximal gradient algorithm for lown-rank tensor recovery ⋮ The degrees of freedom of partly smooth regularizers ⋮ A Dai-Liao-type projection method for monotone nonlinear equations and signal processing ⋮ Proximal linearization methods for Schatten \(p\)-quasi-norm minimization ⋮ Adaptive spatial-spectral dictionary learning for hyperspectral image restoration ⋮ Dynamic behavior analysis via structured rank minimization ⋮ Flexible semi-supervised embedding based on adaptive loss regression: application to image categorization ⋮ High-dimensional generalized linear models and the lasso ⋮ A Unified View of Exact Continuous Penalties for $\ell_2$-$\ell_0$ Minimization ⋮ Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression ⋮ Statistical learning and selective inference ⋮ A Barzilai-Borwein gradient projection method for sparse signal and blurred image restoration ⋮ New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem ⋮ Algorithms for Sparse Nonnegative Tucker Decompositions ⋮ Compressive Sensing ⋮ Sparse eigenbasis approximation: multiple feature extraction across spatiotemporal scales with application to coherent set identification ⋮ Flavors of Compressive Sensing ⋮ Inverse potential problems for divergence of measures with total variation regularization ⋮ On a Scalable Entropic Breaching of the Overfitting Barrier for Small Data Problems in Machine Learning ⋮ An unbiased approach to compressed sensing ⋮ Concentration of \(S\)-largest mutilated vectors with \(\ell_p\)-quasinorm for \(0<p\leq 1\) and its applications ⋮ Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise ⋮ A look at robustness and stability of \(\ell_1\)-versus \(\ell_0\)-regularization: discussion of papers by Bertsimas et al. and Hastie et al. ⋮ Accelerating Sparse Recovery by Reducing Chatter ⋮ Parameter estimation and signal reconstruction ⋮ Consistency Analysis for Massively Inconsistent Datasets in Bound-to-Bound Data Collaboration ⋮ Sparsity Promoting Hybrid Solvers for Hierarchical Bayesian Inverse Problems ⋮ Leveraging Sparsity and Compressive Sensing for Reduced Order Modeling ⋮ Microlocal Analysis of the Geometric Separation Problem ⋮ Statistical challenges of high-dimensional data ⋮ Unnamed Item ⋮ Gaussian averages of interpolated bodies and applications to approximate reconstruction ⋮ The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder). ⋮ Rodeo: Sparse, greedy nonparametric regression ⋮ Geometric separation by single-pass alternating thresholding ⋮ Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO ⋮ Ways to sparse representation: An overview ⋮ Data science, big data and statistics ⋮ On convex envelopes and regularization of non-convex functionals without moving global minima ⋮ Introduction ⋮ A novel hierarchical fingerprint matching approach ⋮ Sparse regularization for semi-supervised classification ⋮ Regression based automatic face annotation for deformable model building ⋮ A Regularized Correntropy Framework for Robust Pattern Recognition ⋮ OperA: Operator-Based Annihilation for Finite-Rate-of-Innovation Signal Sampling ⋮ A gradient descent based algorithm for \(\ell_p\) minimization ⋮ Lazy lasso for local regression ⋮ The stochastic properties of \(\ell^1\)-regularized spherical Gaussian fields ⋮ Sparse reconstructions from few noisy data: analysis of hierarchical Bayesian models with generalized gamma hyperpriors ⋮ Tensor Least Angle Regression for Sparse Representations of Multidimensional Signals ⋮ Sharp oracle inequalities for low-complexity priors ⋮ An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors ⋮ An active set Barzilar-Borwein algorithm for \(l_0\) regularized optimization ⋮ Performance of algebraic multigrid methods for non-symmetric matrices arising in particle methods ⋮ Sparse Sensor Placement Optimization for Classification ⋮ Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction ⋮ Regularized ranking with convex losses and \(\ell^1\)-penalty ⋮ Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization ⋮ Identification of sparse FIR systems using a general quantisation scheme ⋮ On perturbed steepest descent methods with inexact line search for bilevel convex optimization ⋮ Unnamed Item ⋮ Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit ⋮ Iterative Hard-Thresholding Applied to Optimal Control Problems with $L^0(\Omega)$ Control Cost ⋮ Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines ⋮ Orthogonal matched wavelets with vanishing moments: a sparsity design approach ⋮ Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems ⋮ Discussion: Latent variable graphical model selection via convex optimization ⋮ Discussion: Latent variable graphical model selection via convex optimization ⋮ Discussion: Latent variable graphical model selection via convex optimization ⋮ Discussion: Latent variable graphical model selection via convex optimization ⋮ Discussion: Latent variable graphical model selection via convex optimization ⋮ Unnamed Item ⋮ Generalized cross validation in variable selection with and without shrinkage ⋮ An accelerated majorization-minimization algorithm with convergence guarantee for non-Lipschitz wavelet synthesis model * ⋮ Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates ⋮ KERNEL METHODS FOR INDEPENDENCE MEASUREMENT WITH COEFFICIENT CONSTRAINTS ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds ⋮ Optimal \(D\)-RIP bounds in compressed sensing ⋮ Improved combination of RPCA and MEL for sparse representation-based face recognition ⋮ Low rank matrix recovery with adversarial sparse noise*
Uses Software
Cites Work
This page was built for publication: For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
