New insights into one-norm solvers from the Pareto curve

Comparison of one-norm solvers

To illustrate the usefulness of the Pareto curve, we compare IST, ISTc, SPG$\ell _1$ , and IRLS on a noise-free problem and compute a solution of BP$_\sigma$ for $\sigma =0$ , i.e., BP$_0$ . This case is especially challenging for solvers that attack QP$_\lambda$ --e.g., IST, ISTc and IRLS--because the corresponding solution can only be attained in the limit as $\lambda\to0$ .

We construct a benchmark problem that is typically used in the compressed sensing literature (Donoho et al., 2006). The matrix $\tensor{A}$ is taken to have Gaussian independent and identically-distributed entries; a sparse solution $\ensuremath{\mathbf{x}}_0$ is randomly generated, and the ``observations'' $\ensuremath{\mathbf{y}}$ are computed according to equation 1.