scipy.linalg.

clarkson_woodruff_transform#

scipy.linalg.clarkson_woodruff_transform(input_matrix, sketch_size, rng=None)[source]#

將 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。草圖作為數值線性代數的工具。於 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