Sigma delta quantization with harmonic frames and partial Fourier ensembles (Q1634829)

The main results provide estimates for first order \(\Sigma\Delta\)-quantization. Let \(F\) be an \(N\times k\) harmonic frame and let \(\widetilde{F}\in\mathbb{C}^{m,k}\) be a matrix obtained by randomly selecting rows of \(F\) with replacement. Denote by \(q=Q^1(\widetilde{F}(x))\) the one-term \(\Sigma\Delta\)-quantization of \(\widetilde{F}(x)\) using a uniform quantization alphabet \((1+i)\delta\mathbb{Z}\), \(x\) in the unit ball in \(\mathbb{C}^k\). First order \(\Sigma\Delta\)-quantization is defined by \(y\mapsto q\) where \(Q_s\) maps to the closest element of the alphabet and \(q_i=Q_s(u_{i-1}+y_i)\) and \(u_i=y_i-q_i-u_{i-1}\). There exist constants \(c_1,c_2\) such that, for any \(\epsilon>0\), the reconstruction \(\hat{x}=\widetilde{F}_{\text{sob}}(q)\), or any feasible minimizer of \(\|D^{-1}(x-\widetilde{F}z)\|_\infty\leq \delta/2\), satisfies \(\|x-\hat{x}\|_2\leq c_1\delta (m/\ell)^{-1/2}\) with probability at least \(1-\epsilon\) if \(m/\pi^2\geq \ell\geq c_2 k\log^3(m/\epsilon)\). Here \(D\) is the \(m\times m\) discrete difference matrix with ones and minus ones on the main and sub diagonals, respectively, and zeros otherwise, and \(\widetilde{F}_{\text{sob}}\) is a \textit{Sobolev} dual of \(F\), see [\textit{R. Saab} et al., Appl. Comput. Harmon. Anal. 44, No. 1, 123--143 (2018; Zbl 1375.94079)]. The following corresponding estimate is provided for sparse signals: let \(\widetilde{A}\in\mathbb{C}^{m,N}\) be obtained from an unnormalized \(N\times N\) DFT matrix by random row selection with replacement. Let \(x\in\mathbb{C}^N\) be \(k\)-sparse and \(q=Q^1(\widetilde{A}x)\) be the first order \(\Sigma\Delta\)-quantization of \(\widetilde{A}x\), and \(\hat{x}\) a minimizer of \(\|z\|_1\) subject to \(\|D^{-1}(x-\widetilde{F}z)\|_\infty\leq \delta/2\). Then there exist constants \(c_1,c_2\) such that, for any \(\epsilon>0\), \(\|x-\hat{x}\|_2\leq c_1\delta (m/(k^4\log^3(N/\epsilon)))^{-1/2}\) with probability \(1-\epsilon\) provided \(m\geq c_2k^3\log^3(N/\epsilon)\). The proofs require matrix Bernstein and Rosenthal inequalities, and Stirling formula estimates, among others. These estimates provide versions for Fourier matrices of known results for subGaussian matrices, using different techniques. The role of randomization is explained to be a flattening of the spectrum in a similar way that \(\Sigma \Delta\)-quantization moves quantization noise to high frequencies outside the band of interest, as quantified in Theorems 2.6--2.8. Theorem 2.6 provides upper and lower bounds for singular values, in probability, of matrices formed by randomly selecting rows of a harmonic frame matrix.