Abstract

Recent 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 $\ell_{1}$ minimization method for identifying a sparse vector from random linear measurements. Indeed, the $\ell_{1}$ approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability.