Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements (Q1946588)

Compressed sensing deals with the how sparse signals can be recovered either exactly or approximately from few linear measurements (see \textit{E. J. Candès, J. Romberg} and \textit{T. Tao} [IEEE Trans. Inf. Theory 52, No. 2, 489--509 (2006; Zbl 1231.94017)] and \textit{D. L. Donoho} [``Compressed sensing'', IEEE Trans. Inf. Theory 52, No. 4, 1289--1306 (2006; \url{doi:10.1109/TIT.2006.871582})]). Let \(\Phi\) be an \(n\times N\) matrix providing the measurements where \(m\ll N\). Let \(\Sigma_{k}^{N}\) denote the space of \(k\)-sparse signals in \(\mathbb{R}^{N}\), \(k<m\). After a suitable change of basis, a standard objective is the injectivity of the linear mapping \(x\mapsto y=\Phi x\) in \(\Sigma_{k}^{N}\). Minimal conditions on \(\Phi\) are very well known in the literature (see \textit{A. Cohen, W. Dahmen} and \textit{R. De Vore} [J. Am. Math. Soc. 22, No. 1, 211--231 (2009; Zbl 1206.94008)]) and require at least that \(m\geq 2k\). Under more restrictive conditions on \(\Phi\), one can recover sparse vectors from their measurements by numerically efficient methods. The recovery will also be robust when the measurements are corrupted or perturbed. If \(\hat{y} = \Phi x + e\), where \(||e||_{2} \leq \epsilon\), then the solution \(x^\#\) of the optimization problem \(\min||z||_{1}\) with the constraint \(||\Phi z - \hat{y}||_{2} \leq \epsilon\) will satisfy \(||x- x^\#||_{2} \leq C_{1} \epsilon\), where the constant \(C_{1}\) only depends on \(\Phi\). While there are some explicit (deterministic) constructions of measurement matrices guaranteeing stable recovery, best results (for a widest range of values) have been found via random families of matrices. To be amenable to digital processing and storage, the applications require a quantization step where the measurements \(y\) are discretized in amplitude in order of their representation with a finite number of bits. The robust recovery result above mentioned is essential to the practicability of compressed sensing. It has been employed as the primary tool for the design and analysis of quantization methods. The main goal of this contribution is to develop and analyze the class of \(\Sigma\Delta\) algorithms as a high accuracy alternative for quantizing compressed measurements. A two-stage algorithm for the reconstruction of signals from their \(\Sigma\Delta\)-quantized compressed sensing measurements is presented. Indeed, in the first stage, any standard reconstruction algorithm for compressed sensing is used to recover the support \(T\) of the underlying sparse vector. In the second stage, the vector itself is reconstructed using non-standard duals of the associated submatrix \(\Phi_{T}\). These alternative dual frames, called Sobolev dual frames, are recently proposed in the framework of \(\Sigma\Delta\) quantization (see \textit{J. Blum} et al. [J. Fourier Anal. Appl. 16, No. 3, 365--381 (2010; Zbl 1200.42019)]). The two basic and remarkable results of this paper show that the \(\Sigma\Delta\) algorithms can be used to provide high quantized representations in the settings of Gaussian random finite frames and compressed sensing measurements with Gaussian measurement matrices. The quantization error bounds become quantifiably small as the ratio \(m/k\) increases. Indeed, the authors give an alternative recovery method via dual frames which guarantees a reduced approximation error of order \(\delta (k/m)^{\alpha (r- 1/2)}\) for any \(0 < \alpha < 1\) if \(m \lesssim _ {r, \alpha} k (log N) ^{1/(-\alpha)}\). The most appealing features of using \(\Sigma\Delta\) quantization are (i) It produces more accurate approximation than any known quantization scheme in this setting. (ii) It is modular in the sense that, if the fine recovery stage is not available or practical from the point of view of its implementation, then the standard recovery procedure can still be applied as is. (iii) It is progressive in the sense that if new measurements arrive, noise shaping can be continued on these measurements as long as the state of the system (\(r\) real values for an scheme of order \(r\)) has been stored. (iv) It is universal in the sense that it uses no information about the measurement matrix or the signal.