CAM Colloquium: Dennis Amelunxen (Cornell) - Phase Transitions in Convex Geometry and Optimization
Friday, February 8, 2013 at 3:45pm
Frank H. T. Rhodes Hall, 253
Convex optimization provides a powerful approach to solving a wide range of problems under structural assumptions on the solutions. Examples include solving linear inverse problems or separating signals with mutually incoherent structures. A curious phenomenon arises when studying such problems; as the underlying parameters in the optimization program shift, the convex relaxation can change quickly from success to failure.
We reduce the analysis of these phase transitions to a summary parameter, the statistical dimension, associated to the problem. We prove a new concentration of measure phenomenon for some integral geometric invariants, and deduce from this the existence of phase transitions for a wide range of problems; the phase transition being located at the statistical dimension. We furthermore calculate the statistical dimension in concrete problems of interest, and use it to relate previously existing—but seemingly unrelated—approaches to compressed sensing by Donoho and Rudelson & Vershynin.
This is joint work with Martin Lotz, Michael B. McCoy, Joel A. Tropp.