Enhancing sparsity by reweighted _1 minimization
From MaRDI portal
Publication:734955
Abstract: It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained L1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms L1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted L1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations--not by reweighting the L1 norm of the coefficient sequence as is common, but by reweighting the L1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as compressed sensing.
In this nice paper, the authors study a new method for sparse signal recovery that outperforms (unweighted) \(\ell_1\)minimization in the sense that substantially fewer measurements are needed for exact recovery. Let \(\Phi\) be a real \(m\times n\) matrix with \(m<n\). The authors would want to recover a (sparse) signal \(x_0 \in {\mathbb R}^n\) from given data \(y = \Phi x_0\) by solving a weighted \(\ell_1\) minimization problem \[ \min_{x\in {\mathbb R}^n} \sum_{i=1}^n w_i\,|x_i| \;\mathrm{subject to}\; y=\Phi x\,, \] where \(w_i\) are positive weights and \(x = (x_i)_{i=1}^n\in {\mathbb R}^n\). The authors propose a simple iterative algorithm that alternates between estimating \(x_0\) and redefining the weights. The weights are stepwise computed from the current solution. The number of iterations is typically very low. This iterative algorithm falls in the general class of majorization-minimization algorithms. Numerous experiments demonstrate the performance and applicability of this algorithm in sparse signal recovery, compressive sensing, statistical estimation, error correction, and magnetic resonance imaging. This paper closes with discussions of related work and possible future directions.
Recommendations
- Reweighted _1-minimization for sparse solutions to underdetermined linear systems
- Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property
- Stable signal recovery from incomplete and inaccurate measurements
- Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
- Iteratively reweighted least squares minimization for sparse recovery
Cites work
- $\ell_1$ Trend Filtering
- A generalized uncertainty principle and sparse representation in pairs of bases
- An Iterative Technique for Absolute Deviations Curve Fitting
- Analysis versus synthesis in signal priors
- Atomic Decomposition by Basis Pursuit
- Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
- Compressed sensing
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Decoding by Linear Programming
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 804558 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Just relax: convex programming methods for identifying sparse signals in noise
- Linear Inversion of Band-Limited Reflection Seismograms
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Nonlinear total variation based noise removal algorithms
- On the stability of the basis pursuit in the presence of noise
- One-step sparse estimates in nonconcave penalized likelihood models
- Portfolio optimization with linear and fixed transaction costs
- Robust regression using iteratively reweighted least-squares
- Robust Statistics
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Second-order Cone Programming Methods for Total Variation-Based Image Restoration
- Signal Recovery and the Large Sieve
- Sparse representations in unions of bases
- Stable signal recovery from incomplete and inaccurate measurements
- The Adaptive Lasso and Its Oracle Properties
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
- Uncertainty principles and ideal atomic decomposition
- Uncertainty Principles and Signal Recovery
Cited in
(only showing first 100 items - show all)- A unified approach to model selection and sparse recovery using regularized least squares
- Estimating the dimension of a model
- Sparse high-dimensional fractional-norm support vector machine via DC programming
- A linearly convergent algorithm for sparse signal reconstruction
- Tuning parameter selection in sparse regression modeling
- Computation of sparse and dense equilibrium strategies of evolutionary games
- Variable selection via generalized SELO-penalized linear regression models
- Improved adaptive sparse channel estimation using mixed square/fourth error criterion
- A new sensor selection scheme for Bayesian learning based sparse signal recovery in WSNs
- Prior model identification during subsurface flow data integration with adaptive sparse representation techniques
- Speckle noise reduction via nonconvex high total variation approach
- Compressed sensing of data with a known distribution
- Mixed Hölder matrix discovery via wavelet shrinkage and Calderón-Zygmund decompositions
- Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
- Relaxed sparse eigenvalue conditions for sparse estimation via non-convex regularized regression
- Optimal network design for synchronization of coupled oscillators
- An improved algorithm for the \(L_2-L_p\) minimization problem
- A generalized elastic net regularization with smoothed \(\ell _{q}\) penalty for sparse vector recovery
- Online fault diagnosis for nonlinear power systems
- Genetic algorithm versus classical methods in sparse index tracking
- \(\ell _p\) regularized low-rank approximation via iterative reweighted singular value minimization
- Image denoising using combined higher order non-convex total variation with overlapping group sparsity
- Weak fault detection of tapered rolling bearing based on penalty regularization approach
- Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
- An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration
- Bound alternative direction optimization for image deblurring
- Efficient LED-SAC sparse estimator using fast sequential adaptive coordinate-wise optimization (LED-2SAC)
- Sparse signal reconstruction based on multiparameter approximation function with smoothed _0 norm
- An adaptive gradient projection algorithm for piecewise convex optimization and its application in compressed spectrum sensing
- Bayesian augmented Lagrangian algorithm for system identification
- A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
- Multiple-prespecified-dictionary sparse representation for compressive sensing image reconstruction with nonconvex regularization
- On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1]\)
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- Sign function based sparse adaptive filtering algorithms for robust channel estimation under non-Gaussian noise environments
- Reducing effects of bad data using variance based joint sparsity recovery
- Block matching local SVD operator based sparsity and TV regularization for image denoising
- Subspace-based spectrum estimation in innovation models by mixed norm minimization
- A proximal difference-of-convex algorithm with extrapolation
- Sparse signal recovery with prior information by iterative reweighted least squares algorithm
- RTE-based parameter reconstruction with \(T V + L^1\) regularization
- DC programming and DCA: thirty years of developments
- Iterative reweighted methods for \(\ell _1-\ell _p\) minimization
- Equivalent Lipschitz surrogates for zero-norm and rank optimization problems
- Templates for convex cone problems with applications to sparse signal recovery
- Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
- Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach
- A truncation algorithm for minimizing the Frobenius-Schatten norm to find a sparse matrix
- \(\ell_1\)- and \(\ell_2\)-norm joint regularization based sparse signal reconstruction scheme
- Broken adaptive ridge regression and its asymptotic properties
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- Toward fast transform learning
- A bimodal co-sparse analysis model for image processing
- A logarithmic image prior for blind deconvolution
- Sparsity driven people localization with a heterogeneous network of cameras
- Multi-parametric solution-path algorithm for instance-weighted support vector machines
- The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
- Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing
- Side-information-induced reweighted sparse subspace clustering
- Approximate versions of proximal iteratively reweighted algorithms including an extended IP-ICMM for signal and image processing problems
- Rapid compressed sensing reconstruction: a semi-tensor product approach
- Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM
- A new globally convergent algorithm for non-Lipschitz \(\ell_{p}-\ell_q\) minimization
- Design of \(\mathcal H_2\) \((\mathcal H_\infty)\)-based optimal structured and sparse static output feedback gains
- A support-denoiser-driven framework for single image restoration
- Sparse identification of nonlinear dynamical systems via reweighted \(\ell_1\)-regularized least squares
- Consistency bounds and support recovery of d-stationary solutions of sparse sample average approximations
- A robust graph-based semi-supervised sparse feature selection method
- Variational Bayesian inversion for the reaction coefficient in space-time nonlocal diffusion equations
- New regularization method and iteratively reweighted algorithm for sparse vector recovery
- A continuous relaxation of the constrained \(\ell_2-\ell_0\) problem
- Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
- An outer-inner linearization method for non-convex and nondifferentiable composite regularization problems
- A modulus-based iterative method for sparse signal recovery
- Nonconvex and nonsmooth sparse optimization via adaptively iterative reweighted methods
- Dual-density-based reweighted \(\ell_1\)-algorithms for a class of \(\ell_0\)-minimization problems
- The nonconvex tensor robust principal component analysis approximation model via the weighted _p-norm regularization
- Patch-based weighted SCAD prior for Rician noise removal
- \(H_{\infty}\) observer-based control for large-scale systems with sparse observer communication network
- Image retinex based on the nonconvex TV-type regularization
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
- Weighted thresholding homotopy method for sparsity constrained optimization
- Ensemble Kalman inversion for sparse learning of dynamical systems from time-averaged data
- Non-convex fractional-order TV model for impulse noise removal
- Hybrid non-convex regularizers model for removing multiplicative noise
- Reweighted sparse unmixing for hyperspectral images with noise level estimation
- A convex relaxation framework consisting of a primal-dual alternative algorithm for solving \(\ell_0\) sparsity-induced optimization problems with application to signal recovery based image restoration
- SABRINA: a stochastic subspace majorization-minimization algorithm
- GenMod: a generative modeling approach for spectral representation of PDEs with random inputs
- Tucker-3 decomposition with sparse core array using a penalty function based on Gini-index
- The proximity operator of the log-sum penalty
- Conditionally exponential prior in focal near- and far-field EEG source localization via randomized multiresolution scanning (RAMUS)
- Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems
- Efficient projection algorithms onto the weighted \(\ell_1\) ball
- Estimation of dynamic systems using a method of characteristics filter
- The inverse problem for conducting defective lattices
- Neural network training using \(\ell_1\)-regularization and bi-fidelity data
- A combined higher order non-convex total variation with overlapping group sparsity for Poisson noise removal
- Field of experts regularized nonlocal low rank matrix approximation for image denoising
This page was built for publication: Enhancing sparsity by reweighted \(\ell _{1}\) minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q734955)
