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

DOI10.1137/1.9781611974331.CH24zbMATH Open1410.68115arXiv1504.01076OpenAlexW771946922MaRDI QIDQ4575601FDOQ4575601

Authors: Artūrs Bačkurs, Ilya Razenshteyn, David P. Woodruff, Piotr Indyk 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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 $|cdot|$, sparsity parameter $k$, approximation factor $K>0$, and probability of failure $P>0$, we ask: what is the minimal value of $m$ so that there is a distribution over $mimesn$ matrices $A$ with the property that for any $x$, given $Ax$, we can recover a $k$-sparse approximation to $x$ in the given norm with probability at least $1-P$? We give a partial answer to this problem, by showing that for norms that admit efficient linear sketches, the optimal number of measurements $m$ is closely related to the doubling dimension of the metric induced by the norm $|cdot|$ on the set of all $k$-sparse vectors. By applying our result to specific norms, we cast known measurement bounds in our general framework (for the $el{l}_p$ norms, $pin[1,2]$) as well as provide new, measurement-efficient schemes (for the Earth-Mover Distance norm). The latter result directly implies more succinct linear sketches for the well-studied planar $k$-median clustering problem. Finally, our lower bound for the doubling dimension of the EMD norm enables us to address the open question of [Frahling-Sohler, STOC'05] about the space complexity of clustering problems in the dynamic streaming model.

Full work available at URL: https://arxiv.org/abs/1504.01076

Recommendations

• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Sketching and embedding are equivalent for norms
• Sketching and embedding are equivalent for norms

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (5)

• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On deterministic sketching and streaming for sparse recovery and norm estimation
• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Non-negative sparse regression and column subset selection with \(L_1\) error

This page was built for publication: Nearly-optimal bounds for sparse recovery in generic norms, with applications to \(k\)-median sketching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575601)