Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching

Arturs Backurs, Piotr Indyk, Eric Price +2

We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm $\Vert \cdot \Vert$, sparsity par…