scipy.linalg.

clarkson_woodruff_transform#

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

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

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

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

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

参数:

input_matrix类数组, 形状 (…, n, d)

输入矩阵。

sketch_size整型

草图的行数。

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 版本更改: 作为 SPEC-007 从使用 numpy.random.RandomState 过渡到 numpy.random.Generator 的一部分，此关键字从 seed 更改为 rng。在过渡期间，这两个关键字都将继续有效，但一次只能指定一个。过渡期结束后，使用 seed 关键字的函数调用将发出警告。上面概述了 seed 和 rng 的行为，但在新代码中应只使用 rng 关键字。

返回:

A’类数组: 输入矩阵 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 and David P. Woodruff. Low rank approximation and regression in input sparsity time. In STOC, 2013.

[2]

David P. Woodruff. Sketching as a tool for numerical linear algebra. In Foundations and Trends in Theoretical Computer Science, 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