TY - CHAP

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

AU - Khot, Subhash

AU - Naor, Assaf

N1 - Funding Information:
An extended abstract announcing this work appeared in the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. S.K. was supported by NSF CCF-1422159 and the Simons Foundation. A.N. was supported by NSF CCF-1412958, the Packard Foundation and the Simons Foundation. This work was carried out under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - 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) = ∞.

AB - 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) = ∞.

UR - http://www.scopus.com/inward/record.url?scp=85103627512&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85103627512&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-61887-2_8

DO - 10.1007/978-3-030-61887-2_8

M3 - Chapter

AN - SCOPUS:85103627512

T3 - Springer Optimization and Its Applications

SP - 185

EP - 204

BT - Springer Optimization and Its Applications

PB - Springer

ER -