Unknown Sparsity in Compressed Sensing: Denoising and Inference

DOI10.1109/TIT.2016.2587772MaRDI QIDQ2976642zbMATH OpenFDO

Authors Miles E. Lopes

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: The theory of Compressed Sensing (CS) asserts that an unknown signal $xinmathbb{R}^p$ can be accurately recovered from an underdetermined set of $n$ linear measurements with $nllp$, provided that $x$ is sufficiently sparse. However, in applications, the degree of sparsity $|x{|}_0$ is typically unknown, and the problem of directly estimating $|x{|}_0$ has been a longstanding gap between theory and practice. A closely related issue is that $|x{|}_0$ is a highly idealized measure of sparsity, and for real signals with entries not equal to 0, the value $|x{|}_0=p$ is not a useful description of compressibility. In our previous conference paper [Lop13] that examined these problems, we considered an alternative measure of "soft" sparsity, $|x{|}_1^2/|x{|}_2^2$, and designed a procedure to estimate $|x{|}_1^2/|x{|}_2^2$ that does not rely on sparsity assumptions. The present work offers a new deconvolution-based method for estimating unknown sparsity, which has wider applicability and sharper theoretical guarantees. In particular, we introduce a family of entropy-based sparsity measures $$ parameterized by $qin[0,infty]$. This family interpolates between $|x{|}_0=s_0(x)$ and $|x{|}_1^2/|x{|}_2^2=s_2(x)$ as $q$ ranges over $[0,2]$. For any $qin(0,2]setminus1$, we propose an estimator $hat{s}_q(x)$ whose relative error converges at the dimension-free rate of $1/sqrtn$, even when $p/noinfty$. Our main results also describe the limiting distribution of $hat{s}_q(x)$, as well as some connections to Basis Pursuit Denosing, the Lasso, deterministic measurement matrices, and inference problems in CS.

Cited in

(8)

• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• Estimation of block sparsity in compressive sensing
• A bootstrap method for spectral statistics in high-dimensional elliptical models
• Sparse signal reconstruction via collaborative neurodynamic optimization
• Point process simulation of generalised hyperbolic Lévy processes
• Point process simulation of generalised inverse Gaussian processes and estimation of the Jaeger integral
• Sparse recovery: the square of \(\ell_1/\ell_2\) norms
• Structured iterative hard thresholding with on- and off-grid applications

This page was built for publication: Unknown Sparsity in Compressed Sensing: Denoising and Inference

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