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

\(\ell_0\)-minimizationbilevel optimizationconvex relaxationdual-density-based algorithmmerit functions for sparsityoptimality conditionstrict complementarity

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.

Review text

Let \(A\in \mathbb{R}^{m\times n}\) (with \(m\ll n\)), \(B\in \mathbb{R}^{l\times n}\) (with \(l\leq n\)), \(y\in \mathbb{R}^{m}\), \(b\in \mathbb{R}^{l}\), and \(\epsilon \geq 0\). The \(l_{0}\)-minimization problem considered in this paper consists in minimizing the number of nonzero components of \(x\) subject to \(\left\Vert y-Ax\right\Vert _{2}\leq \epsilon \) and \(Bx\leq b\). To this problem, the authors associate the weighted \(l_{1}\)-minimization problem consisting in minimizing \(w^{T}\left\vert x\right\vert \) subject to the same constraints, \(w\in \mathbb{R}_{+}^{n}\) being a weight vector. Under suitable assumptions, the authors formulate a bilevel optimization problem for obtaining an optimal weight \(w\), propose several convex relaxations of this bilevel problem, present so-called dual-density-based algorithms for solving them, and report the outcomes of some numerical experiments aimed at comparing such algorithms.

Recommendations

• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Reweighted _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

• 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
• 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
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Decoding by Linear Programming
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Fast and Accurate Algorithms for Re-Weighted $\ell _{1}$-Norm Minimization
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 6438182 (Why is no real title available?)
• 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 _1-minimization for sparse solutions to underdetermined linear systems
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Sparse optimization theory and methods
• Sparse Recovery of Streaming Signals Using <formula formulatype="inline"><tex Notation="TeX">$\ell_1$</tex></formula>-Homotopy
• 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)