Lipschitz bounds for noise robustness in compressive sensing: two algorithms
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Laboratoire de l'intégration, du matériau au système [IMS] | |
| dc.contributor.author | NICODÈME, Marc | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | DOSSAL, Charles | |
| hal.structure.identifier | Laboratoire de l'intégration, du matériau au système [IMS] | |
| dc.contributor.author | TURCU, Flavius | |
| hal.structure.identifier | Laboratoire de l'intégration, du matériau au système [IMS] | |
| dc.contributor.author | BERTHOUMIEU, Yannick | |
| dc.date.accessioned | 2024-04-04T03:20:42Z | |
| dc.date.available | 2024-04-04T03:20:42Z | |
| dc.date.created | 2014-06-30 | |
| dc.date.issued | 2014-11-30 | |
| dc.date.conference | 2014-09-22 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194608 | |
| dc.description.abstractEn | The 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.iso | en | |
| dc.source.title | 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing | |
| dc.title.en | Lipschitz bounds for noise robustness in compressive sensing: two algorithms | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Traitement du signal et de l'image | |
| dc.subject.hal | Sciences de l'ingénieur [physics]/Traitement du signal et de l'image | |
| dc.subject.hal | Informatique [cs]/Traitement des images | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | International Symposium on Symbolic and Numeric Algorithms for Scientific Computing | |
| bordeaux.country | RO | |
| bordeaux.title.proceeding | 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing | |
| bordeaux.conference.city | Timisoara | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01063235 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2014-09-25 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| dc.subject.it | compressive sensing Dual certificate sparse minimization l1 minimization tomography | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01063235v1 | |
| bordeaux.COinS | ctx_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 |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||