scipy.linalg.clarkson_woodruff_transform¶
- scipy.linalg.clarkson_woodruff_transform(input_matrix, sketch_size, seed=None)[源代码]¶
将Clarkson-Woodruff变换/草图应用于输入矩阵。
给定输入矩阵
A大小的(n, d)，计算一个矩阵A'大小(sketch_size，d)，以便\[\|Ax\|\约x\|A‘x\|\]通过Clarkson-Woodruff变换(也称为CountSketch矩阵)具有很高的概率。
- 参数
- input_matrix: array_like
输入矩阵，形状
(n, d)。- sketch_size: int
草图的行数。
- seed ：{无，整型，
numpy.random.Generator，{无，整型， 如果 seed 为无(或 np.random )、
numpy.random.RandomState使用的是Singleton。如果 seed 是一个整型、一个新的RandomState实例，其种子设定为 seed 。如果 seed 已经是一个Generator或RandomState实例，则使用该实例。
- 退货
- A'array_like
输入矩阵示意图
A，大小(sketch_size, d)。
注意事项
发表声明
\[\|Ax\|\约x\|A‘x\|\]精确地，观察从定理14的证明改编而来的下列结果 [2] 通过马尔可夫不等式。如果我们有草图大小
sketch_size=k这至少是\[K\geq\frac{2}{\epsilon^2\Delta}\]那么对于任何固定的向量
x，\[\|Ax\|=(1\pm\epsilon)\|A‘x\|\]概率至少是一个负增量。
此实现利用了稀疏性：计算草图所需的时间与
A.nnz。数据A这是在scipy.sparse.csc_matrix格式为稀疏输入提供了最快的计算时间。>>> 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
题名/责任者：David P.输入稀疏时间的低秩逼近和回归。2013年，斯托克。
- 2
大卫·P·伍德拉夫。作为数值线性代数的工具的素描。“理论计算机科学的基础与趋势”，2014。
示例
给定一个大的稠密矩阵
A：>>> from scipy import linalg >>> n_rows, n_columns, sketch_n_rows = 15000, 100, 200 >>> rng = np.random.default_rng() >>> A = rng.standard_normal((n_rows, n_columns)) >>> sketch = linalg.clarkson_woodruff_transform(A, sketch_n_rows) >>> sketch.shape (200, 100) >>> norm_A = np.linalg.norm(A) >>> norm_sketch = np.linalg.norm(sketch)
现在以极高的概率，真正的规范
norm_A接近草图上的标准norm_sketch绝对值。类似地，应用我们的草图可以将解决方案保留到线性回归 \(\min \|Ax - b\|\) 。
>>> from scipy import linalg >>> n_rows, n_columns, sketch_n_rows = 15000, 100, 200 >>> rng = np.random.default_rng() >>> A = rng.standard_normal((n_rows, n_columns)) >>> b = rng.standard_normal(n_rows) >>> x = np.linalg.lstsq(A, b, rcond=None) >>> Ab = np.hstack((A, b.reshape(-1,1))) >>> SAb = linalg.clarkson_woodruff_transform(Ab, sketch_n_rows) >>> SA, Sb = SAb[:,:-1], SAb[:,-1] >>> x_sketched = np.linalg.lstsq(SA, Sb, rcond=None)
与矩阵范数示例一样，
np.linalg.norm(A @ x - b)接近于np.linalg.norm(A @ x_sketched - b)可能性很大。