Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
复制标题
DOI：
10.1098/rsta.2009.0152
复制
发表时间：
2009-11-13
期刊：
影响因子：
5
通讯作者：
Tanner, Jared
中科院分区：
文献类型：
--
作者：
Donoho, David;Tanner, Jared
我们回顾了高维组合几何中的相变与现代高维数据分析和信号处理中的相变之间的联系。在数据分析中，当模型的复杂性或离群值的数量增加超过阈值时，这种过渡会出现线性模型选择、鲁棒数据拟合或压缩感知重建的突然崩溃。在组合几何中，当维数变化时，这些过渡表现为凸多面体面数性质的突变。在这些非常不同的问题的阈值出现在相同的关键位置后，适当的变量校准。这些阈值在每个主题领域都很重要：对于线性建模，它们对现在无处不在的高通量数据分析的成功程度进行了严格限制;对于鲁棒性，它们对标准鲁棒拟合方法在崩溃之前可以容忍离群值的程度进行了严格限制;对于压缩感知，它们定义了欠采样定理中欠采样/稀疏性权衡曲线的尖锐边界。组合几何中相变的现有推导假设基础矩阵具有独立且同分布的高斯元素。然而，在应用中，似乎经常不需要高斯性。我们进行了广泛的计算实验和正式的推理分析，以测试的假设，这些相变是普遍的范围内的基础矩阵合奏。我们运行了数百万个线性程序，使用随机矩阵跨越几个矩阵合奏和问题的大小;视觉上，经验相变不依赖于合奏，他们同意非常好的渐近理论假设高斯。仔细的统计分析揭示了差异，可以解释为短暂的条款，随着问题的大小而衰减。因此，实验结果是一致的渐近大N的普遍性矩阵合奏;有限样本的普遍性可以被拒绝。
We review connections between phase transitions in high-dimensional combinatorial geometry and phase transitions occurring in modern high-dimensional data analysis and signal processing. In data analysis, such transitions arise as abrupt breakdown of linear model selection, robust data fitting or compressed sensing reconstructions, when the complexity of the model or the number of outliers increases beyond a threshold. In combinatorial geometry, these transitions appear as abrupt changes in the properties of face counts of convex polytopes when the dimensions are varied. The thresholds in these very different problems appear in the same critical locations after appropriate calibration of variables. These thresholds are important in each subject area: for linear modelling, they place hard limits on the degree to which the now ubiquitous high-throughput data analysis can be successful; for robustness, they place hard limits on the degree to which standard robust fitting methods can tolerate outliers before breaking down; for compressed sensing, they define the sharp boundary of the undersampling/sparsity trade-off curve in undersampling theorems. Existing derivations of phase transitions in combinatorial geometry assume that the underlying matrices have independent and identically distributed Gaussian elements. In applications, however, it often seems that Gaussianity is not required. We conducted an extensive computational experiment and formal inferential analysis to test the hypothesis that these phase transitions are universal across a range of underlying matrix ensembles. We ran millions of linear programs using random matrices spanning several matrix ensembles and problem sizes; visually, the empirical phase transitions do not depend on the ensemble, and they agree extremely well with the asymptotic theory assuming Gaussianity. Careful statistical analysis reveals discrepancies that can be explained as transient terms, decaying with problem size. The experimental results are thus consistent with an asymptotic large-n universality across matrix ensembles; finite-sample universality can be rejected.