Saturday, August 20, 2011

Sigma Delta for Frame Coefficients

The idea behind the compressed sensing scheme in the paper mentioned earlier1 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...)

No comments:

Post a Comment