The Sample Complexity of WeightedSparse Approximation

DOI10.1109/TSP.2016.2543211zbMATH Open1414.94049arXiv1507.06736MaRDI QIDQ4619617FDOQ4619617

Authors: Bubacarr Bah, Rachel Ward 

Publication date: 7 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: For Gaussian sampling matrices, we provide bounds on the minimal number of measurements $m$ required to achieve robust weighted sparse recovery guarantees in terms of how well a given prior model for the sparsity support aligns with the true underlying support. Our main contribution is that for a sparse vector $$ supported on an unknown set $mathcalSsubset1,dots,N$ with $|mathcalS|leqk$, if $mathcalS$ has emph{weighted cardinality} $omega(mathcalS):=su{m}_{jinmathcalS}omeg{a}_j^2$, and if the weights on $mathcal{S}^c$ exhibit mild growth, $omeg{a}_j^{2}geqgammalog(j/omega(mathcalS))$ for $jinmathcal{S}^c$ and $gamma>0$, then the sample complexity for sparse recovery via weighted $el{l}_1$-minimization using weights $omeg{a}_j$ is linear in the weighted sparsity level, and $m=mathcalO(omega(mathcalS)/gamma)$. This main result is a generalization of special cases including a) the standard sparse recovery setting where all weights $omeg{a}_{j}equiv1$, and $m=mathcalOleft(klogleft(N/kight)ight)$; b) the setting where the support is known a priori, and $m=mathcalO(k)$; and c) the setting of sparse recovery with prior information, and $m$ depends on how well the weights are aligned with the support set $mathcalS$. We further extend the results in case c) to the setting of additive noise. Our results are {em nonuniform} that is they apply for a fixed support, unknown a priori, and the weights on $mathcalS$ do not all have to be smaller than the weights on $mathcal{S}^c$ for our recovery results to hold.

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (6)

• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• Sufficient conditions on stable reconstruction of weighted problem
• Stable recovery of weighted sparse signals from phaseless measurements via weighted l₁ minimization
• Robust recovery of a kind of weighted l1-minimization without noise level
• New conditions on stable recovery of weighted sparse signals via weighted \(l_1\) minimization
• Recovery of signals under the condition on RIC and ROC via prior support information

This page was built for publication: The Sample Complexity of Weighted<?Pub _newline ?>Sparse Approximation

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