List-Decoding of Error-Correcting Codes with Applications to Compressed Sensing

SPEAKER: Dr. Farzad Parvaresh, Postdoctoral Fellow, California Institute of TechnologyABSTRACT: We consider the problem of designing codes and decoding algorithms for the adversarial channel. We show that the ultimate error-correction radius of 1 - R, where R is the rate of the code, can be achieved constructively with polynomial-time decoding, in the list-decoding sense.Our codes and list-decoders are based on two key ideas. The first is the transition from bivariate polynomial interpolation, pioneered by Sudan and Guruswami-Sudan, to multivariate interpolation decoding. The second idea is to part ways with Reed-Solomon codes, for which numerous prior attempts at breaking the rate barrier in the worst-case were unsuccessful. Rather than devising a better list-decoder for Reed-Solomon codes, we devise better codes. In our codes, instead of evaluating certain functions at rational points of a curve, we evaluate the rational points themselves, viewed as pairs of polynomials over a subfield, at certain elements of the subfield. This construction leads to polynomial-time error-correction up to the radius of 1 - O(R log(1/R)). Utilizing the folding technique of Guruswami and Rudra one can improve the decoding bound up to 1 - R - \epsilon, for any positive \epsilon.Finally, we borrow ideas from the list-decoding of Reed-Solomon codes to improve the state of the art in the area of compressed sensing. We show that a deterministic Fourier measurement of the signal with a decoding algorithm due to Coppersmith and Sudan can reach the ultimate threshold of sparsity to number-of-measurements for block sparse signals in polynomial time. We will also point out connections of this to DNA microarrays.BIO: Farzad Parvaresh was born in Isfahan, Iran, in 1978.He received the B.S. degree in electrical engineering from the Sharif University of Technology, Tehran, Iran, in 2001, and the M.S. and Ph.D. degrees in electrical and computer engineering form the University of California, San Diego, in 2003 and 2007, respectively. He is currently a post doctoral scholar at the Center for Mathematics of Information, California Institute of Technology, Pasadena, CA. His research interests include error-correcting codes, algebraic decoding algorithms, information theory, networks, and fun math problems. Dr. Parvaresh was a recipient of the best paper award from the 46th Annual IEEE symposium on foundations of computer science (FOCS'05).Host: Prof. Giuseppe Caire, caire@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher