Living on the Edge - Phase Transitions in Random Convex Programs

author: Joel Tropp, Department of Computing and Mathematical Sciences, California Institute of Technology (Caltech)
published: Aug. 26, 2013,   recorded: July 2013,   views: 5363


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Recent empirical research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the l1 minimization method for identifying a sparse vector from random linear samples. Indeed, this approach succeeds with high probability when the number of samples exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability.

This talk summarizes a rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. Joint work with D. Amelunxen, M. Lotz, and M. B. McCoy

See Also:

Download slides icon Download slides: roks2013_tropp_optimization_01.pdf (1.2┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 jerry, April 8, 2019 at 1:57 p.m.:

If you loves to play online board game then here you will play the game of tiles and numbers play online without any download and login the dare of the game is to connect the tiles to make at least 2 angle of ninety degree.

Write your own review or comment:

make sure you have javascript enabled or clear this field: