Sigma delta quantization with harmonic frames and partial Fourier ensembles

DOI10.1007/S00041-017-9582-2MaRDI QIDQ1634829zbMATH OpenOpenAlexFDO

Authors Rongrong Wang

Publication date 18 December 2018

Published in The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.05671

zbMATH Keywords

compressed sensingpartial Fourier matrixsigma delta quantization

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) General harmonic expansions, frames (42C15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Sigma Delta quantization, a quantization method which first surfaced in the 1960s, has now been used widely in various digital products such as cameras, cell phones, radars, etc. The method samples an input signal at a rate higher than the Nyquist rate, thus achieves great robustness to quantization noise. Compressed Sensing (CS) is a frugal acquisition method that utilizes the possible sparsity of the signals to reduce the required number of samples for a lossless acquisition. One can deem the reduced number as an effective dimensionality of the set of sparse signals and accordingly, define an effective oversampling rate as the ratio between the actual sampling rate and the effective dimensionality. A natural conjecture is that the error of Sigma Delta quantization, previously shown to decay with the vanilla oversampling rate, should now decay with the effective oversampling rate when carried out in the regime of compressed sensing. Confirming this intuition is one of the main goals in this direction. The study of quantization in CS has so far been limited to proving error convergence results for Gaussian and sub-Gaussian sensing matrices, as the number of bits and/or the number of samples grow to infinity. In this paper, we provide a first result for the more realistic Fourier sensing matrices. The major idea is to randomly permute the Fourier samples before feeding them into the quantizer. We show that the random permutation can effectively increase the low frequency power of the measurements, thus enhance the quality of $SigmaDelta$ quantization.

Review text

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.

Recommendations

• Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements
• Sigma-delta quantization for fusion frames and distributed sensor networks
• Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing
• Frame paths and error bounds for sigma-delta quantization
• Sobolev duals in frame theory and Sigma-Delta quantization

Cites work

• Alternative dual frames for digital-to-analog conversion in sigma-delta quantization
• An Improved Estimate in the Restricted Isometry Problem
• An optimal family of exponentially accurate one-bit sigma-delta quantization schemes
• Approximating a bandlimited function using very coarsely quantized data: a family of stable sigma-delta modulators of arbitrary order
• From Compressed Sensing to Compressed Bit-Streams: Practical Encoders, Tractable Decoders
• Matrix concentration inequalities via the method of exchangeable pairs
• Near-optimal encoding for sigma-delta quantization of finite frame expansions
• Noise-shaping quantization methods for frame-based and compressive sampling systems
• On sparse reconstruction from Fourier and Gaussian measurements
• One-bit compressed sensing by linear programming
• One-bit compressed sensing with non-Gaussian measurements
• One-Bit Compressive Sensing With Norm Estimation
• One-bit sigma-delta quantization with exponential accuracy
• Quantization and finite frames
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Root-Exponential Accuracy for Coarse Quantization of Finite Frame Expansions
• Sigma-delta (/spl Sigma//spl Delta/) quantization and finite frames
• Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing
• Smooth frame-path termination for higher order sigma-delta quantization
• Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements
• Sobolev duals in frame theory and Sigma-Delta quantization
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• The restricted isometry property and its implications for compressed sensing

Cited in

(7)

• On the \(\ell^\infty\)-norms of the singular vectors of arbitrary powers of a difference matrix with applications to sigma-delta quantization
• Quantization for spectral super-resolution
• Quantized compressed sensing for random circulant matrices
• Ergodic dynamics in sigma-delta quantization: tiling invariant sets and spectral analysis of error
• Quantization and compressive sensing
• Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing
• Sigma Delta Quantization for Images

This page was built for publication: Sigma delta quantization with harmonic frames and partial Fourier ensembles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1634829)