Abstract: In real-world, many problems can be formulated as the alignment between two geometric patterns. Previously, a great amount of research focus on the alignment of 2D or 3D patterns, especially in the field of computer vision. Recently, the alignment of geometric patterns in high dimension finds several novel applications, and has attracted more and more attentions. However, the research is still rather limited in terms of algorithms. To the best of our knowledge, most existing approaches for high dimensional alignment are just simple extensions of their counterparts for 2D and 3D cases, and often suffer from the issues such as high complexities. In this paper, we propose an effective framework to compress the high dimensional geometric patterns and approximately preserve the alignment quality. As a consequence, existing alignment approach can be applied to the compressed geometric patterns and thus the time complexity is significantly reduced. Our idea is inspired by the observation that high dimensional data often has a low intrinsic dimension. We adopt the widely used notion “doubling dimension” to measure the extents of our compression and the resulting approximation. Finally, we test our method on both random and real datasets; the experimental results reveal that running the alignment algorithm on compressed patterns can achieve similar qualities, comparing with the results on the original patterns, but the running times (including the times cost for compression) are substantially lower.
Introduction
Geometric alignment—the process of finding the optimal spatial transformation to match two sets of points—is a cornerstone of computer vision. While traditionally focused on 2D and 3D spaces, modern applications such as matching word embeddings across languages, aligning protein-protein interaction (PPI) networks, and indoor localization require alignment in much higher dimensions (e.g., 50D to 500D).
The Earth Mover’s Distance (EMD) is the gold standard for measuring the difference between these sets due to its robustness to noise. However, EMD is computationally expensive, formulated as a min-cost flow problem. When used iteratively to find an optimal transformation, the computational complexity becomes a bottleneck that scales poorly with the number of points ($n$) and dimensions ($d$).
Methodology
The proposed framework leverages the observation that high-dimensional real-world data often possesses a low doubling dimension. Even when points are embedded in a 500D space, they typically lie on a much simpler, lower-dimensional manifold.
The Compression Framework
- Coreset Construction: The algorithm uses Gonzalez’s $k$-center clustering to identify $k$ representative points for both sets.
- Weight Assignment: Each representative point is weighted by the number of original points it represents, creating a simplified "coreset."
- Alignment: Existing alignment algorithms, such as the alternating minimization approach, are applied to these significantly smaller sets.
- Theoretical Guarantees: The authors provide a rigorous proof that alignment on these compressed sets yields a $(1 + O(\epsilon))$-approximation of the optimal alignment on the original data.
This approach acts as an independent preprocessing step, allowing any existing alignment algorithm to be "plugged in" for immediate performance gains.
Experimental Results
The framework was evaluated on synthetic manifolds in $\mathbb{R}^{500}$, linguistic word embeddings in $\mathbb{R}^{50}$, and PPI networks in $\mathbb{R}^{100}$.
As shown in Table 1, the algorithm achieved massive speedups on synthetic data. At a compression level of $\gamma = 1/50$, the total execution time (including compression) was 48.7 seconds, compared to 1418.2 seconds for the baseline—a 29x improvement—while maintaining an EMD value remarkably close to the original.
Results on real-world linguistic datasets (Table 2) further confirm the framework's fidelity. For language pairs like Spanish-English (sp-en) and Italian-English (it-en), the EMD with compression typically remained within 1.1x to 1.2x of the baseline, while reducing computation time from hundreds of seconds to under 10 seconds.
Conclusion
This research demonstrates that the complexity of high-dimensional alignment depends more on the underlying doubling dimension of the data than its ambient dimension. By reducing the number of points from $n$ to a small coreset $k$, the most expensive computational steps are performed on a fraction of the data. Future work may explore extending this framework to non-rigid transformations and developing automated methods for selecting optimal compression levels.
Summary updated