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

DOI10.1137/1.9781611974331.CH24MaRDI QIDQ4575601zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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)