“Blind Demixing and Deconvolution at Near-Optimal Rate”
Dr. Felix Krahmer, Technical University of Munich
Wednesday, August 31, 2016 2:00 - 3:00PM EEB 248
Abstract: Consider a communication setup of $r$ devices, each sending a signal $x_i$ to a common receiver. In the transmission process, each signal $x_i$ gets convolved with an unknown vector $w_i$, which represents the channel. The receiver measures only the superposition of these signals. The goal is to recover all signals $x_i$. Of course, this problem is highly underdetermined, but in many practical applications, it is a natural to assume that $x_i$ and $w_i$ are elements of some (known) subspaces. Ling and Strohmer have proposed a convex recovery program for this problem, which is based on nuclear norm minimization. They were able to prove (probabilistic) recovery guarantees, which scale quadratically in the number of devices $r$. However, their numerical experiments suggest that recovery is still possible when the number of measurements scales linearly in $r$. In this talk, we present a recovery guarantee, which is linear in the number of degrees of freedom $r$ and which is close to the number of degrees of freedom. Similar to the work of Ling and Strohmer, the proof is based on the Golfing Scheme by David Gross. However, using tools on Chaos Processes developed by Krahmer, Mendelson, and Rauhut we are able to prove a certain local isometry property, which is stronger than the one established in the work of Ling and Strohmer. This allows us to construct a different dual certificate. This is joint work with Peter Jung (TU Berlin) and Dominik Stöger (TU Munich).
Bio: Felix Krahmer received his PhD in Mathematics in 2009 from New York University under the supervision of Percy Deift and Sinan Güntürk. He was a HCM postdoc in the group of Holger Rauhut at the University of Bonn, Germany from 2009-2012. In 2012 he joined the University of Göttingen as an assistant professor for mathematical data analysis, where he has been awarded an Emmy Noether Junior Research Group. Since 2015 he has been tenure track assistant professor for optimization and data analysis in the department of mathematics at the Technical University of Munich.