Sigma Delta for Frame Coefficients

The idea behind the compressed sensing scheme in the paper mentioned earlier¹ is as follows. We know that under suitable conditions, we can recover a sparse vector $x\in\Sigma_k$ with few non-adaptive linear measurements $y = \Phi x$. For practical applications, we need to be able to store these measurements, and robustness results tell us that perturbing $y$ still allows approximate recovery of $x$. Specifically, we know that  we can determine the approximate support of $x$ from perturbed measurements. Let $T = {\rm supp}(x)$.

If we know the support of $x$, then we also know that if we took the columns of $\Phi$ corresponding to $T$, which we denote $\Phi_T$, then we can recover $x$ from $y$ via any left-inverse of $\Phi_T$ (there are many such left-inverses as $\Phi_T$ is $m \times k$ with $m>k$, i.e. overdetermined). In the language of frame theory, the columns of $\Phi_T$ will form a frame and the rows of the left-inverse form a dual frame.

From what follows we will let $E = \Phi_T$. The problem then boils down to the following: How can we quantize the measurements $q = Q(y)$, so that the error from recovery is as small as possible? Let us fix some alphabet $\mathcal{A} = \delta \mathbb{Z}$ say, and $Q: \mathbb{R}^m \to \mathcal{A}^m$. Essentially we want to solve
\[ \min_{Q, F: FE=I}  \| x - FQ(y) \|_2 \]
Then taking the worst case $x \in \Sigma_k$ will tell us the rate-distortion tradeoff for compressing $\Sigma_k$ with this scheme.

The paper cited above investigates the situation where $\Sigma\Delta$ quantization is used for the quantizer. That is, for an $r$-th order scheme, if $D$ is the finite difference matrix, the scheme solves a difference equation
\[   y - q = D^r u \]
for $q \in \mathcal{A}^m$ and $u$ bounded. In the setting of bandlimited signals, an $r$-th order scheme can obtain an error of the form $\lambda^{-r}$ where $\lambda$ is the oversampling ratio. The intuition here is that actually, since we know the support, which has size $k$, we are effectively oversampling by a factor $\lambda := m/k$, and thus we hope that we can achieve similar results in this setting.

This equation is solved via recursion greedily, by choosing $q_n$ to minimize $u_n$, with the catch that for larger $r$ we need a finer alphabet (or more bits in quantization).

Then to obtain an error estimate, for a dual frame $F$ (satisfying $FE=I$), we have the error estimate
\[  \|x - \hat{x}\| = \| F(y - q) \| = \| FD^r u \| \leq \|FD^r\|_{op} \|u\|_2 \]
Since $u$ is bounded, $\|u\|_2 \leq \sqrt{m} \|u\|_\infty$, and we want to find the dual frame $F$ which minimizes this operator norm, i.e. solve
\[  \min_{FE=I} \|FD^r\|_{op} \]

The solution is $F = (D^{-r}E)^\dagger D^{-r}$,  with operator norm $(\sigma_{min}(D^{-r}E)^{-1}$, which if $E$ is taken to be a random Gaussian frame (which is the case in one setting of compressed sensing), we can obtain an error estimate of $\lambda^{-\alpha r} / \sqrt{m}$ with overwhelming probability. When we put everything together, this gives a recovery error of  $\lambda^{-\alpha r}$.  (Above $\alpha$ is some constant in $(0,1)$, which affects the probability and rate of recovery)

An Extension
One possible extension of the above is then to say, what happens if we don't use $D^r$ as the noise shaping operator? Given $D$ and $E$, we note that there is an optimal dual frame $F$ for recovery. Can we choose $D$ so that the corresponding $F$ leads to a better result? The catch is that we need to constrain $D$ to lead to a stable scheme, so that we can still solve $y - q = Du$ with $u$ bounded, and constrained to the bit budget (alphabet constraint)

Let us study $D$ of the form $D = I + H$ where $H$ is lower triangular with $0$'s on the diagonal
(will add more later...)