scipy.linalg.

clarkson_woodruff_transform#

scipy.linalg.clarkson_woodruff_transform(input_matrix, sketch_size, rng=None)[源代码]#

对输入矩阵应用 Clarkson-Woodruff 变换/草图。

给定大小为 (n, d) 的输入矩阵 A，计算一个大小为 (sketch_size, d) 的矩阵 A'，使得

\[\|Ax\| \approx \|A'x\|\]

通过 Clarkson-Woodruff 变换（也称为 CountSketch 矩阵）以高概率成立。

参数:

input_matrixarray_like

输入矩阵，形状为 (n, d)。

sketch_sizeint

草图的行数。

rng{None, int, numpy.random.Generator}, 可选

如果通过关键字传递 rng，则除了 numpy.random.Generator 之外的类型将传递给 numpy.random.default_rng 以实例化 Generator。如果 rng 已经是 Generator 实例，则使用提供的实例。指定 rng 可实现可重复的函数行为。

如果此参数按位置传递或通过关键字传递 seed，则对参数 seed 应用旧的行为。

如果 seed 为 None (或 numpy.random)，则使用 numpy.random.RandomState 单例。
如果 seed 是一个整数，则使用一个新的 RandomState 实例，并使用 seed 作为种子。
如果 seed 已经是 Generator 或 RandomState 实例，则使用该实例。

在 1.15.0 版本中更改：作为从使用 numpy.random.RandomState 到 numpy.random.Generator 的 SPEC-007 过渡的一部分，此关键字从 seed 更改为 rng。在过渡期间，两个关键字将继续工作，尽管一次只能指定一个。在过渡期之后，使用 seed 关键字的函数调用将发出警告。 seed 和 rng 的行为如上所述，但在新代码中应仅使用 rng 关键字。

返回:

A’array_like: 输入矩阵 A 的草图，大小为 (sketch_size, d)。

注释

为了使该陈述

\[\|Ax\| \approx \|A'x\|\]

准确，请观察以下结果，该结果改编自 [2] 的定理 14 的证明，通过马尔可夫不等式。如果草图大小 sketch_size=k 至少为

\[k \geq \frac{2}{\epsilon^2\delta}\]

那么对于任何固定的向量 x，

\[\|Ax\| = (1\pm\epsilon)\|A'x\|\]

概率至少为 1 减去 delta。

此实现利用了稀疏性：计算草图所需的时间与 A.nnz 成正比。格式为 scipy.sparse.csc_matrix 的数据 A 可以为稀疏输入提供最快的计算时间。

>>> import numpy as np
>>> from scipy import linalg
>>> from scipy import sparse
>>> rng = np.random.default_rng()
>>> n_rows, n_columns, density, sketch_n_rows = 15000, 100, 0.01, 200
>>> A = sparse.rand(n_rows, n_columns, density=density, format='csc')
>>> B = sparse.rand(n_rows, n_columns, density=density, format='csr')
>>> C = sparse.rand(n_rows, n_columns, density=density, format='coo')
>>> D = rng.standard_normal((n_rows, n_columns))
>>> SA = linalg.clarkson_woodruff_transform(A, sketch_n_rows) # fastest
>>> SB = linalg.clarkson_woodruff_transform(B, sketch_n_rows) # fast
>>> SC = linalg.clarkson_woodruff_transform(C, sketch_n_rows) # slower
>>> SD = linalg.clarkson_woodruff_transform(D, sketch_n_rows) # slowest

也就是说，此方法在密集输入上表现良好，只是在相对尺度上速度较慢。

参考

[1]

Kenneth L. Clarkson 和 David P. Woodruff。输入稀疏时间中的低秩逼近和回归。在 STOC，2013。

[2]

David P. Woodruff。草图作为数值线性代数的工具。在理论计算机科学基础和趋势，2014。

示例

为示例创建一个大型密集矩阵 A

>>> import numpy as np
>>> from scipy import linalg
>>> n_rows, n_columns  = 15000, 100
>>> rng = np.random.default_rng()
>>> A = rng.standard_normal((n_rows, n_columns))

应用变换以创建一个具有 200 行的新矩阵

>>> sketch_n_rows = 200
>>> sketch = linalg.clarkson_woodruff_transform(A, sketch_n_rows, seed=rng)
>>> sketch.shape
(200, 100)

现在，以高概率，真实范数在绝对值上接近草图范数。

>>> linalg.norm(A)
1224.2812927123198
>>> linalg.norm(sketch)
1226.518328407333

同样，应用我们的草图保留了 \(\min \|Ax - b\|\) 的线性回归解。

>>> b = rng.standard_normal(n_rows)
>>> x = linalg.lstsq(A, b)[0]
>>> Ab = np.hstack((A, b.reshape(-1, 1)))
>>> SAb = linalg.clarkson_woodruff_transform(Ab, sketch_n_rows, seed=rng)
>>> SA, Sb = SAb[:, :-1], SAb[:, -1]
>>> x_sketched = linalg.lstsq(SA, Sb)[0]

与矩阵范数示例一样，linalg.norm(A @ x - b) 以高概率接近 linalg.norm(A @ x_sketched - b)。

>>> linalg.norm(A @ x - b)
122.83242365433877
>>> linalg.norm(A @ x_sketched - b)
166.58473879945151