Dual-density-based reweighted \(\ell_1\)-algorithms for a class of \(\ell_0\)-minimization problems (Q2052391)

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.