FoCM 2014 conference
Workshop A2 - Computational Harmonic Analysis, Image and Signal Processing
December 11, 16:00 ~ 16:25 - Room C21
Least squares regularized or constrained by $L_0$: relationship between their optimal solutions and properties
Mila Nikolova
CMLA -- CNRS ENS-Cachan, France - nikolova@cmla.ens-cachan.fr
When looking for a sparse solution of an under-determined linear system, two popular options are to find the optimal solution of the least squares regularized by $L_0$ pseudo-norm using a trade-off parameter $\beta$ or constrained by $L_0$ (known also as the $K$-sparsity constrained problem).
We provide important features of the optimal solutions of both problems. We analyse in depth the relationship between the sets of optimal solutions of these two nonconvex (combinatorial) models. A general quasi-equivalence between these problems is established in the sense explained next. There exists a strictly decreasing sequence of critical values $\{\beta_k\}$ that partitions the positive axis into a certain number of intervals. For every $\beta$ inside the $K$-th interval, the regularized problem and the $K$-constrained problem share exactly the same set of optimal solutions. For $\beta=\beta_k$, the optimal set of the regularized problem is composed of the optimal solutions of the $K$-constrained problem and the constrained problem corresponding to the next interval (and possibly a few others in-between). All $\beta_k$'s are obtained from the optimal values of the constrained problems. The strict decay of $\{\beta_k\}$ is a necessary and sufficient condition. We will present all important points concerning this quasi-equivalence.
Small-size exact numerical tests illustrate the theoretical results. By way of conclusion, the $K$-sparsity problem offers wider possibilities which is not necessarily an advantage.