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 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 ; 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.