Universität zu Köln

Fuchs, Tim, Gross, David, Krahmer, Felix, Kueng, Richard ORCID: 0000-0002-8291-648X and Mixon, Dustin (2022). SKETCHING WITH KERDOCK'S CRAYONS: FAST SPARSIFYING TRANSFORMS FOR ARBITRARY LINEAR MAPS. SIAM J. Matrix Anal. Appl., 43 (2). S. 939 - 953. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7162

Full text not available from this repository.

Abstract

Given an arbitrary matrix A is an element of R-mxn, we consider the fundamental problem of computing Ax for any x is an element of R-n 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(mn(2) logn+n(2) log(2) n) operations. Next, given any unit vector x is an element of R-n such that Ax is s-sparse, our randomized fast transform uses this representation of A to compute the entrywise is an element of-hard threshold of Ax with high probability in only O(sn + is an element of(-2)vertical bar vertical bar A vertical bar vertical bar(2)(2 ->infinity)(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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Fuchs, Tim UNSPECIFIED UNSPECIFIED UNSPECIFIED Gross, David UNSPECIFIED UNSPECIFIED UNSPECIFIED Krahmer, Felix UNSPECIFIED UNSPECIFIED UNSPECIFIED Kueng, Richard UNSPECIFIED orcid.org/0000-0002-8291-648X UNSPECIFIED Mixon, Dustin UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-680773
DOI:	10.1137/21M1438992
Journal or Publication Title:	SIAM J. Matrix Anal. Appl.
Volume:	43
Number:	2
Page Range:	S. 939 - 953
Date:	2022
Publisher:	SIAM PUBLICATIONS
Place of Publication:	PHILADELPHIA
ISSN:	1095-7162
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TRANSLATION-PLANES; SPARSE; ALGORITHM; SPREADS Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/68077