-
USC CS Theory Seminar Series
Thu, Sep 13, 2012 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Arash Saber Tehrani,
Talk Title: Arash Saber Tehrani, Message-Passing Algorithms and Improved LP Decoding
Series: USC CS Theory
Abstract: Message-Passing Algorithms and Improved LP Decoding By Sanjeev Arora, Constantinos Daskalakis, and David Steurer
(http://www.cs.princeton.edu/~dsteurer/lpdecode.pdf)
By Arash Saber Tehrani: I will discuss the results of the paper above, where the authors prove the best known performance guarantee for the LP decoding. Further, if I have time, Arash will connect the LP decoding problem to compressed sensing through the bridge introduced
in:
http://www-bcf.usc.edu/~dimakis/DV_Allerton2009_final_arxiv.pdf
and show that the same guarantee is valid for compressed sensing as shown in
http://www-bcf.usc.edu/~dimakis/KSDH11_isit.pdf
and a current project that me and Alex are working on. Note that the above result leads to an explicit construction for measurement matrices which can be checked to be ``good'' efficiently.
****
Host: Dr. Shanghua Teng
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Jacob Beal
