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

Kahane, Jean-Pierre

Annales de l'Institut Fourier, Tome 63 (2013), p. 2081-2096 / Harvested from Numdam

Résumé

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 $C s \log N$ 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.

Abstract

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 $C s \log N$ 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.

Détail

Publié le : 2013-01-01

MR 3237441 | Zbl 06325427

DOI : https://doi.org/10.5802/aif.2823
Classification:  42A05,  42A55,  42A61,  65T50,  94A12,  94A20
Mots clés: Signal, échantillonnage parcimonieux, analyse de Fourier, groupes cycliques, sélection aléatoire, algèbre de Wiener, extrapolation minimale.

Bibliographie

[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