TY - GEN

T1 - Near-ideal behavior of some compressed sensing algorithms

AU - Ahsen, M. Eren

AU - Vidyasagar, M.

PY - 2014/7/22

Y1 - 2014/7/22

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

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

UR - http://www.scopus.com/inward/record.url?scp=84911465179&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84911465179&partnerID=8YFLogxK

U2 - 10.1109/ECC.2014.6862520

DO - 10.1109/ECC.2014.6862520

M3 - Conference contribution

AN - SCOPUS:84911465179

T3 - 2014 European Control Conference, ECC 2014

SP - 2216

EP - 2218

BT - 2014 European Control Conference, ECC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 13th European Control Conference, ECC 2014

Y2 - 24 June 2014 through 27 June 2014

ER -