zbMATH — the first resource for mathematics

Variations on a theorem of Candès, Romberg and Tao. (Variantes sur un théorème de Candès, Romberg et Tao.) (French. English summary) Zbl 1306.42006
The problem considered in the pioneering work of Candès, Romberg and Tao in compressive sampling is that of reconstructing a signal from incomplete, sparse frequency samples. In Fourier analytic terms, the CRT-theorem considered in the paper under review can be described as follows:
CRT theorem: Let $$G$$ denote the group $$\mathbb{Z}_N:= \mathbb{Z}/N\mathbb{Z}$$ ($$N$$ large), with dual group $$\widehat{G}$$. Suppose that the signal $$x\in \ell^1(G)$$ is supported on a set of cardinality $$s$$ ($$s$$ small). Let $$\Omega\subset \widehat{G}$$ be a random set of frequencies (satisfying a suitable probabilistic condition). For a given ‘accuracy parameter’ $$M$$, if $$|\Omega| > C(M) s \log N$$, then, with probability $$1-O(N^{-M})$$, the problem $\min \{\|y\|_1: \hat{y}|_{\Omega}=\hat{x}|_{\Omega}\}$ has a unique minimiser and the minimiser is $$x$$.
Note that the theorem is concerned with the reconstruction of a single signal. The paper under review also deals with variants of this result and is concerned with the condition: $$\hat{x}$$ is the minimal extension of $$\hat{x}|_{\Omega }$$ in $$A(\widehat{G}):= \mathcal{F}\ell^1(G)$$. Can all signals with the same support be reconstructed? Can all signals supported on $$s$$ points be reconstructed? How to choose $$\Omega$$ and what are the corresponding probabilistic estimates? These are some of the variants considered. The last variant considers the circle group $$\mathbb{T}$$ in place of $$\mathbb{Z}_N$$. The present author uses classical Fourier analytic methods, whereas the CRT approach involves random matrices.

MSC:
 42A38 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type 42A55 Lacunary series of trigonometric and other functions; Riesz products 42A61 Probabilistic methods for one variable harmonic analysis 65T50 Numerical methods for discrete and fast Fourier transforms 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 94A20 Sampling theory in information and communication theory
Full Text:
References:
 [1] Candès, Emmanuel J., Proceedings of the International Congress of Mathematicians, Madrid 2006, III, Compressive sampling, 1433-1452, EMS-ph · 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, 52, 2, 489-509, (2006) · 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, 59, 8, 1207-1223, (2006) · 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, 52, 12, 5406-5425, (2006) · Zbl 1309.94033 [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 [6] Kahane, J.-P., Idempotents et échantillonnage parcimonieux, Comptes rendus de l’Académie des sciences de Paris. série 1, 349, 1073-1076, (2011) · Zbl 1231.94044 [7] Kahane, J.-P., Analyse et synthèse harmonique, 17-53, (2012), École Polytechnique, Palaiseau · Zbl 1256.42001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.