Variantes sur un théorème de Candès, Romberg et Tao
[Variations on a theorem of Candès, Romberg and Tao]
Annales de l'Institut Fourier, Volume 63 (2013) no. 6, pp. 2081-2096.

The CRT theorem reconstructs a signal from a sparse set of frequencies, a paradigm of Compressed sensing. The signal is assumed to be carried by a small number of points, s , in a large cyclic set, of order N ; the frequencies consist of CslogN points chosen randomly in /N ; the reconstruction is based on a minimal extrapolation in the Wiener algebra of /N of the restriction of the Fourier transform of the signal to the chosen set of frequencies. The probability of reconstructing the signal is nearly 1 when C is large. The statement should be modified when we want all signals carried by s points to be reconstructed in that way. The CRT approach is based on random matrices, here the approach is classical Fourier analysis.

Le théorème CRT dit comment reconstruire un signal à partir d’un échantillonnage de fréquences parcimonieux. L’hypothèse sur le signal, considéré comme porté par un groupe cyclique d’ordre N, est qu’il est porté par un petit nombre de points, s, et la méthode est de choisir aléatoirement CslogN fréquences et de minimiser dans l’algèbre de Wiener le prolongement à /N de la transformée de Fourier du signal réduite à ces fréquences. Quand C est grand, la probabilité de reconstruire le signal est voisine de 1. L’énoncé doit être modifié si l’on veut que l’échantillonnage convienne à tout signal porté par s points. La démonstration de CRT repose sur des matrices aléatoires, celle que présente le présent article, avec des résultats voisins mais différents, est d’analyse de Fourier classique.

DOI: 10.5802/aif.2823
Classification: 42A05,  42A55,  42A61,  65T50,  94A12,  94A20
Keywords: Signal, compressed sensing, Fourier analysis, cyclic groups, random selection, Wiener algebra, minimal extrapolation
Kahane, Jean-Pierre 1

1 Laboratoire de Mathématiques Université Paris–Sud 91405 Orsay cedex (France)
@article{AIF_2013__63_6_2081_0,
     author = {Kahane, Jean-Pierre},
     title = {Variantes sur un th\'eor\`eme de {Cand\`es,} {Romberg} et {Tao}},
     journal = {Annales de l'Institut Fourier},
     pages = {2081--2096},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {63},
     number = {6},
     year = {2013},
     doi = {10.5802/aif.2823},
     mrnumber = {3237441},
     zbl = {06325427},
     language = {fr},
     url = {http://www.numdam.org/articles/10.5802/aif.2823/}
}
TY  - JOUR
AU  - Kahane, Jean-Pierre
TI  - Variantes sur un théorème de Candès, Romberg et Tao
JO  - Annales de l'Institut Fourier
PY  - 2013
DA  - 2013///
SP  - 2081
EP  - 2096
VL  - 63
IS  - 6
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.2823/
UR  - https://www.ams.org/mathscinet-getitem?mr=3237441
UR  - https://zbmath.org/?q=an%3A06325427
UR  - https://doi.org/10.5802/aif.2823
DO  - 10.5802/aif.2823
LA  - fr
ID  - AIF_2013__63_6_2081_0
ER  - 
%0 Journal Article
%A Kahane, Jean-Pierre
%T Variantes sur un théorème de Candès, Romberg et Tao
%J Annales de l'Institut Fourier
%D 2013
%P 2081-2096
%V 63
%N 6
%I Association des Annales de l’institut Fourier
%U https://doi.org/10.5802/aif.2823
%R 10.5802/aif.2823
%G fr
%F AIF_2013__63_6_2081_0
Kahane, Jean-Pierre. Variantes sur un théorème de Candès, Romberg et Tao. Annales de l'Institut Fourier, Volume 63 (2013) no. 6, pp. 2081-2096. doi : 10.5802/aif.2823. http://www.numdam.org/articles/10.5802/aif.2823/

[1] Candès, Emmanuel J. Compressive Sampling, Proceedings of the International Congress of Mathematicians, Madrid 2006, Volume III, EMS-ph, pp. 1433-1452 | MR | Zbl

[2] Candès, Emmanuel J.; Romberg, J.; Tao, T. Robust Uncertainty Principles : Exact Signal Reconstruciton From Highly Incomplete Frequency Information, IEEE Transactions on Information Theory, Volume 52 (2006) no. 2, pp. 489-509 | DOI | MR | Zbl

[3] Candès, Emmanuel J.; Romberg, J.; Tao, T. Stable signal recovery from incomplete and inaccurate measurements, Communications in Pure and Applied Mathematics, Volume 59 (2006) no. 8, pp. 1207-1223 | DOI | MR | Zbl

[4] Candès, Emmanuel J.; Tao, T. Near optimal signal recovery from random projections : universal encoding strategies, IEEE Transactions on Information Theory, Volume 52 (2006) no. 12, pp. 5406-5425 | DOI | MR

[5] Cohen, A. Communication orale lors du colloque de décembre 2011 au Centre de recerca matemática (CRM) de l’Université autonome de Barcelone (ICREA Conference on Approximation Theory and Fourier Analysis)

[6] Kahane, J.-P. Idempotents et échantillonnage parcimonieux, Comptes rendus de l’Académie des sciences de Paris. série 1, Volume 349 (2011), pp. 1073-1076 | Zbl

[7] Kahane, J.-P. Analyse et synthèse harmonique (Histoires de mathématiques (Journéees X–UPS 2011)), École Polytechnique, Palaiseau, 2012, pp. 17-53 | Zbl

Cited by Sources: