Variantes sur un théorème de Candès, Romberg et Tao

Kahane, Jean-Pierre

Annales de l'Institut Fourier, Tome 63 (2013) no. 6, pp. 2081-2096.

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 à $\mathbb{Z}/N\mathbb{Z}$ 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.

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 $\mathbb{Z}/N\mathbb{Z}$ ; the reconstruction is based on a minimal extrapolation in the Wiener algebra of $\mathbb{Z}/N\mathbb{Z}$ 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.

Classification : 42A05, 42A55, 42A61, 65T50, 94A12, 94A20
Mot clés : Signal, échantillonnage parcimonieux, analyse de Fourier, groupes cycliques, sélection aléatoire, algèbre de Wiener, extrapolation minimale.
Keywords: Signal, compressed sensing, Fourier analysis, cyclic groups, random selection, Wiener algebra, minimal extrapolation

[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