scipy.linalg.

clarkson_woodruff_transform#

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

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

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

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

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

参数:

input_matrix类似于数组: 形状为 (n, d) 的输入矩阵。
sketch_sizeint: 草图的行数。
seed{None, int, numpy.random.Generator, numpy.random.RandomState}, 可选: 如果 seed 为 None（或 np.random），将使用 numpy.random.RandomState 单例。如果 seed 为 int，将使用一个新 RandomState 实例，使用 seed 进行种子设置。如果 seed 已是一个 Generator 或 RandomState 实例，那么将使用该实例。

返回:

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