June 06, 2011, Elings Hall 1605

In this lecture we explore problems that are convex, except for a constraint or objective that involves sparsity of a vector, or the rank of a matrix. We derive the l_1 heuristic, widely used in modern statistics and machine learning, as a convex relaxation of the nonconvex problem. We derive extensions such as iterative re-weighting, sum-of-norms, and dual spectral (nuclear) norm methods for rank problems.

Stephen P. Boyd is the Samsung Professor of Engineering, and Professor of Electrical Engineering in the Information Systems Laboratory at Stanford University. He also has a courtesy appointment in the Department of Management Science and Engineering, and is member of the Institute for Computational and Mathematical Engineering. His current research focus is on convex optimization applications in control, signal processing, and circuit design.