scipy.linalg.

clarkson_woodruff_transform#

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

Wendet eine Clarkson-Woodruff-Transformation/Skizze auf die Eingabematrix an.

Gegeben eine Eingabematrix A der Größe (n, d), berechnen Sie eine Matrix A' der Größe (sketch_size, d), sodass

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

mit hoher Wahrscheinlichkeit über die Clarkson-Woodruff-Transformation, auch bekannt als CountSketch-Matrix.

Parameter:
input_matrixarray_like, shape (…, n, d)

Eingabematrix.

sketch_sizeint

Anzahl der Zeilen für die Skizze.

rng{None, int, numpy.random.Generator}, optional

Wenn rng als Schlüsselwort übergeben wird, werden andere Typen als numpy.random.Generator an numpy.random.default_rng übergeben, um einen Generator zu instanziieren. Wenn rng bereits eine Generator-Instanz ist, dann wird die bereitgestellte Instanz verwendet. Geben Sie rng für reproduzierbares Funktionsverhalten an.

Wenn dieses Argument positionsabhängig übergeben wird oder seed als Schlüsselwort übergeben wird, gilt das Legacy-Verhalten für das Argument seed.

  • Wenn seed None ist (oder numpy.random), wird die Singleton-Instanz von numpy.random.RandomState verwendet.

  • Wenn seed eine Ganzzahl ist, wird eine neue RandomState-Instanz mit seed verwendet.

  • Wenn seed bereits eine Generator- oder RandomState-Instanz ist, dann wird diese Instanz verwendet.

Geändert in Version 1.15.0: Im Rahmen des SPEC-007-Übergangs von der Verwendung von numpy.random.RandomState zu numpy.random.Generator wurde dieses Schlüsselwort von seed in rng geändert. Für eine Übergangszeit werden beide Schlüsselwörter weiterhin funktionieren, obwohl nur eines gleichzeitig angegeben werden darf. Nach der Übergangszeit geben Funktionsaufrufe mit dem Schlüsselwort seed Warnungen aus. Das Verhalten von sowohl seed als auch rng ist oben beschrieben, aber nur das Schlüsselwort rng sollte in neuem Code verwendet werden.

Rückgabe:
A’array_like

Skizze der Eingabematrix A der Größe (sketch_size, d).

Hinweise

Um die Aussage

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

präzise zu machen, beachten Sie das folgende Ergebnis, das aus dem Beweis von Theorem 14 von [2] mittels Markow-Ungleichung adaptiert wurde. Wenn wir eine Skizzengröße sketch_size=k haben, die mindestens

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

ist, dann gilt für jeden festen Vektor x,

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

mit einer Wahrscheinlichkeit von mindestens eins minus delta.

Diese Implementierung nutzt die Sparsity: Die Berechnung einer Skizze dauert proportional zu A.nnz. Daten A im Format scipy.sparse.csc_matrix ergeben die schnellste Berechnungszeit für spärliche Eingaben.

>>> 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

Dennoch funktioniert diese Methode auch gut für dichte Eingaben, nur relativ langsamer.

Referenzen

[1]

Kenneth L. Clarkson und 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.

Beispiele

Erstellen Sie eine große dichte Matrix A für das Beispiel

>>> 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))

Wenden Sie die Transformation an, um eine neue Matrix mit 200 Zeilen zu erstellen

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

Jetzt ist die wahre Norm mit hoher Wahrscheinlichkeit nahe der skizzierten Norm in absolutem Wert.

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

Ähnlich bewahrt die Anwendung unserer Skizze die Lösung einer linearen Regression von \(\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]

Wie im Matrixnorm-Beispiel ist linalg.norm(A @ x - b) mit hoher Wahrscheinlichkeit nahe bei linalg.norm(A @ x_sketched - b).

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