EE Special Seminar

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*x. In this talk, we prove a restricted isometry property for this problem, which then entails local 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 given by  the sum of L absolute-squares of the scalar prodcut of b_l and Xc_l, where b_l and c_l are two given independent standard Gaussian vector sequences and X is taken as the supremum over a set of random matrices χ.  Such processes can be interpreted as the empirical process corresponding to a chaos process. We analyze such processes in terms of the Talagrand γ^2 functional. For the blind deconvolution application, our results yield local convergence guarantees whenever the sparsity of the signals is less than cL/(log L)^6 where L is the dimension and c is an absolute constant.

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