Show simple item record

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorDOSSAL, Charles
dc.date.accessioned2024-04-04T02:26:16Z
dc.date.available2024-04-04T02:26:16Z
dc.date.created2011-11-25
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189948
dc.description.abstractEnThe 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.isoen
dc.subject.enidentifiable vectors
dc.subject.enSparse representations
dc.subject.enunderdetermined linear systems
dc.subject.en$\ell_1$-minimization
dc.subject.enidentifiable vectors.
dc.title.enA necessary and sufficient condition for exact recovery by l1 minimization.
dc.typeDocument de travail - Pré-publication
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-00164738
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00164738v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=DOSSAL,%20Charles&rft.genre=preprint


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record