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

Subhash Khot () and Assaf Naor ()
Additional contact information
Subhash Khot: New York University
Assaf Naor: Princeton University

A chapter in Harmonic Analysis and Applications, 2021, pp 185-204 from Springer

Abstract: 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 $$\alpha \geqslant 1$$ and an embedding f : X → ℓ 1−ε such that ∥ x − y ∥ X ⩽ ∥ f ( x ) − f ( y ) ∥ 1 − ε ⩽ α ∥ x − y ∥ X $$\|x-y\|{ }_X\leqslant \|f(x)-f(y)\|{ }_{1-\varepsilon }\leqslant \alpha \|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 ∈ ℕ $$n\in \mathbb N$$ , there is an n-point metric space (M(n), d M(n)) which is O(1)-sketchable yet for every ε ∈ ( 0 , 1 2 ) $$\varepsilon \in (0,\frac 12)$$ , if α ( n ) ⩾ 1 $$\alpha (n)\geqslant 1$$ and f n : M(n) → ℓ 1−ε are such that d M ( n ) ( x , y ) ⩽ ∥ f n ( x ) − f n ( y ) ∥ 1 − ε ⩽ α ( n ) d M ( n ) ( x , y ) $$d_{M(n)}(x,y)\leqslant \|f_n(x)-f_n(y)\|{ }_{1-\varepsilon }\leqslant \alpha (n) d_{M(n)}(x,y)$$ for all x, y ∈ M(n), then necessarily limn→∞ α(n) = ∞.

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-61887-2_8

Ordering information: This item can be ordered from
http://www.springer.com/9783030618872

DOI: 10.1007/978-3-030-61887-2_8

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().