New insights into one-norm solvers from the Pareto curve

Solution paths

plot
Figure 2. Pareto curve and solution paths (large enough number of iterations) of four solvers for a BP$_0$ problem. The symbols + represent a sampling of the Pareto curve. The solid (--) line, obscured by the Pareto curve, is the solution path of ISTc, the chain (- $\cdot$ -) line the path of SPGL$\ell _1$ , the dashed (- -) line the path of IST, and the dotted ($\cdots$ ) line the path of IRLS.

Figure 2 shows the solution paths of the four solvers as they converge to the BP$_0$ solution. The starting vector provided to each solver is the zero vector, and hence the paths start at $(0,\Vert\ensuremath{\mathbf{y}}\Vert _2)$ --point in Figure 1. The number of iterations is large enough for each solver to converge, and therefore the solution paths end at $(\tau_{_{BP_0}},0)$ --point in Figure 1.

The two solvers SPG$\ell _1$ and ISTc approach the BP$_0$ solution from the left and remain close to the Pareto curve. In contrast, IST and IRLS aim at a least-squares solution before turning back towards the BP$_0$ solution. ISTc solves QP$_\lambda$ for a decreasing sequence $\lambda_i\to0$ . The starting vector for QP $_{\lambda_{i}}$ is the solution of QP $_{\lambda_{i-1}}$ , which is by definition on the Pareto curve. This explains why ISTc so closely follows the curve. SPG$\ell _1$ solves a sequence of LS$_\tau$ problems for an increasing sequence of $\tau_i\to\tau_{_{BP_0}}$ , hence the vertical segments along the SPG$\ell _1$ solution path. IST solves QP$_{0^+}$ . Because there is hardly any regularization, IST first works towards minimizing the data misfit. When the data misfit is sufficiently small, the effect of the one-norm penalization starts, yielding a change of direction towards the BP$_0$ solution. IRLS solves a sequence of weighted, damped, least-squares problems. Because the weights are initialized to ones, IRLS first reaches the standard least-squares solution. The estimates obtained from the subsequent reweightings have a smaller one norm while maintaining the residual (close) to zero. Eventually, IRLS gets to the BP$_0$ solution.

New insights into one-norm solvers from the Pareto curve