Living on the edge: Phase transitions in convex programs with random data
Dennis Amelunxen , Martin Lotz , Michael B. Mccoy and Joel A. Tropp
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.
中文速览
随机凸优化问题（random convex optimization）中普遍存在一种"相变"现象：当随机测量次数超过某个门槛时，求解算法几乎必然成功，低于门槛则几乎必然失败，但此前人们对这一现象缺乏系统性的理论解释。本文引入一个称为"统计维数"（statistical dimension）的核心参数，将线性子空间的维度概念推广到凸锥（convex cone），并证明凸锥的本征体积序列（intrinsic volumes）高度集中在统计维数附近——这一集中性结果是全文的核心技术成就。基于此，作者推导出近似运动学公式（approximate kinematic formula），将随机旋转凸锥相交的概率精确刻画为两个锥的统计维数之和与环境维度的大小比较，并将这套理论应用于压缩感知的ℓ₁最小化、随机去混叠（demixing）以及随机仿射约束锥规划等一系列问题，首次从理论上完整解释了相变的成因、位置和宽度。这项工作不仅统一解答了为何相变在随机凸优化中普遍出现，还提供了可计算的预测工具，对信号处理和统计中的逆问题研究具有深远意义。
原文 arXiv:1303.6672;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1303.6672v2