Unknown sparsity in compressed sensing: Denoising and inference

Abstract

The theory of Compressed Sensing (CS) asserts that an unknown signal $x\in {\mathbb{R}}^p$ can be accurately recovered from an underdetermined set of $n$ linear measurements with $n\ll p$, provided that $x$ is sufficiently sparse. However, in applications, the degree of sparsity $\Vert x{\Vert }_0$ is typically unknown, and the problem of directly estimating $\Vert x{\Vert }_0$ has been a longstanding gap between theory and practice. A closely related issue is that $\Vert x{\Vert }_0$ is a highly idealized measure of sparsity, and for real signals with entries not equal to 0, the value $\Vert x{\Vert }_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, $\Vert x{\Vert }_1^2/\Vert x{\Vert }_2^2$, and designed a procedure to estimate $\Vert x{\Vert }_1^2/\Vert x{\Vert }_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 $s_q(x):=(\frac{\Vert x{\Vert }_q}{\Vert x{\Vert }_1}{)}^{\frac{q}{1-q}}$ parameterized by $q\in [0,\infty ]$. This family interpolates between $\Vert x{\Vert }_0=s_0(x)$ and $\Vert x{\Vert }_1^2/\Vert x{\Vert }_2^2=s_2(x)$ as $q$ ranges over $[0,2]$. For any $q\in (0,2]\setminus \{1\}$, we propose an estimator ${\hat{s}}_q(x)$ whose relative error converges at the dimension-free rate of $1/\sqrt{n}$, even when $p/n\to \infty$. 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.

The title of the previous tech report has been updated so that it matches the published version. The published version contains additional material

References in corpus (9)

• The Convex Geometry of Linear Inverse Problems
• Generalized SURE for Exponential Families: Applications to Regularization
• Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
• LDPC Codes for Compressed Sensing
• Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed l1/l2 Regularization
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization
• A new perspective on least squares under convex constraint
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values

Cited by in corpus (3)

• SPOQ ${\ell }_p$-Over-${\ell }_q$ Regularization for Sparse Signal Recovery applied to Mass Spectrometry
• Communication-Efficient Distributed SGD with Compressed Sensing
• Enhanced block sparse signal recovery based on $q$-ratio block constrained minimal singular values