Near-ideal behavior of some compressed sensing algorithms

M. Eren Ahsen, M. Vidyasagar

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A well-known result of Candès and Tao [1] states the following: Suppose x n 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 socalled Restricted Isometry Property (RIP) of order 2k with a coefficient δ2k < √2 - 1. Then one can recover x exactly by minimizing z1 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 η2 ≤ ε, and shows that minimizing z1 subject to y - Az2 ≤ ε leads to an estimate x&Hat whose error x&Hat - x2 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 ℓ1-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.

Original languageEnglish (US)
Title of host publication2014 European Control Conference, ECC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages3
ISBN (Electronic)9783952426913
StatePublished - Jul 22 2014
Externally publishedYes
Event13th European Control Conference, ECC 2014 - Strasbourg, France
Duration: Jun 24 2014Jun 27 2014

Publication series

Name2014 European Control Conference, ECC 2014


Other13th European Control Conference, ECC 2014

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this