Sketching and Embedding Equivalence for Norms in Metric Spaces
Sketching and embedding techniques are explored by Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn in the context of metric spaces. This research delves into the equivalence between sketching and embedding for various norms, addressing topics such as compressing high-dimensional objects, similarity search, and sketching metrics in metric spaces. The main focus is on determining which metrics can be effectively sketched with a constant sketch size and approximation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sketching and Embedding are Equivalent for Norms Alexandr Andoni (Columbia) Robert Krauthgamer (Weizmann Inst) Ilya Razenshteyn (MIT) 1
Sketching Compress a massive object to a smallsketch Objects: high-dimensional vectors, matrices, graphs Similarity search, compressed sensing, numerical linear algebra Dimension reduction (Johnson, Lindenstrauss 1984): random projection on a low-dimensional subspace preserves distances d n When is sketching possible? 2
Similarity search Motivation: similarity search Model similarity as a metric Sketching may speed-up computation and allow indexing Interesting metrics: Euclidean Manhattan, Hamming ? distances Edit distance, Earth Mover s Distance etc. 3
Sketching metrics 0 1 1 0 1 Alice and Bob each hold a point from a metric space, x and y Both send ?-bit sketches to Charlie For ? > 0 and ? > 1 distinguish ?(?,?) ? ?(?,?) ?? Shared randomness, allow 1% probability of error Trade-off between ? and ? Alice Bob ? ? sketch(?) sketch(?) Charlie ?(?,?) ? or ?(?,?) ?? ? 4
Sketches Near Neighbor Search Near Neighbor Search (NNS): Given ?-point dataset ? A query ? within ? from some data point Return any data point within ?? from ? Sketches of size ? imply NNS with space ?? ? and a 1-probe query Polynomial space whenever ? = ?(1) 5
Sketching ? norms [Kushilevitz-Ostrovsky-Rabani 98]: can sketch Hamming space [Indyk 00]: can sketch ? for 0 < ? 2 via random projections using p-stable distributions For ? = 1 + ? one gets ? = ?(1/?2) Tight by [Woodruff 2004] For ? > 2 sketching ? is somewhat hard (Bar-Yossef, Jayram, Kumar, Sivakumar 2002), (Indyk, Woodruff 2005) To achieve ? = ?(1) one needs sketch size to be ? = ?1 2/? 6
The main question Which metrics can we sketch with constant sketch size and approximation? 7
Beyond ?norms: embeddings A map f: X Y is an embedding with distortion C, if for a, b from X: dX(a, b) / C dY(f(a), f(b)) dX(a, b) Reductions for geometric problems f f(a) Sketches of size s and approximation CD for X a Sketches of size s and approximation D for Y Y X f b f(b) 8
Metrics with good sketches: summary A metric X admits sketches with s, D = O(1), if: X = pfor p 2 X embeds into pfor p 2 with distortion O(1) Are there any other metrics with efficient sketches? We don t know! 9
The main result If a normed space ? admits sketches of size ? and approximation ?, then for every > 0 the space ? embeds into 1 ? with distortion ?(?? / ?) Embedding into p, p 2 A normed space: Rd equipped with a metric Examples: ? s, matrix norms (spectral, trace), EMD Rabani 1998) (Indyk 2000) (Kushilevitz, Ostrovsky, For norms Efficient sketches 10
Application: lower bounds for sketches Convert non-embeddability into lower bounds for sketches in a black box way No embeddings with distortion O(1) into 1 *in fact, any communication protocols No sketches* of size and approximation O(1) 11
Example 1: the Earth Movers Distance For ?: [ ] ? with zero average, ||?||??? is the cost of the best transportation of the positive part of ? to the negative part Initial motivation for this work Upper bounds: [Charikar 02, Indyk-Thaper 03, Naor-Schechtman 05, [A.-Do Ba-Indyk-Woodruff 09] Lower bound also holds for the minimum-cost matching metric on subsets No embedding into 1 ? with distortion O(1) [Naor-Schechtman 05] No sketches with D = O(1) and s = O(1) 12
Example 2: the Trace Norm For an n n matrix A define the Trace Norm(the Nuclear Norm) A to be the sum of the singular values Previously: lower bounds only for certain restricted classes of sketches [Li-Nguyen-Woodruff 14] Any sketch must satisfy ? log ? Any embedding into 1 requires distortion ? (Pisier 1978) ?? = 13
Linear embedding of X into 1- [Aharoni-Maurey-Mityagin 1985], Fourier analysis The sketch of the proof Good sketches for X ?:? 2 s.t. ? ||?1 ?2||? ||? ?1 ? ?2|| ?(||?1 ?2||?) ? and ? are non-decreasing, ?(?) > 0 for ? > 0 ?(?) 0 as ? 0 Uses that X is a norm Uniform embedding ? of X into 2 [Johnson-Randrianarivony 2006], Lipschitz extension Good sketches for (X) ||(?1,?2, ,??)||= maxi||??|| [A-Jayram-P tra cu 2010], Direct sum for Information Complexity ||?1 ?2|| 1 ||? ?1 ? ?2|| 1 ||?1 ?2|| ?? ||? ?1 ? ?2|| 10 Absence of certain Poincar -type inequalities on X Weak embedding ? of X into 2 Convex duality + compactness 14
Open problems Can one strengthen our theorem to sketches with O(1) size and approx. imply embedding into 1with distortion O(1) ? Equivalent to an old open problem from Functional Analysis [Kwapien 1969] Extend to a more general class of metrics (e.g., Edit Distance?) Other regimes: what about super-constant ?,? ? Linear sketches with ?(?) measurements and ?(?) approximation? 15
