Matching Map Recovery with an Unknown Number of Outliers

Arshak Minasyan, Tigran Galstyan, Sona Hunanyan, Arnak S. Dalalyan

Abstract

This paper addresses the challenge of matching two sets of high-dimensional data points in the presence of an unknown number of outliers on both sides. We introduce a robust framework, $k$-Least Sum of Squares ($k$-LSS), which leverages Minimum Cost Flow (MCF) for optimization and a data-driven model selection procedure to estimate the number of true matches. Our theoretical analysis reveals a "no-gap" result: recovery of the true matching map is possible at the same signal-to-noise ratio threshold regardless of whether the number of matches is known. Empirical results across synthetic, computer vision, and single-cell RNA-seq datasets demonstrate the framework's optimality and practical utility.

Introduction

Matching problems are fundamental across diverse fields, ranging from computer vision (image alignment) to bioinformatics (data integration). The core task is to identify a "matching map" between two sets of $d$-dimensional feature vectors. However, real-world datasets are frequently contaminated with outliers—points in one set that have no corresponding match in the other. While existing algorithms often assume a known number of matches ($k^*$) or restrict outliers to a single set, this work tackles the more realistic and difficult scenario where outliers exist on both sides and their quantity is unknown.

The $k$-Least Sum of Squares ($k$-LSS) Framework

To solve the matching problem, the authors propose the $k$-Least Sum of Squares ($k$-LSS) procedure. For a fixed number of matches $k$, the objective is to select $k$ pairs of points that minimize the total sum of squared Euclidean distances.

Figure 1: Bipartite matching formulated as a Minimum Cost Flow problem with source and sink nodes.

Although finding the optimal $k$ matches is a combinatorial challenge, it can be efficiently solved by mapping it to a Minimum Cost Flow (MCF) problem. By constructing a bipartite graph with additional source and sink nodes, standard polynomial-time optimization solvers can be employed to find the globally optimal set of $k$ matches.

Model Selection and the "Jump" Phenomenon

A critical contribution of this work is the method for estimating the unknown number of true matches, $k^*$. The authors developed a sequential algorithm that monitors the residual error (sum of squares) as $k$ increases. The intuition is that matching true "inliers" adds only minimal noise variance to the total error. Conversely, once all true matches are exhausted, the algorithm is forced to pair outliers, leading to a significant "jump" in the error curve.

Figure 6: Estimation of the number of matches $\hat{k}$ and noise level $\bar{\sigma}^2_{\hat{k}}$ showing the characteristic jump at the true number of matches.

By detecting this change point, the algorithm simultaneously estimates $k^*$ and the noise level $\sigma$. This data-driven approach allows for robust recovery without prior knowledge of the signal-to-noise ratio (SNR).

Theoretical Insights: The "No Gap" Result

Theoretically, the paper proves a surprising "no-gap" result. One might intuitively expect that not knowing $k^*$ would impose a statistical penalty, requiring a higher SNR for successful recovery. However, the authors demonstrate that the minimax separation rate—the minimum signal strength required to distinguish true matches from noise—is essentially identical whether $k^*$ is known or unknown.

The analysis also identifies two distinct regimes based on dimensionality $d$. In low-dimensional settings ($d \lesssim \log n$), the required separation is independent of $d$. In high-dimensional settings ($d \gtrsim \log n$), the required signal strength scales with $d^{1/4}$.

Experimental Validation

The $k$-LSS framework was validated across three domains:

  1. Synthetic Data: Using 100-dimensional Gaussian vectors, the authors confirmed that the empirical recovery thresholds align with their theoretical minimax rates.
  2. Computer Vision: On the IMC-PT 2020 dataset (SIFT descriptors of the "Reichstag" scene), the algorithm accurately estimated $k^* \approx 60$ matches. The presence of a clear change point in the error curve validated the model selection strategy in a complex, real-world feature space.
  3. Biomedical Data: In matching single-cell RNA-seq data (CEL-seq2 and Smart-seq2) of human pancreatic cells, the method achieved 97.88% cell-type level accuracy. This performance is comparable to specialized, domain-specific integration methods, highlighting the versatility of the general $k$-LSS approach.

Conclusion and Future Directions

This work provides a theoretically grounded and practically efficient solution for matching with unknown outliers. While the current framework assumes i.i.d. Gaussian noise and homoscedasticity, it sets a strong foundation for future extensions. Potential research directions include adapting the model for heavy-tailed or correlated noise, handling heteroscedasticity where noise levels vary across points, and extending the injective mapping to one-to-many or many-to-many matching scenarios common in complex data integration tasks.

Summary updated

Abstract

We consider the problem of finding the matching map between two sets of $d$-dimensional noisy feature-vectors. The distinctive feature of our setting is that we do not assume that all the vectors o...
BibTeX
@inproceedings{minasyan2023matching,
  author = {Arshak Minasyan and Tigran Galstyan and Sona Hunanyan and Arnak S. Dalalyan},
  title = {{Matching Map Recovery with an Unknown Number of Outliers}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=0Nrd4rUGuc},
}
Figure