Kavli Affiliate: David Gross

| First 5 Authors: Tim Fuchs, David Gross, Felix Krahmer, Richard Kueng, Dustin G. Mixon

| Summary:

Given an arbitrary matrix $Ainmathbb{R}^{ntimes n}$, we consider the

fundamental problem of computing $Ax$ for any $xinmathbb{R}^n$ such that $Ax$

is $s$-sparse. While fast algorithms exist for particular choices of $A$, such

as the discrete Fourier transform, there is currently no $o(n^2)$ algorithm

that treats the unstructured case. 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(n^3log n)$ operations. Next, given any unit vector

$xinmathbb{R}^n$ such that $Ax$ is $s$-sparse, our randomized fast transform

uses this representation of $A$ to compute the entrywise $epsilon$-hard

threshold of $Ax$ with high probability in only $O(sn +

epsilon^{-2}|A|_{2toinfty}^2nlog n)$ operations. In addition to a

performance guarantee, we provide numerical results that demonstrate the

plausibility of real-world implementation of our algorithm.

| Search Query: ArXiv Query: search_query=au:”David Gross”&id_list=&start=0&max_results=10