Tutte Colloquium -Michael Friedlander-The Measure of a Cone: Randomness and exactness in convex optimization

Abstract: 

Conic geometry encodes combinatorial properties of a convex program. Under a probabilistic model of the data, these combinatorial properties become random events. Their likelihood is the measure of a cone. We illustrate this view with a dual pair of questions. First, how much can a linear program be regularized before its solution changes? With random costs, the answer turns on the Gaussian measure of the solution's normal cone. Second, how many measurements are needed to separate a superposition of structured signals? Here, each signal's complexity is the statistical dimension of its descent cone. A convex program recovers the components once the measurement count exceeds the total complexity.