Near-ideal behavior of some compressed sensing algorithms

A well-known result of Candès and Tao [1] states the following: Suppose x ∈ ℝⁿ and has at most k nonzero components, but the location of the nonzero components is not known. Suppose A is an m × n matrix that satisfies the so-called Restricted Isometry Property (RIP) of order 2k with a coefficient δ_2k <; √2 - 1. Then one can recover x exactly by minimizing ∥z∥₁ subject to Az = y = Ax. A later paper by Candès [2] - see also [3] - studies the case of noisy measurements with y = Az + η where ∥η∥₂ ≤ ε, and shows that minimizing ∥z∥₁ subject to ∥y - Az∥₂ ≤ ε leads to an estimate x̂ whose error ∥x̂ - x∥₂ is bounded by a universal constant times the error achieved by an “oracle” that knows the location of the nonzero components of x. This is called “near ideal behavior” in [4], where a closely related problem is studied. The minimization of the ℓ₁-norm is closely related to the LASSO algorithm, which in turn is a special case of the Sparse Group LASSO (SGL) algorithm. In this paper, it is shown that both SGL, and an important special case of SGL introduced here called Modified Elastic Net (MEN), exhibit near ideal behavior.