- Acquisition comprimée
-
L'Acquisition compressée est une technique permettant de trouver une solution éparse aux systèmes linéaires sous-déterminés. Compressed sensing, également appelé Compressive sensing, Compressed Sampling ou encore Sparse Sampling en anglais.Histoire
Plusieurs disciplines scientifiques utilisent les techniques de l'espace L1[1]. En statistique, la méthode des moindres carrés a été complétée par la norme L1 introduite par Laplace. Après l'introduction de la programmation linéaire et de l'algorithme du simplexe de George Dantzig la norme L1 a été utilisée en statistique numérique. En théorie statistique la norme L1 a été utilisée par George Brown et plus tard elle servit à définir des estimateurs non-biaisés de la médiane. Elle a été utilisé par Peter Huber et d'autres dans leurs travaux sur les statistiques robustes. Dans les années 70, la norme L1 a été utilisée par les sismologues pour analyser les données de réflexions d'ondes entre les couches de l'écorce terrestre lorsqu'elles ne semblaient pas respecter les conditions du théorème d'échantillonnage de Nyquist-Shannon[2]. Toujours en traitement du signal elle a été introduite en 1993 dans l'algorithme « Matching Pursuit » et dans l'estimateur LASSO par Robert Tibshirani en 1996[3] et « Basis Pursuit » en 1998[4]. Des résultats théoriques permettaient de savoir quand ces algorithmes permettaient de retrouver des solutions éparses, mais le type et le nombre de mesures requis pour cela était sous-optimaux et l'algorithme d'acquisition comprimée a permis une amélioration sensible de ce domaine du traitement du signal. Vers 2004 Emmanuel Candès, Terence Tao et David Donoho découvrirent des résultats importants sur le nombre minimum de données nécessaires à la reconstruction d'une image qui apparut plus petit que le nombre minimum déterminé par le critère de Nyquist-Shannon[5],[6].
Méthodes de reconstruction
Notes et références
- List of L1 regularization ideas from Vivek Goyal, Alyson Fletcher, Sundeep Rangan, The Optimistic Bayesian: Replica Method Analysis of Compressed Sensing
- Hayes, Brian, The Best Bits, American Scientist, July 2009
- The Lasso page, at Robert Tibshirani's homepage. "Regression shrinkage and selection via the lasso". J. Royal. Statist. Soc B., Vol. 58, No. 1, pages 267-288
- "Atomic decomposition by basis pursuit", by Scott Shaobing Chen, David L. Donoho, Michael, A. Saunders. SIAM Journal on Scientific Computing
- E. J. Candès, J. Romberg and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59 1207-1223 (www-stat.stanford.edu) [PDF]
- Donoho, D. L., Compressed Sensing, IEEE Transactions on Information Theory, V. 52(4), 1289–1306, 2006 (ieeexplore.ieee.org)
Wikimedia Foundation. 2010.
