Sketching with Kerdock's crayons: Fast sparsifying transforms for arbitrary linear maps

Tim Fuchs, David Gross, Felix Krahmer +2

Given an arbitrary matrix $A\in {\mathbb{R}}^{n\times n}$, we consider the fundamental problem of computing $Ax$ for any $x\in {\mathbb{R}}^n$ such that $Ax$ is $s$-sparse. While fast al…