Description of the Minimizers of Least Squares Regularized with ₀-norm. Uniqueness of the Global Minimizer

We have an M×N real-valued arbitrary matrix A (e.g., a dictionary) with M<N and data d describing the sought-after object with the help of A. This work provides an in-depth analysis of the (local and global) minimizers of an objective function Fd combining a quadratic data-fidelity term and an ₀ penalty applied to each entry of the sought-after solution, weighted by a regularization parameter β>0. For several decades, this objective has attracted a ceaseless effort to conceive algorithms approaching a good minimizer. Our theoretical contributions, summarized below, shed new light on the existing algorithms and can help in the conception of innovative numerical schemes. Solving the normal equation associated with any M-row submatrix of A is equivalent to computing a local minimizer u of Fd. (Local) minimizers u of Fd are strict if and only if the submatrix, composed of those columns of A whose indices form the support of u, has full column rank. An outcome is that strict local minimizers of Fd are easily computed without knowing the value of β. Each strict local minimizer is linear in data. It is proved that Fd has global minimizers and that they are always strict. They are studied in more detail under the (standard) assumption that rank(A)=M<N. The global minimizers with M-length support are seen to be impractical. Given d, critical values β_K for any KM-1 are exhibited such that if β>β_K, all global minimizers of Fd are K-sparse. An assumption on A is adopted and proved to fail only on a closed negligible subset. Then for all data d beyond a closed negligible subset, the objective Fd for β>β_K, KM-1, has a unique global minimizer, and this minimizer is K-sparse. Instructive small-size (5× 10) numerical illustrations confirm the main theoretical results.