Universality in numerical computations with random data
Universality in numerical computations with random data
复制标题
随机数据数值计算的普遍性
DOI：
10.1073/pnas.1413446111
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Trogdon
中科院分区：
文献类型：
--
作者：
P. Deift;Govind Menon;S. Olver;T. Trogdon
显着性普遍存在波动时，众所周知的和广泛使用的数值算法应用于随机数据。在随机算法和模拟神经计算的算法中也显示出类似的普遍行为。是否普遍性存在于所有或几乎所有的计算的问题被提出。作者提出了随机数据的数值计算的普遍性的证据。给定一个具有随机输入数据的（可能是随机的）数值算法，收敛的时间（或迭代次数）（在给定的公差内）是一个随机变量，称为停止时间。对于停止时间的波动，观察到两个分量的普遍性，即，以样本平均值为中心并以样本方差为尺度的停止时间的直方图随着维数的增加而塌陷为通用曲线，与输入数据分布无关。因此，最多两个组成部分-样本平均值和样本方差-停机时间的统计量是普遍规定的。案例研究包括六个标准的数值算法以及神经计算和决策模型。一个链接到相关的软件提供给读者谁愿意做自己的计算。
Significance Universal fluctuations are shown to exist when well-known and widely used numerical algorithms are applied with random data. Similar universal behavior is shown in stochastic algorithms and also in an algorithm that models neural computation. The question of whether universality is present in all, or nearly all, computation is raised. The authors present evidence for universality in numerical computations with random data. Given a (possibly stochastic) numerical algorithm with random input data, the time (or number of iterations) to convergence (within a given tolerance) is a random variable, called the halting time. Two-component universality is observed for the fluctuations of the halting time—i.e., the histogram for the halting times, centered by the sample average and scaled by the sample variance, collapses to a universal curve, independent of the input data distribution, as the dimension increases. Thus, up to two components—the sample average and the sample variance—the statistics for the halting time are universally prescribed. The case studies include six standard numerical algorithms as well as a model of neural computation and decision-making. A link to relevant software is provided for readers who would like to do computations of their own.