Compressed Sensing over ℓp-balls: Minimax mean square error

We consider the compressed sensing problem where the object x 0 ∈ ℝ N is to be recovered from incomplete measurements y = Ax 0 +z. Here the sensing matrix A is an n×N random matrix with Gaussian entries and n <; N. A popular method of sparsity-promoting reconstruction is ℓ 1 -penalized least-squares reconstruction (aka LASSO, Basis Pursuit). Suppose that x ο is sparse in the sense of having ℓ ρ norm bounded by ξ · N 1/ρ for some fixed 0 <; p ≤ 1 and radius ξ >; 0. In both the noisy (z i iid N(0, σ 2 )) and noiseless (z = 0) cases, we evaluate the worst-case asymptotic mean square error (AMSE) for optimally tuned ℓ 1 penalized least-squares, and we exhibit the least-favorable object x ο (hardest sparse signal to recover) and the maximin penalization. Our explicit formulas yield precise relations. For example, in the noiseless case z = 0, for vectors x ο of ℓ ρ norm bounded by 1, we show that mm max∥ x̑ λ - x 0 ∥ 2 = n 1-2/p (2log(N/n)) 2/p-1 {1+o N (l)} where n, N → ∞, n/N → 0 slowly. The complete formulas applies to a general scaling limit n/N → δ and sparsity parameter ξ, and unexpectedly involve quantities from statistical decision theory. This reflects a deep connection between ℓ 1 -penalized ℓ 2 minimization and scalar soft thresholding.