SKETCHING WITH KERDOCK'S CRAYONS: FAST SPARSIFYING TRANSFORMS FOR ARBITRARY LINEAR MAPS

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