From Sparsity to Rank, and Beyond: algebra, geometry, and convexity

School of Mathematics Colloquium
Monday, October 24, 2011 - 4:00pm for 1 hour (actually 50 minutes)
Skiles 006
Pablo Parrilo – MIT – parrilo@mit.edu
Greg Blekherman
Optimization problems involving sparse vectors or low-rank matrices are of great importance in applied mathematics and engineering. They provide a rich and fruitful interaction between algebraic-geometric concepts and convex optimization, with strong synergies with popular techniques like L1 and nuclear norm minimization. In this lecture we will provide a gentle introduction to this exciting research area, highlighting key algebraic-geometric ideas as well as a survey of recent developments, including extensions to very general families of parsimonious models such as sums of a few permutations matrices, low-rank tensors, orthogonal matrices, and atomic measures, as well as the corresponding structure-inducing norms.Based on joint work with Venkat Chandrasekaran, Maryam Fazel, Ben Recht, Sujay Sanghavi, and Alan Willsky.