Unknown Sparsity in Compressed Sensing: Denoising and Inference

The theory of compressed sensing (CS) asserts that an unknown signal x ϵ Rp 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 IlxIl0is typically unknown, and the problem of directly estimating IlxIl0has been a longstanding gap between theory and practice. A closely related issue is that IlxIl0is a highly idealized measure of sparsity, and for real signals with entries not equal to 0, the value IlxIl0= p is not a useful description of compressibility. In our previous conference paper [1] that examined these problems, we considered an alternative measure of soft sparsity, IlxIl12/IlxIl22, and designed a procedure to estimate IlxIl12/IlxIl22that does not rely on sparsity assumptions. This paper 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 sq(x) = (IlxIlq/IlxIl1)(q/1-q)parameterized by q ϵ [0, ∞]. This family interpolates between IlxIl0= sq(x) and IlxIl12/IlxIl22= s2(x) as q ranges over [0, 2]. For any q ϵ (0, 2] \ 111, we propose an estimator ŝ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 ŝq(x), as well as some connections to basis pursuit denosing, the Lasso, deterministic measurement matrices, and inference problems in CS.