Mostrar el registro sencillo del ítem

Lipschitz bounds for noise robustness in compressive sensing: two algorithms

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorNICODÈME, Marc
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorDOSSAL, Charles
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorTURCU, Flavius
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorBERTHOUMIEU, Yannick
dc.date.accessioned2024-04-04T03:20:42Z
dc.date.available2024-04-04T03:20:42Z
dc.date.created2014-06-30
dc.date.issued2014-11-30
dc.date.conference2014-09-22
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194608
dc.description.abstractEnThe paper deals with estimating the local noise robustness in a compressive sensing framework. We provide two algorithms which estimate, for each vector x that can be recovered by $\ell^1$ minimization, the Lipschitz bounds relating the $\ell^1$-reconstruction error to the measurement error (or noise) for a given sensing matrix. Classical theoretical estimations, such as those based on the restricted isometry property, theoretically give error bounds estimates depending on RIP constants. Unfortunately these RIP assumptions can only be applied for random matrices and are unsuitable for a given deterministic matrix. Other known results applying to deterministic matrices give errors bounds estimates under a small noise assumption, using a semi implicit formula of the solution considering small perturbations of the noiseless $\ell^1$ minimization problem. As an alternative, more recent papers focus on the local behavior of the reconstruction error. One such approach theoretically consists in emphasizing an error bound for each member of a certain family of vectors associated to a local noiseless solution. These vectors are called dual certificates and play a fundamental role in several reconstruction criteria. As such, the theoretical bound estimates based on dual certificates are more versatile, since they are local - hence potentially more accurate - and need no a priori assumptions on the magnitude of the measurement noise. However, as a drawback, finding dual certificates might have a significant computational cost. The paper provides two algorithms for computing dual certificates that minimize their related Lipschitz error bounds, based on two different approaches. The first is a greedy algorithm that provides a fast approximate solution, by minimizing the error bound with respect to a dual certificate. This produces a fast approximation of the optimal bound, since all the numerical computations only rely on scalar products. The second algorithm is based on a theoretical geometric result that describes the exact optimal solution. More precisely we showed that the problem of finding the dual certificate minimizing the error bound can be reduced to computing the convex projection of a suitable vector over a certain convex set. As such, it gives the best error bound but has a higher complexitational cost than the greedy approximation. The two algorithms are illustrated and numerically compared for compressive sensing matrices issued from a tomography application framework. The relationship between theoretical bounds and numerical observed bounds is also discussed.
dc.language.isoen
dc.source.title16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
dc.title.enLipschitz bounds for noise robustness in compressive sensing: two algorithms
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Traitement du signal et de l'image
dc.subject.halSciences de l'ingénieur [physics]/Traitement du signal et de l'image
dc.subject.halInformatique [cs]/Traitement des images
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleInternational Symposium on Symbolic and Numeric Algorithms for Scientific Computing
bordeaux.countryRO
bordeaux.title.proceeding16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
bordeaux.conference.cityTimisoara
bordeaux.peerReviewedoui
hal.identifierhal-01063235
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2014-09-25
hal.popularnon
hal.audienceInternationale
dc.subject.itcompressive sensing Dual certificate sparse minimization l1 minimization tomography
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01063235v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=16th%20International%20Symposium%20on%20Symbolic%20and%20Numeric%20Algorithms%20for%20Scientific%20Computing&rft.date=2014-11-30&rft.au=NICOD%C3%88ME,%20Marc&DOSSAL,%20Charles&TURCU,%20Flavius&BERTHOUMIEU,%20Yannick&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem