Variations on a theorem of Candès, Romberg and Tao (Q2511495)

The problem considered in the pioneering work of Candès, Romberg and Tao in \textit{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 \textit{single} signal. The paper under review also deals with variants of this result and is concerned with the condition: \(\hat{x}\) \textit{is the minimal extension of \(\hat{x}|_{\Omega }\) in} \(A(\widehat{G}):= \mathcal{F}\ell^1(G)\). Can \textit{all} signals with the same support be reconstructed? Can \textit{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.