Turán's new method and compressive sampling (Q2874922)

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 \textit{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 NEWLINE\[NEWLINE\big| \sum_{j=1}^n \exp(2\pi i m x_j)\big| \leq \delta n\,,NEWLINE\]NEWLINE for all integers \(m\) satisfying NEWLINE\[NEWLINE1\leq m\leq \frac12 2^{n\delta^2/4}\,.NEWLINE\]NEWLINE 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 NEWLINE\[NEWLINEP(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)NEWLINE\]NEWLINE satisfies NEWLINE\[NEWLINE1-P(M,n,\delta)\leq M\nu \exp (-n\delta^2 a^2)NEWLINE\]NEWLINE for all \(\nu\in\mathbb{N}\), \(\nu\geq 3\).NEWLINENEWLINEThen 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\).NEWLINENEWLINEFinally, 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.NEWLINENEWLINEFor the entire collection see [Zbl 1279.00053].