Evan Chou | |

Courant Institute of Mathematical Sciences | |

Email: chou (at cims) | |

Office: 608 Warren Weaver Hall |

In general, I am interested in mathematical models of signal processing; specifically, quantization. My current project (with Sinan Güntürk): Investigating noise-shaping (Sigma-Delta) as a means to boost sparse recovery of compressed sensing measurements.

Measurements \(y=\Phi x\) are encoded in a finite alphabet via Sigma-Delta, finding \(q\) such that \(y-q=D^{r}u\) for some bounded \(u\). (\(D\) is the finite-difference linear operator). The effect of this on compressed sensing: if we can recover the support of a sparse \(x\) (say via original \(l^1\) minimization methods), then we can boost the recovery further. Let \(T\) be the support and \(\Phi_T\) the corresponding submatrix.

Originally, if we have no information about the noise profile of \(y-q\), (or say \(y-q\) behaves like white-noise, which happens in the case of scalar quantization), then the best we can do is to recover using the psuedoinverse of \(\Phi_T\).

Otherwise, we can tailor the reconstruction to take advantage of the structure: of all the possible left-inverses of \(\Phi_T\), choose the one \(F\) that minimizes the operator norm of \(FD^{r}\), and use the bound \[ \|x - \hat{x}\| = \|Fy - Fq\| = \|FD^{r}u\| \leq \|FD^{r}\| \|u\| \]

Already proven that if \(\Phi\) is taken from the Gaussian ensemble, we can derive a recovery rate behaving like \(C_r(m/k)^{\alpha r}\) where \(m\) is the number of measurements, \(k\) is the sparsity, \(0 < \alpha < 1\) and \(r\) is the order of Sigma-Delta. (This is all in the Sobolev Dual paper by Güntürk, et. al.)

An alternative is to examine the quantization cell of \(x\), described entirely by the set \(\{z: \|D^{-r}(\Phi z - Q(x))\|_\infty \leq \delta\}\) where \(\delta\) is the alphabet resolution. Experiments of recovery methods based on the quantization cell directly seem to exhibit a better rate (for large \(m\)) than above.

- Chou, Evan. Nonconvex Decoding for \(\Sigma\Delta\)-Quantized Compressed Sensing.

Accepted to SampTA 2013. Turns out that considering the cell \[\{z: \|D^{-r}(\Phi z - Q(x))\|_2 \leq \sqrt{m}\delta\}\] with \(l^\tau\) minimization for sufficiently small \(\tau\), we can directly recover the signal. Moreover, in this case \(\delta\) does not need to be small for the results to hold!

Talk slides here.