• Albert COHEN
• Wolfgang DAHMEN
• Ronald DEVORE

Code(s) de Classification MSC:

Code(s) de Classification CR:

Résumé: Nous discutons le problème de reconstruction exacte ou approchée d'un signal à partir d'un petit nombre de mesure linéaires fixées à l'avance (compressed sensing) et comparons la performance de cette reconstruction avec celle de l'approximation non-linéaire à k-terme du signal.

Abstract: Compressed sensing is a new concept in signal processing where one seeks to minimize the number of measurements to be taken from signals while still retaining
the information necessary to approximate them well. The ideas have their origins in certain abstract results from functional analysis and approximation theory by Kashin [15] but were recently brought into the forefront by the work of Candès, Romberg and Tao [5, 3, 4] and Donoho [9] who constructed concrete algorithms and showed their promise in application. There remain several fundamental questions on both the theoretical and practical side of compressed sensing. This paper is primarily concerned about one of these theoretical issues revolving around just how well compressed sensing can approximate a given signal from a given budget of fixed linear measurements, as compared to adaptive linear measurements. More precisely, we consider discrete signals x∈R^N, allocate n linear measurements of x, and we describe the range of k for which these measurements encode enough information to recover x in the sense of l_p to the accuracy of best k-term approximation. We also consider the problem of having such accuracy only with high probability.

Mots Clés: ;

Date: 2007-12-27