The \(\ell_{2,q}\) regularized group sparse optimization: lower bound theory, recovery bound and algorithms
type: Item
instance of: scholarly article
title: The \(\ell_{2,q}\) regularized group sparse optimization: lower bound theory, recovery bound and algorithms
zbMATH Open document ID: 1448.94058
author: X. Feng
author: Shi Yan
author: Chunlin Wu
published in: Applied and Computational Harmonic Analysis
publication date: 2020-06-30T00:00:00Z
review text: This paper deals with the classical problem of signal recovery, namely to restore a vector \(x^{0}\in \mathbb{R}^{N}\) from a noisy observation \(d\). This problem is modeled as \(d=Ax^0+\xi\) where \(A\in \mathbb{R}^{M\times N}\) is the measurement matrix and \(\xi \in \mathbb{R}^M\) represents the measurement error. The authors consider the case where the data to be restored have a natural structure. In particular, they assume that vectors \(x=(x_1,x_2,\ldots ,x_N)\in \mathbb{R}^N\) have a predefined group structure \(x=(x_{\mathcal{G}_1},x_{\mathcal{G}_2},\ldots ,x_{\mathcal{G}_n}),\) where \(\mathcal{G}_i\subset \{1,\ldots ,n\}\) and \(x_{\mathcal{G}_i}\) denotes the \(i\)-th group of \(x\) for \(i\in \{1,2,\ldots,n\}\). In this case, the group sparsity of \(x\) is better measured by a nonconvex \(\ell _{p,q}\) ``norm'', defined by \(||x||_{p,q}:=\left( \sum_{i=1}^n ||x_{\mathcal{G}i}||_p^q \right)^{1/q},\) where \(p\geq 1\) and \(q\in (0,1)\). The authors consider the case \(p=2\) and focus on the minimization of the \(\ell _{p,q}\) regularization: \( \underset{x\in \mathbb{R}^{N}}{\mathrm{min}}\,\left\{||Ax-d||^{2}+||x||_{2,q}^{q}\right\}.\) They provide sufficient conditions for stationary points to be local minimizers and give a uniform lower bound for nonzero groups of local minimizers. They also propose a new IRLS (iteratively reweighted least square) algorithm with thresholding together with an error bound analysis. This new algorithm compares favorably with the classical IRLS algorithm with smoothing in both global convergence and computational efficiency. The paper also contains some numerical experiments.
reviewed by: A. Daniilidis
Mathematics Subject Classification ID: 94A12
Mathematics Subject Classification ID: 62J07
Mathematics Subject Classification ID: 90C26
zbMATH DE Number: 7216377
zbMATH Keywords: group sparsity
zbMATH Keywords: global convergence
zbMATH Keywords: recovery bound
zbMATH Keywords: lower bound IRLS
zbMATH Keywords: signal recovery
describes a project that uses: PDCO
MaRDI profile type: Publication
full work available at URL: j.acha.2020.04.002
OpenAlex ID: W3021333344
cites work: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
cites work: Atomic decomposition by basis pursuit
cites work: Q4864293
cites work: Model Selection and Estimation in Regression with Grouped Variables
cites work: Empirical Bayes Estimation of a Sparse Vector of Gene Expression Changes
cites work: A sparse signal reconstruction perspective for source localization with sensor arrays
cites work: Compressed sensing of color images
cites work: Analysis of multi-stage convex relaxation for sparse regularization
cites work: Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
cites work: Group sparse optimization via $\ell_{p,q}$ regularization
cites work: Decoding by Linear Programming
cites work: Recovery of sparsest signals via \(\ell^q \)-minimization
cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
cites work: Stable signal recovery from incomplete and inaccurate measurements
cites work: Compressed sensing and best 𝑘-term approximation
cites work: The restricted isometry property and its implications for compressed sensing
cites work: Shifting Inequality and Recovery of Sparse Signals
cites work: Simultaneous analysis of Lasso and Dantzig selector
cites work: Error bounds for compressed sensing algorithms with group sparsity: A unified approach
cites work: Robust Recovery of Signals From a Structured Union of Subspaces
cites work: An efficient and globally convergent algorithm for \(\ell_{p,q} - \ell_r\) model in group sparse optimization
cites work: Iteratively reweighted least squares minimization for sparse recovery
cites work: An Unconstrained $\ell_q$ Minimization with $0q\leq1$ for Sparse Solution of Underdetermined Linear Systems
cites work: Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization
cites work: Q5318420
cites work: Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization
cites work: Iterative thresholding for sparse approximations
cites work: The Group Lasso for Logistic Regression
cites work: A new globally convergent algorithm for non-Lipschitz \(\ell_{p}-\ell_q\) minimization
cites work: An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration
cites work: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
cites work: Q5643297
cites work: On gradients of functions definable in o-minimal structures
cites work: The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
cites work: Clarke Subgradients of Stratifiable Functions
cites work: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
cites work: Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
cites work: Proximal alternating linearized minimization for nonconvex and nonsmooth problems
cites work: Geometric categories and o-minimal structures
DOI: 10.1016/J.ACHA.2020.04.002
description: scientific article; zbMATH DE number 7216377