scipy.linalg.

clarkson_woodruff_transform#

scipy.linalg.clarkson_woodruff_transform(input_matrix, sketch_size, rng=None, *, seed=None)[источник]#

Применяет преобразование Кларксона-Вудраффа/скетч к входной матрице.

Для заданной input_matrix A размера (n, d), вычислить матрицу A' размера (sketch_size, d), так что

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

с высокой вероятностью через преобразование Кларксона-Вудраффа, также известное как матрица CountSketch.

Параметры:

input_matrixarray_like, shape (…, 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 является int, новый RandomState используется экземпляр, инициализированный с seed.
Если seed уже является Generator или RandomState экземпляр, тогда этот экземпляр используется.

Изменено в версии 1.15.0: В рамках SPEC-007 переход от использования numpy.random.RandomState to numpy.random.Generator, этот ключевое слово было изменено с seed to rng. В переходный период оба ключевых слова будут продолжать работать, хотя только одно может быть указано за раз. После переходного периода вызовы функций, использующие seed ключевое слово будет выдавать предупреждения. Поведение обоих seed и rng описаны выше, но только rng ключевое слово должно использоваться в новом коде.

Возвращает:

A’array_like: Эскиз входной матрицы A, размера (sketch_size, d).

Примечания

Чтобы сделать утверждение

\[\|Ax\| \approx \|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 формат обеспечивает самое быстрое время вычисления для разреженного ввода.

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