Caltech Logo

EE Special Seminar

Friday, August 12, 2016
3:00pm to 4:30pm
Add to Cal
Moore 139
Empirical Chaos Processes and their Application in Blind Deconvolution
Felix Krahmer, Assistant Professor for Optimization and Data Analysis, Department of Mathematics, Technische Universität München,

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).

For more information, please contact Katie Pichotta by email at [email protected].