Living on the edge: phase transitions in convex programs with random data
Living on the edge: phase transitions in convex programs with random data
复制标题
DOI：
10.1093/imaiai/iau005
复制
发表时间：
2014-09-01
影响因子：
1.6
通讯作者：
Tropp, Joel A.
中科院分区：
文献类型：
--
作者：
Amelunxen, Dennis;Lotz, Martin;Tropp, Joel A.
最近的研究表明，随着约束数量的增加，许多带有随机约束的凸优化问题表现出相变。例如，这种现象出现在L（1）最小化方法中，用于从随机线性测量中识别稀疏向量。实际上，当测量次数超过取决于稀疏度的阈值时，L（1）方法的可能性很高。否则，它的可能性很高。本文提供了第一个严格的分析，该分析解释了为什么相位过渡在随机凸优化问题中无处不在。它还描述了用于对过渡的定量方面（包括过渡区域的位置和宽度）进行可靠预测的工具。这些技术适用于随机测量的正常线性反问题，在随机不一致模型下解决问题，也适用于具有随机仿射约束的锥形程序。应用结果取决于圆锥几何形状中的基础研究。本文介绍了一个称为统计维度的摘要参数，该参数将线性子空间的维度扩展到凸锥类别。主要技术结果表明，凸锥的内在体积序列围绕统计维度急剧集中。这一事实导致了与随机旋转的锥与固定锥共享射线的概率的准确界限。
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 l(1) minimization method for identifying a sparse vector from random linear measurements. Indeed, the l(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. This paper provides the first 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. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.