计算科学 - 有效地逼近 2 范数之和 - 吾爱随笔录

计算科学线性代数向量

2021-12-09 18:19:54

假设我有一个长度为，其中。假设我将这个向量分解为个向量，每个向量的长度为， $\bf x$ $KN$ $K<<N$ $\bf x$ $N$ $K$

x_{1}, . . . x_{n} .

${\bf x}_1,...{\bf x}_n.$

现在我想近似它们的 2 范数的总和：

f (K, N, x) \approx \sum_{n = 1}^{N} | | x_{n} {| |}_{2} .

$f(K, N, {\bf x})\approx \sum_{n=1}^N\left |\right |{\bf x}_n\left |\right |_2.$

其中可以非常有效地计算（与计算 2 范数之和相比）。有没有标准的方法来做到这一点？ $f$

1个回答

如果您只想要它们的范数总和的近似值，您可以选择个索引的随机样本（即，大小）和计算 $m$ $S \subseteq \{1,2,\dots,N\}$ $m$

f (x) = \sum_{n \in S} ‖ x_{n} ‖_{2} .

$f(\textbf{x}) = \sum_{n \in S} \| x_n \|_2.$

根据标准中心极限定理论证，将是范数总和的合理近似；越大，近似值就越好。计算的时间可能明显少于计算范数总和的时间，这取决于的存储方式和的值。 $f(\textbf{x})$ $m$ $\tilde{f}(\textbf{x})$ $\mathbf{x}$ $m$

其它你可能感兴趣的问题