Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
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 ||·||, sparsity parameter k, approximation factor K > 0, and probability of failure P > 0, we ask: what is the minimal value of m so that th...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/113845 https://orcid.org/0000-0001-7546-6313 https://orcid.org/0000-0002-7983-9524 https://orcid.org/0000-0002-3962-721X |