The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics

DOI10.1137/1.9781611975482.109MaRDI QIDQ5236293zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Assaf Naor

Publication date 15 October 2019

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

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

Mathematics Subject Classification ID

Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: Andoni, Krauthgamer and Razenshteyn (AKR) proved (STOC 2015) that a finite-dimensional normed space $(X,|cdot{|}_X)$ admits a $O(1)$ sketching algorithm (namely, with $O(1)$ sketch size and $O(1)$ approximation) if and only if for every $varepsilonin(0,1)$ there exist $alphageqslant1$ and an embedding $f:Xoel{l}_{1-varepsilon}$ such that $|x-y{|}_{X}leqslant|f(x)-f(y){|}_{1-varepsilon}leqslantalpha|x-y{|}_X$ for all $x,yinX$. The "if part" of this theorem follows from a sketching algorithm of Indyk (FOCS 2000). The contribution of AKR is therefore to demonstrate that the mere availability of a sketching algorithm implies the existence of the aforementioned geometric realization. Indyk's algorithm shows that the "if part" of the AKR characterization holds true for any metric space whatsoever, i.e., the existence of an embedding as above implies sketchability even when $X$ is not a normed space. Due to this, a natural question that AKR posed was whether the assumption that the underlying space is a normed space is needed for their characterization of sketchability. We resolve this question by proving that for arbitrarily large $ninmathbbN$ there is an $n$-point metric space $(M(n),d_{M(n)})$ which is $O(1)$-sketchable yet for every $varepsilonin(0,frac12)$, if $alpha(n)geqslant1$ and $f_n:M(n)oel{l}_{1-varepsilon}$ are such that $d_{M(n)}(x,y)leqslant|f_n(x)-f_n(y){|}_{1-varepsilon}leqslantalpha(n)d_{M(n)}(x,y)$ for all $x,yinM(n)$, then necessarily $li{m}_{noinfty}alpha(n)=infty$.

Recommendations

• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Sketching and embedding are equivalent for norms
• Sketching and embedding are equivalent for norms
• On the distortion required for embedding finite metric spaces into normed spaces
• Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance

Cited in

(4)

• Sketching and embedding are equivalent for norms
• Near-optimal (Euclidean) metric compression
• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Sketching and embedding are equivalent for norms

This page was built for publication: The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics

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