Numerical Analysis and Scientific Computing Seminar

A Convex Perspective on Spectral Methods in Signal Processing.

Speaker: Ben Recht, University of Wisconsin - Madison

Location: Warren Weaver Hall 1302

Date: Oct. 19, 2012, 10 a.m.


Abstract: Spectral methods that leverage the singular value decomposition to reject noise and identify models are ubiquitous in signal processing. Despite their widespread adoption, little is understood about their finite-sample convergence properties. In this talk, I will provide a general framework, called atomic norm denoising, for understanding these spectral methods in the context of convex programming. The resulting optimization problems have generic, mean-squared-error guarantees and reduce to familiar soft-thresholding algorithms in the context of sparse approximation.

To demonstrate the wide applicability of atomic norm denoising, I will detail two examples, deriving novel efficient algorithms and guarantees. I will present a convex approach to spectrum estimation, estimating the frequencies and phases of a mixture of complex exponentials from noisy or missing data. I will then apply the framework to identify linear dynamical systems from corrupted measurements. In both cases, I will show that the standard spectral methods are in fact non-convex approximations of atomic-norm denoising. Moreover, I will present experimental results showing that atomic norm denoising efficiently achieves comparable or better error to existing spectral methods without a priori knowledge of system parameters such as model order. Joint work with Badri Bhaskar, Parikshit Shah, and Gongguo Tang

Bio: Benjamin Recht is an Assistant Professor in the Department of Computer Sciences at the University of Wisconsin-Madison and holds courtesy appointments in Electrical and Computer Engineering, Mathematics, and Statistics. He is a PI in the Wisconsin Institute for Discovery (WID), a newly founded center for research at the convergence of information technology, biotechnology, and nanotechnology. Ben received his B.S. in Mathematics from the University of Chicago, and received a M.S. and PhD from the MIT Media Laboratory. After completing his doctoral work, he was a postdoctoral fellow in the Center for the Mathematics of Information at Caltech. He is the recipient of an NSF Career Award, an Alfred P. Sloan Research Fellowship, and the 2012 SIAM/MOS Lagrange Prize in Continuous Optimization.