Near-Ideal Behavior of Compressed Sensing Algorithms
share
In a recent paper, it is shown that the LASSO algorithm exhibits "near-ideal behavior," in the following sense: Suppose y = Az + η where A satisfies the restricted isometry property (RIP) with a sufficiently small constant, and η_2 ≤ϵ. Then minimizing z _1 subject to y - Az _2 ≤ϵ leads to an estimate x̂ whose error x̂ - x _2 is bounded by a universal constant times the error achieved by an "oracle" that knows the location of the nonzero components of x. In the world of optimization, the LASSO algorithm has been generalized in several directions such as the group LASSO, the sparse group LASSO, either without or with tree-structured overlapping groups, and most recently, the sorted LASSO. In this paper, it is shown that any algorithm exhibits near-ideal behavior in the above sense, provided only that (i) the norm used to define the sparsity index is "decomposable," (ii) the penalty norm that is minimized in an effort to enforce sparsity is "γ-decomposable," and (iii) a "compressibility condition" in terms of a group restricted isometry property is satisfied. Specifically, the group LASSO, and the sparse group LASSO (with some permissible overlap in the groups), as well as the sorted ℓ_1-norm minimization all exhibit near-ideal behavior. Explicit bounds on the residual error are derived that contain previously known results as special cases.
READ FULL TEXT