给定一个包含 1000000 个观测值 100 个特征的数据矩阵，是否有一种快速的方法来构建三对角近似值
？
然后可以分解，
和都为 0 ，并通过求解
进行快速去相关（白化） 。（“快速”是指。）
（添加，试图澄清）：我正在寻找一种快速而肮脏的增白剂，它比完全更快，但比对角线更好。假设是个数据点个特征，例如 1000000 100，特征为 0-mean。
1) 构建，Cholesky 将其分解为，求解以白化新 s。这是特征数量的二次方。
2) 对角线： 完全忽略了互相关。
只需将三对角线 之外的所有条目归零，或者一开始就不累积它们，就可以从在这里我开始下沉：必须有一个更好的近似，也许是分层的，块对角线→三对角线？
1）是否有一个快速的近似值?
不（whuber），必须查看所有对（或具有结构，或样本）。
2) 给定一个 s可以多快变白？
好吧， ,下三角分解一次，然后求解
非常快；例如，scipy.linalg.solve_triangular 使用 Lapack。
我一直在寻找更快的 whiten()，仍在寻找。
仅仅计算协方差矩阵——在任何情况下你都需要开始——是中渐近地，通过选择算法来获得什么美白。
当变量具有附加结构时存在近似值，例如当它们形成时间序列或在不同位置实现空间随机过程时。这些有效地依赖于假设，这些假设让我们将一对变量之间的协方差与其他变量对之间的协方差联系起来，例如由相同时滞分隔的对之间的协方差。例如，这是假设一个过程是静止的或本质上是静止的的常规原因。在这种情况下，计算可以是 （例如，使用Yao & Journel 1998中的快速傅立叶变换）。如果没有这样的模型，我看不出如何避免计算所有成对协方差.
一时兴起，我决定尝试（在 R 中）为大约 OP 中提到的大小的数据集计算协方差矩阵：
z <- rnorm(1e8)
dim(z) <- c(1e6, 100)
vcv <- cov(z)
在运行 Windows XP 32 位的相当通用的笔记本电脑上，这总共花费了不到一分钟的时间。z首先生成可能比计算矩阵花费更长的时间vcv。而且 R 并没有特别针对开箱即用的矩阵运算进行优化。
鉴于这个结果，速度有那么重要吗？如果 N >> p，计算近似值所需的时间可能不会比获得实际协方差矩阵少很多。
额外两分钱：
从算法上讲，我不认为有任何更快的算法可以为通用做到这一点。如果有，它们必须已经在迄今为止的程序中实施。然而，从软件工程的角度来看，不同的实现（例如，传统的 Blas、Goto Blas、英特尔的 MKL 和 OpenBlas）之间的速度可能会有很大差异。
根据应用场景，您可以针对您的用例对实现进行编码，但这需要使用更原生的语言（例如 Fortran、C 和 C++）进行代码处理。现在要进行快速实现，绝对需要的一件事是利用新的 CPU 功能，例如 AVX512，这需要一些 ASM 知识。
此外，根据您的意思，一种可能的近似值是使用蒙特卡洛积分。例如，对于 1000000 x 1 列（例如，对某事物的 1000000 次观察），平均值的文字计算将为，但对于近似值，您可以取只有 1000 的子样本来粗略估计平均值，比如，其中是原始 x 的子样本. 这个想法适用于计算你的协方差。假设您有两列 x 和 y；而不是做，你可以只用一个子样本（例如，1000）. 如果行的顺序足够随机，则不需要显式地对这 1000 个索引进行采样，您可以按常规步骤进行抽样，也可以只抽取前 1000 行。
为了解决的反向替换，如果 L 被多次重复使用，一个小的改进是将的对角线元素显式存储为它们的反转（例如）；这将避免进行除法，而是在反向替换阶段进行乘法。如今，考虑到浮点除法和乘法的速度应该大致相同，这种节省并没有真正意义。但旧 CPUS 的情况并非如此，因为除法通常比乘法慢得多。同样，这只是一件小事，不会显着加快计算速度，但根据用户情况，它可能会有所帮助。