DOSSAL, Charles

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

DOSSAL, Charles
Institut de Mathématiques de Bordeaux [IMB]

Idioma

Document de travail - Pré-publication

Resumen en inglés

The minimum $\ell_1$-norm solution to an underdetermined system of linear equations $y = A x$, is often, remarkably, also the sparsest solution to that system. In this paper, we provide a \textit{necessary} and \textit{sufficient} condition for $x$ to be identifiable for a large set of matrices $A$; that is to be the unique sparsest solution to the $\ell_1$-norm minimization problem. Furthermore, we prove that this sparsest solution is stable under a reasonable perturbation of the observations $y$. We also propose an efficient semi-greedy algorithm to check our condition for any vector $x$. We present numerical experiments showing that our condition is able to predict almost perfectly all identifiable solutions $x$, whereas other previously proposed criteria are too pessimistic and fail to identify properly some identifiable vectors $x$. Beside the theoretical proof, this provides empirical evidence to support the sharpness of our condition.< Leer menos

Palabras clave en inglés

identifiable vectors

Sparse representations

underdetermined linear systems

$\ell_1$-minimization

identifiable vectors.

Metadatos

Compartir este ítem

Licencia de uso del documento

A necessary and sufficient condition for exact recovery by l1 minimization.

Idioma

Resumen en inglés

Palabras clave en inglés

URI

Orígen

Centros de investigación