Dual-density-based reweighted _1-algorithms for a class of _0-minimization problems

DOI10.1007/S10898-021-01013-2MaRDI QIDQ2052391zbMATH OpenOpenAlexFDO

Authors Jialiang Xu, Yun-Bin Zhao

Publication date 26 November 2021

Published in Journal of Global Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.13047

zbMATH Keywords

convex relaxationbilevel optimizationoptimality conditionstrict complementarity\(\ell_0\)-minimizationdual-density-based algorithmmerit functions for sparsity

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30)

Abstract: The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $el{l}_1$-algorithms for a class of $el{l}_0$-minimization models which can be used to model a wide range of practical problems. This class of algorithms is based on certain convex relaxations of the reformulation of the underlying $el{l}_0$-minimization model. Such a reformulation is a special bilevel optimization problem which, in theory, is equivalent to the underlying $el{l}_0$-minimization problem under the assumption of strict complementarity. Some basic properties of these algorithms are discussed, and numerical experiments have been carried out to demonstrate the efficiency of the proposed algorithms. Comparison of numerical performances of the proposed methods and the classic reweighted $el{l}_1$-algorithms has also been made in this paper.

Recommendations

• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Stability analysis of a class of sparse optimization problems
• Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 6438182 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• A new computational method for the sparsest solutions to systems of linear equations
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Compressed sensing
• Compressive sampling
• Concave programming for finding sparse solutions to problems with convex constraints
• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Decoding by Linear Programming
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Fast and Accurate Algorithms for Re-Weighted $\ell _{1}$-Norm Minimization
• Matching pursuits with time-frequency dictionaries
• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• Nonlinear methods of approximation
• Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
• Properties and refinements of the fused Lasso
• Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
• Sparse Recovery of Streaming Signals Using <formula formulatype="inline"><tex Notation="TeX">$\ell_1$</tex></formula>-Homotopy
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Sparse optimization theory and methods
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Spatial smoothing and hot spot detection for CGH data using the fused lasso
• Stability analysis of a class of sparse optimization problems
• Stable signal recovery from incomplete and inaccurate measurements
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Trust, But Verify: Fast and Accurate Signal Recovery From 1-Bit Compressive Measurements

Describes a project that uses

Uses Software

• CoSaMP
• CVX

This page was built for publication: Dual-density-based reweighted \(\ell_1\)-algorithms for a class of \(\ell_0\)-minimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052391)