×

Turán’s new method and compressive sampling. (English) Zbl 1311.42001

Pintz, János (ed.) et al., Number theory, analysis, and combinatorics. Proceedings of the Paul Turán memorial conference, Budapest, Hungary, August 22–26, 2011. Berlin: De Gruyter (ISBN 978-3-11-028242-9/ebook; 978-3-11-028237-5/hbk). De Gruyter Proceedings in Mathematics, 155-165 (2014).
The author starts from a result contained in [On a new method of analysis and its applications. New York: John Wiley & Sons (1984; Zbl 0544.10045)] by P. Turán (Theorem 11.6), stating that, for any given integer \(n\geq 2\) and \(0<\delta<1\), it is possible to find \(n\) real numbers \(x_1, \dots, x_n\), such that \[ \big| \sum_{j=1}^n \exp(2\pi i m x_j)\big| \leq \delta n\,, \] for all integers \(m\) satisfying \[ 1\leq m\leq \frac12 2^{n\delta^2/4}\,. \] First, by using the Laplace transform, the author slightly improves this result, proving that, given an integer \(n\geq 2\) and \(0<\delta<1\), the probability \[ P(M,n,\delta):=P\Big(\forall m\in\{1,\dots, M\}: \, \big| \sum_{j=1}^n \exp(2\pi i m x_j)\big| <\delta n\Big) \] satisfies \[ 1-P(M,n,\delta)\leq M\nu \exp (-n\delta^2 a^2) \] for all \(\nu\in\mathbb{N}\), \(\nu\geq 3\).
Then he proves a discrete version of the same theorem (Theorem 2), by replacing the \(x_j\) (considered as independent random variables on \(\mathbb{T}\)) by independent random variables \(\{X_j\}\) on \(\mathbb{Z}/ \mathbb{NZ}\), with \(N\) prime, \(N\geq 5\).
Finally, the author illustrates some connections between his discrete version of Turán’s theorem and some results in sampling theory. More precisely, he discusses some variations of the paradigmatic result about compressive sampling due to Candès, Romberg and Tao (2006) in the light of Theorem 2.
For the entire collection see [Zbl 1279.00053].

MSC:

42A05 Trigonometric polynomials, inequalities, extremal problems
42A61 Probabilistic methods for one variable harmonic analysis
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A20 Sampling theory in information and communication theory

Biographic References:

Turán, Paul

Citations:

Zbl 0544.10045