Description of the minimizers of least squares regularized~ with~ ℓ0\bm{\ell_0}-norm. Uniqueness of the global minimizer

preprint2013arXivOpen access

Abstract

We have an $\m\x\n$ real-valued arbitrary matrix AA (e.g. a dictionary) with $\m<\n$ and data dd describing the sought-after object with the help of AA. 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 ℓ0\ell_0 penalty applied to each entry of the sought-after solution, weighted by a regularization parameter $\be>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 the conception of innovative numerical schemes. To solve the normal equation associated with any $\m$-row submatrix of AA is equivalent to compute a local minimizer $\hu$ of $\Fd$. (Local) minimizers $\hu$ of $\Fd$ are strict if and only if the submatrix, composed of those columns of AA whose indexes form the support of $\hu$, has full column rank. An outcome is that strict local minimizers of $\Fd$ are easily computed without knowing the value of $\be$. 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 details under the (standard) assumption that $\rank(A)=\m<\n$. The global minimizers with $\m$-length support are seen to be impractical. Given dd, critical values $\be_\k$ for any $\k\leq\m-1$ are exhibited such that if $\be>\be_\k$, all global minimizers of $\Fd$ are $\k$-sparse. An assumption on AA is adopted and proved to fail only on a closed negligible subset. Then for all data dd beyond a closed negligible subset, the objective $\Fd$ for $\be>\be_\k$, $\k\leq\m-1$, has a unique global minimizer and this minimizer is $\k$-sparse. Instructive small-size ($5\x 10$) numerical illustrations confirm the main theoretical results.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.