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

Abstract

Variations on a theorem of Candès, Romberg and Tao 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 Z/N Z; the reconstruction is based on a minimal extrapolation in the Wiener algebra of Z/N 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.

arXiv commentA paraître aux Annales de l'Institut Fourier en 2013