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

DOI10.1007/S10898-021-01013-2zbMATH Open1500.90074arXiv2003.13047OpenAlexW3154048545MaRDI QIDQ2052391FDOQ2052391

Authors: Jialiang Xu, Yun-Bin Zhao 

Publication date: 26 November 2021

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

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.

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

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

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)

Cites Work

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

Uses Software

• CVX
• CoSaMP

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)