图 书 馆
生活在边缘：随机数据凸规划中的相变Living on the edge: Phase transitions in convex programs with random data |
|
| 课程网址: | http://videolectures.net/sahd2014_tropp_phase_transitions/ |
| 主讲教师: | Joel Tropp |
| 开课单位: | 加州理工学院 |
| 开课时间: | 2014-10-29 |
| 课程语种: | 英语 |
| 中文简介: |  最近的研究表明，随着约束数量的增加，许多具有随机约束的凸优化问题都表现出相变。例如，这种现象出现在“ 1”最小化方法中，该方法用于从随机线性测量中识别稀疏矢量。实际上，当测量数量超过取决于稀疏性水平的阈值时，`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 `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-10-21：zyk |
| 最后编审: | 2020-10-21：zyk |
| 阅读次数: | 82 |