Empirical Chaos Processes and their application in Blind Deconvolution

Felix Khramer (TU München)
Wednesday, January 27, 2016 - 10:00am
WIAS, Raum 4.13, Hausvogteiplatz 11a, 10117 Berlin

The motivation of this talk is the deconvolution of two unknown vectors $w$ and $x$, each of which is sparse with respect to a generic (but known) basis. That is, one seeks to recover $w$ and $x$ from their circular convolution $y = w {\ast} x$. In this talk, we prove a restricted isometry property for this problem, which then entails convergence guarantees for the non-convex sparse power factorization algorithm via recent work by Lee et al. A key ingredient of our proof are tail bounds for random processes of the form \[ \sup\limits_{X\in{\cal X}}\sum\limits^L_{\ell =1}| \langle b_{\ell}, X_{C_\ell}\rangle|^2, \] where the $b_{\ell}, c_{\ell}$ are independent standard Gaussian vectors and ${\cal X}$ is a set of matrices. Such processes can be interpreted as the empirical process corresponding to a chaos process. We analyze such processes in terms of the Talagrand $\gamma_2$ functional. For the blind deconvolution application, our results yield convergence guarantee whenever the sparsity of the signals is less than $c L/ \log^6 L$, where $L$ is the dimension and $c$ is an absolute constant.

This is joint work with Justin Romberg (Georgia Tech) and Ali Ahmed (MIT).