Sparse Recovery for Orthogonal Polynomial Transforms

Anna Gilbert, Albert Gu, Christopher Re +2

In this paper we consider the following sparse recovery problem. We have query access to a vector $\vx \in \R^N$ such that $\vhx = \vF \vx$ is $k$-sparse (or nearly $k$-sparse) for…