Timezone: »

Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
Yik Chau (Kry) Lui · Gavin Weiguang Ding · Ruitong Huang · Robert McCann

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #103
In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure `how' wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the $L_2$-Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.

Author Information

Yik Chau (Kry) Lui (BorealisAI)
Gavin Ding (Borealis AI)
Ruitong Huang (Borealis AI)
Robert McCann (University of Toronto)

More from the Same Authors