Text

Sketching with Kerdock's Crayons : Fast Sparsifying Transforms for Arbitrary Linear Maps

Given an arbitrary matrix A∈Rm×n, we consider the fundamental problem of computing Ax for any x∈Rn such that Ax is s-sparse. While fast algorithms exist for particular choices of A, such as the discrete Fourier transform, there are hardly any approaches that beat standard matrix-vector multiplication for realistic problem dimensions without such structural assumptions. In this paper, we devise a randomized approach to tackle the unstructured case. Our method relies on a representation of A in terms of certain real-valued mutually unbiased bases derived from Kerdock sets. In the preprocessing phase of our algorithm, we compute this representation of A in O(mn2logn+n2log2n) operations. Next, given any unit vector x∈Rn such that Ax is s-sparse, our randomized fast transform uses this representation of A to compute the entrywise ϵ-hard threshold of Ax with high probability in only O(sn+ϵ−2∥A∥22→∞(m+n)logm) operations. In addition to a performance guarantee, we provide numerical results that demonstrate the plausibility of real-world implementation of our algorithm.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS; Vol.43 No.2 April-June 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 939-952

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

SPARSE REPRESENTATION
SPARSIFYING TRANSFORM
RANDOMIZED MATRIX-VECTOR MULTIPLICATION

Info Detail Spesifik

https://doi.org/10.1137/21M1438992

Pernyataan Tanggungjawab

Tim Fuchs, David Gross, Felix Krahmer, Richard Kueng, Dustin Mixon

Versi lain/terkait

Lampiran Berkas

Komentar