English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We initiate the study of trade-offs between sparsity and the number ofmeasurements in sparse recovery schemes for generic norms. Specifically, for anorm $\|\cdot\|$, sparsity parameter $k$, approximation factor $K>0$, andprobability of failure $P>0$, we ask: what is the minimal value of $m$ so thatthere is a distribution over $m \times n$ matrices $A$ with the property thatfor any $x$, given $Ax$, we can recover a $k$-sparse approximation to $x$ inthe given norm with probability at least $1-P$? We give a partial answer tothis problem, by showing that for norms that admit efficient linear sketches,the optimal number of measurements $m$ is closely related to the doublingdimension 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 knownmeasurement bounds in our general framework (for the $\ell_p$ norms, $p \in[1,2]$) as well as provide new, measurement-efficient schemes (for theEarth-Mover Distance norm). The latter result directly implies more succinctlinear sketches for the well-studied planar $k$-median clustering problem.Finally, our lower bound for the doubling dimension of the EMD norm enables usto address the open question of [Frahling-Sohler, STOC'05] about the spacecomplexity of clustering problems in the dynamic streaming model.

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