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, p. 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 : https://doi.org/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
@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},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {63},
     number = {6},
     year = {2013},
     pages = {2081-2096},
     doi = {10.5802/aif.2823},
     mrnumber = {3237441},
     zbl = {06325427},
     language = {fr},
     url = {http://www.numdam.org/item/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/item/AIF_2013__63_6_2081_0/

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

[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, Tome 52 (2006) no. 2, pp. 489-509 | Article | MR 2236170 | Zbl 1231.94017

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

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

[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, Tome 349 (2011), pp. 1073-1076 | Zbl 1231.94044

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