Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Short course on Convex Optimization and Applications, 21, 22, 23, 27 March
Lecture 2: Convex-Cardinality Problems

Problems that are convex, except for the presence of cardinality or sparsity constraints in the objective or constraints, arise in many applications, including parsimonious model fitting, compressed sensing, and network topology selection. The standard method for approximately solving such problems is to use the $\ell_1$ norm as a surrogate for the cardinality. This leads to a tractable convex problem, such as LASSO fitting, widely used in modern statistics. We interpret the $\ell_1$ heuristic as a relaxation of a mixed-integer formulation of the convex-cardinality problem, and show how this naturally leads to more nuanced heuristics involving weighted asymmetric type surrogates, as well as iterative re-weighting methods.
Based on joint work by: Stephen Boyd, Emmanuel Candes.

Published recordings: On-demand video.
Type of Seminar:
IfA Seminar
Prof. Stephen Boyd
Electrical Engineering, Information Systems Laboratory, Stanford University
Mar 22, 2012   16:15

ETF E 1, Sternwartstr. 7
Contact Person:

John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
See Lecture 1