Near-Ideal Behavior of Compressed Sensing Algorithms
This provides a theoretical foundation for sparsity-enforcing algorithms in signal processing and machine learning, but it is incremental as it extends known results to broader conditions.
The paper tackles the problem of establishing near-ideal error bounds for compressed sensing algorithms, showing that any algorithm with decomposable norms and compressibility conditions achieves error within a constant factor of an oracle that knows the sparsity pattern, generalizing previous results like LASSO to methods such as group LASSO and sorted L1-norm minimization.
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 $\Vert η\Vert_2 \leq ε$. Then minimizing $\Vert z \Vert_1$ subject to $\Vert y - Az \Vert_2 \leq ε$ leads to an estimate $\hat{x}$ whose error $\Vert \hat{x} - x \Vert_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 {\it 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 $\ell_1$-norm minimization all exhibit near-ideal behavior. Explicit bounds on the residual error are derived that contain previously known results as special cases.