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

We consider the compressed sensing problem where the object x₀ ∈ ℝ^N is to be recovered from incomplete measurements y = Ax₀+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 ℓ¹-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, σ²)) and noiseless (z = 0) cases, we evaluate the worst-case asymptotic mean square error (AMSE) for optimally tuned ℓ¹ 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₀∥² = 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 ℓ₁-penalized ℓ₂ minimization and scalar soft thresholding.