The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics

Subhash Khot, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Andoni, Krauthgamer, and Razenshteyn (AKR) proved (STOC 2015) that a finite-dimensional normed space (X, ∥⋅∥X) admits a O(1) sketching algorithm (namely, with O(1) sketch size and O(1) approximation) if and only if for every ε ∈ (0, 1), there exist α⩾ 1 and an embedding f : X → ℓ1−ε such that ∥ x− y∥ X⩽ ∥ f(x) − f(y) ∥ 1ε⩽ α∥ x− y∥ X for all x, y ∈ X. 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 n∈ ℕ, there is an n-point metric space (M(n), dM(n)) which is O(1)-sketchable yet for every if α(n) ⩾ 1 and fn : M(n) → ℓ1−ε are such that dM(n)(x, y) ⩽ ∥ fn(x) − fn(y) ∥ 1ε⩽ α(n) dM(n)(x, y) for all x, y ∈ M(n), then necessarily limn→∞α(n) = ∞.

Original languageEnglish (US)
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer
Pages185-204
Number of pages20
DOIs
StatePublished - 2021

Publication series

NameSpringer Optimization and Its Applications
Volume168
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

ASJC Scopus subject areas

  • Control and Optimization

Fingerprint Dive into the research topics of 'The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics'. Together they form a unique fingerprint.

Cite this