Unknown sparsity in compressed sensing: Denoising and inference

Abstract

The theory of Compressed Sensing (CS) asserts that an unknown signal xR^p can be accurately recovered from an underdetermined set of n linear measurements with n p, 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 s_q(x):=(\|x\|_q\|x\|_1)^q1-q parameterized by q[0,]. 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 q (0,2]\1\, we propose an estimator s_q(x) whose relative error converges at the dimension-free rate of 1/n, even when p/n. Our main results also describe the limiting distribution of s_q(x), as well as some connections to Basis Pursuit Denosing, the Lasso, deterministic measurement matrices, and inference problems in CS.

Tasks

Reproductions