Sketching and Embedding are Equivalent for Norms

Alexandr Andoni, Robert Krauthgamer, Ilya Razenshteyn

TL;DR

This paper proves a fundamental equivalence in theoretical computer science: for normed spaces, the ability to create "efficient sketches" (small summaries that preserve distances) is essentially the same as the ability to embed that space into an $\ell_1$ (or $\ell_{1-\epsilon}$) space. This result allows the authors to prove that important distances like the Earth Mover’s Distance (EMD) and the Trace norm cannot be sketched efficiently, resolving several open questions from 2006.

What Problem Does This Paper Address?

In modern data science, we often deal with massive high-dimensional vectors. To compare them quickly, we use sketching: a process of compressing a large input into a tiny "sketch" such that the distance between two original inputs can be estimated just by looking at their sketches.

A central question in the field, posed by Guha and Indyk in 2006, is: Which metric spaces allow for efficient sketching? We define "efficient" as achieving a constant approximation of the distance using a constant sketch size (independent of the data's dimension).

We already knew that if a space could be "embedded" (mapped geometrically) into an $\ell_p$ space for $p \in (0, 2]$, it could be sketched efficiently. The big mystery was the converse: Is embedding the only way to get efficient sketches? This paper tackles that question for the broad and important category of normed spaces.

Methods

The authors bridge the gap between communication complexity (the study of how much information two parties need to exchange) and functional analysis (the study of vector spaces and mappings). Their proof follows a multi-step "pipeline":

  1. Information-Theoretic Step: They show that an efficient sketching protocol for a normed space $X$ implies the absence of certain "Poincaré-type inequalities." This essentially means the space doesn't have a specific kind of rigid structure that prevents compression.
  2. Threshold Maps: They use convex duality to convert the sketching protocol into a "threshold map"—a very weak type of geometric embedding into a Hilbert space.
  3. Analytic Step: Using sophisticated tools from non-linear functional analysis (specifically work by Aharoni, Maurey, Mityagin, and Nikishin), they "upgrade" this weak threshold map into a uniform embedding, and finally into a linear embedding into $\ell_{1-\epsilon}$.
  4. Sum-Products: For norms that are "closed under sum-products" (meaning you can combine multiple instances of the space into a larger one of the same type), they show the equivalence holds for embedding into $\ell_1$ exactly.

Datasets

As a theoretical research paper, this work does not use empirical datasets for training or benchmarking. Instead, it provides mathematical proofs concerning specific metric spaces and norms, including:

  • $\ell_p$ norms: The standard Euclidean and Manhattan distances.
  • Earth Mover’s Distance (EMD): Used extensively in computer vision and image retrieval.
  • Trace Norm (Nuclear Norm): Used in matrix completion and machine learning.
  • Hamming Space: A fundamental metric for bitstrings.

Key Insights and Ideas

  • The Algorithmic-Geometric Link: The most profound insight is that the algorithmic limit of data compression (sketching) is dictated by the geometric properties of the space (embeddability). If you can't map it to $\ell_1$, you can't sketch it.
  • Kwapien’s Problem: The authors discover that proving the equivalence for all general norms (without specific restrictions) is actually equivalent to solving a famous open problem in functional analysis posed by Kwapien in 1969. This highlights how deeply the roots of computer science are buried in classical mathematics.
  • Hardness of EMD and Trace Norm: By proving this equivalence, the authors can "import" known non-embeddability results from geometry to prove that EMD and the Trace norm are fundamentally hard to sketch.

Key Results

  • Characterization Theorem: A finite-dimensional normed space allows efficient sketches if and only if it linearly embeds into $\ell_{1-\epsilon}$ with constant distortion.
  • Lower Bounds for EMD: The paper provides the first sketching lower bound for the planar Earth Mover’s Distance, showing it does not admit constant-size, constant-approximation sketches.
  • Lower Bounds for Trace Norm: They prove a quantitative lower bound for the Trace norm: any sketch achieving approximation $D$ must have size $s$ such that $sD = \Omega(\frac{\sqrt{n}}{\log n})$, where $n$ is the matrix dimension.

Limitations and Future Work

  • General Metrics: The results are primarily for normed spaces. While the authors suspect a similar equivalence might hold for general metric spaces, they note that the current proof relies heavily on the linear structure of norms. In fact, they point out known counter-examples for general metrics (like the Heisenberg group) where efficient sketching is possible despite poor $\ell_1$ embeddability.
  • Dimension Dependence: Theorem 1.3 includes a $\log(\text{dim } X)$ factor in the distortion. Removing this dependence for general norms remains tied to the unresolved Kwapien’s problem.
  • Non-Normed Distances: Distances like Edit Distance, which are not norms, remain a major frontier for this line of research.

Summary updated

Abstract

An outstanding open question posed by Guha and Indyk in 2006 asks to characterize metric spaces in which distances can be estimated using efficient sketches. Specifically, we say that a sketching algorithm is efficient if it achieves constant approximation using constant sketch size. A well-known result of Indyk (J. ACM, 2006) implies that a metric that admits a constant-distortion embedding into $\ell_p$ for $p\in(0,2]$ also admits an efficient sketching scheme. But is the converse true, i.e., is embedding into $\ell_p$ the only way to achieve efficient sketching? We address these questions for the important special case of normed spaces, by providing an almost complete characterization of sketching in terms of embeddings. In particular, we prove that a finite-dimensional normed space allows efficient sketches if and only if it embeds (linearly) into $\ell_{1-\varepsilon}$ with constant distortion. We further prove that for norms that are closed under sum-product, efficient sketching is equivalent to embedding into $\ell_1$ with constant distortion. Examples of such norms include the Earth Mover's Distance (specifically its norm variant, called Kantorovich-Rubinstein norm), and the trace norm (a.k.a. Schatten $1$-norm or the nuclear norm). Using known non-embeddability theorems for these norms by Naor and Schechtman (SICOMP, 2007) and by Pisier (Compositio. Math., 1978), we then conclude that these spaces do not admit efficient sketches either, making progress towards answering another open question posed by Indyk in 2006. Finally, we observe that resolving whether "sketching is equivalent to embedding into $\ell_1$ for general norms" (i.e., without the above restriction) is equivalent to resolving a well-known open problem in Functional Analysis posed by Kwapien in 1969.
BibTeX
@inproceedings{andoni2014sketching,
  author = {Alexandr Andoni and Robert Krauthgamer and Ilya Razenshteyn},
  title = {{Sketching and Embedding are Equivalent for Norms}},
  booktitle = {STOC},
  year = {2014},
  doi = {10.1145/2746539.2746552},
}
Figure