从少量采样数据恢复水土距离矩阵，加速复杂数据的嵌入分析。
Recovering Wasserstein Distance Matrices from Few Measurements
- 基于Nyström方法，仅需计算约d log(d)列即可估计距离矩阵
- 在仅10%列数采样的情况下，对MedMNIST数据分类仍保持稳定
- 相比传统矩阵补全，该方法在相同采样预算下性能更优
本文提出两种算法，从少量样本中估计平方 Wasserstein 距离矩阵。这类矩阵常用于多维缩放（MDS）或 Isomap 等流形学习嵌入，但计算成本远高于欧氏距离矩阵。研究分析了上三角采样下的矩阵补全与 Nyström 补全方法，其中只需计算 𝒪(d log(d)) 列，d 为期望嵌入维度。证明了 MDS 在 Nyström 补全下的稳定性，并显示在固定采样距离预算下，其性能优于传统矩阵补全。最后实验表明，在仅计算 10% 列的情况下，使用 Nyström 估计的距离矩阵嵌入组织化 CMNIST（OrganCMNIST）数据，仍能实现稳定的分类表现。
原文摘要 · Abstract (English)
This paper proposes two algorithms for estimating square Wasserstein distance matrices from a small number of entries. These matrices are used to compute manifold learning embeddings like multidimensional scaling (MDS) or Isomap, but contrary to Euclidean distance matrices, are extremely costly to compute. We analyze matrix completion from upper triangular samples and Nyström completion in which $\mathcal{O}(d\log(d))$ columns of the distance matrices are computed where $d$ is the desired embedding dimension, prove stability of MDS under Nyström completion, and show that it can outperform matrix completion for a fixed budget of sample distances. Finally, we show that classification of the OrganCMNIST dataset from the MedMNIST benchmark is stable on data embedded from the Nyström estimation of the distance matrix even when only 10\% of the columns are computed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。