A necessary and sufficient condition for exact recovery by l1 minimization.
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | DOSSAL, Charles | |
| dc.date.accessioned | 2024-04-04T02:26:16Z | |
| dc.date.available | 2024-04-04T02:26:16Z | |
| dc.date.created | 2011-11-25 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189948 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | identifiable vectors | |
| dc.subject.en | Sparse representations | |
| dc.subject.en | underdetermined linear systems | |
| dc.subject.en | $\ell_1$-minimization | |
| dc.subject.en | identifiable vectors. | |
| dc.title.en | A necessary and sufficient condition for exact recovery by l1 minimization. | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-00164738 | |
| hal.version | 1 | |
| hal.audience | Non spécifiée | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00164738v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=DOSSAL,%20Charles&rft.genre=preprint |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||