图 书 馆
生活在边缘：随机数据凸规划中的相变Living on the edge: Phase transitions in convex programs with random data |
|
| 课程网址: | http://videolectures.net/sahd2014_tropp_phase_transitions/ |
| 主讲教师: | Joel Tropp |
| 开课单位: | 加州理工学院 |
| 开课时间: | 2014-10-29 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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 `1 minimization method for identifying a sparse vector from random linear measurements. Indeed, the `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. |
| 关 键 词: | 约束; 统计维数; 凸优化 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2020-12-07：yxd |
| 最后编审: | 2020-12-07：yxd |
| 阅读次数: | 48 |