Sobolev duals in frame theory and Sigma-Delta quantization (Q981637)

A frame \(\{e_1,\dots, e_N\}\) for \(\mathbb{R}^d\) defines a right-invertible \(d\times N\) frame matrix \(E\) whose \(j\)th column is \(e_j\). A dual frame consists of the columns \(\{f_1,\dots, f_N\}\) of a matrix \(F\) such that \(F E^\ast \) is the \(d\times d\) identity. The Sobolev dual frame of order \(r\) is defined via the matrix \(F=(E\nabla^{-r} E^\ast)^{-1} E \nabla^{-r}\) in which \(\nabla =D^\ast D\) where \(D\) is the \(N\times N\) forward difference matrix \(D_{jj}=1\), \(D_{j,j+1}=-1\) and \(D_{j,k}=0\) otherwise. An \(r\)th order \(\Sigma\Delta\) scheme is an iteration \(q_n=Q(\rho(u_{n-1}^1,\dots, u_{n-1}^r,x_n))\); \(\Delta^r u_n^r=x_n-q_n\) and \(u_n^{j}=\Delta u_n^{j+1} \), \(j=1,\dots, r-1\). The iteration runs for \(n=1,\dots, N\) starting with \(u_0^1=\dots=u_0^{r}=0\). Here \(\rho: \mathbb{R}^{r+1}\to\mathbb{R}\) is called the quantization rule. The mapping \(Q\) sends \(u\) to a closest element of a finite quantization alphabet \(\mathcal{A}\). Such a scheme is stable if, essentially, \(|x_n|\leq C_1\) implies each \(|u_n^j|\leq C_2\) for appropriate \(C_1\) and \(C_2\). Given frame coefficients \(x_n=\langle x,\, e_n\rangle\), one can construct an approximation \(\widetilde{x}=\sum_{n=1}^N q_n f_n\) with respect to a dual frame \(\{f_n\}\). The main theorem gives an approximation criterion for frame quantization reconstructions for Sobolev duals when the frame \(E\) is generated from a uniformly sampled continuous frame path. This means that \(E(t)=[e_1(t),\dots,e_d(t)]^T\) is continuous on \([0,1]\) and the matrix \(\{E(n/N)\}_{n=1}^N\) is a frame once \(N\) is large enough. Let an \(r\)th order stable \(\Sigma\Delta\) scheme with quantization alphabet \(\mathcal{A}\) be given. Let \(E(t)\) be a piecewise \(C^1\) uniformly sampled frame path for \(\mathbb{R}^d\) and \(N_0\) such that \(E_N=\{E(n/N)\}_{n=1}^N\) is a frame for \(\mathbb{R}^d\) for all \(N\geq N_0\). The main result states that, then, given \(x\in\mathbb{R}^d\) with \(\|x\|\leq \eta\) with frame coefficients \(\{\langle x,\, E(n/N)\rangle\}\) and \(\{q_n^N\}\subset\mathcal{A}^N\) the sequence of quantized frame coefficients generated by the \(r\)th order \(\Sigma\Delta\) scheme, if one uses the \(r\)th order Sobolev dual frame \(F_N\) of \(E_N\) to linearly reconstruct the approximation \(\widetilde{x}=\sum_{n=1}^N q_n f_n\) of \(x\), then \(\|x-\widetilde{x}\|=\mathcal{O}(N^{-r})\). Furthermore, it is shown that if \(x\) is drawn randomly from a compact subset of \(\mathbb{R}^d\) with a Borel probability density then, under a standard white noise assumption on the quantization errors, among all dual frames, the \(r\)th order \(\Sigma\Delta\) scheme minimizes the expected quantization error \(\|x-\widetilde{x}\|\).