Matching Map Recovery with an Unknown Number of Outliers

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

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 of the first set have their corresponding vector in the second set. If $n$ and $m$ are the sizes of these two sets, we assume that the matching map that should be recovered is defined on a subset of unknown cardinality $k^* \le \min(n,m)$. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(d\log(4nm/\alpha))^{1/4}$, then the true matching map can be recovered with probability $1-\alpha$. Interestingly, this threshold does not depend on $k^*$ and is the same as the one obtained in prior work in the case of $k = \min(n,m)$. The procedure for which the aforementioned property is proved is obtained by a data-driven selection among candidate mappings $\{\hat\pi_k:k\in[\min(n,m)]\}$. Each $\hat\pi_k$ minimizes the sum of squares of distances between two sets of size $k$. The resulting optimization problem can be formulated as a minimum-cost flow problem, and thus solved efficiently. Finally, we report the results of numerical experiments on both synthetic and real-world data that illustrate our theoretical results and provide further insight into the properties of the algorithms studied in this work.

Introduction

Matching map recovery is a fundamental task in fields ranging from computer vision (aligning two photos of the same building) to biology (matching cells across different sequencing technologies). The goal is to find which point in Dataset A corresponds to which point in Dataset B. Most existing theoretical frameworks assume a "clean" setup: either every point has a match, or we at least know exactly how many matches to look for. In the real world, this is rarely true. Sensors fail, different views capture different parts of a scene, and biological samples contain unique cells. This paper tackles the "outliers-on-both-sides" problem: we don't know which points are inliers, and we don't know the total number of true matches ($k^*$).

Surprisingly, researchers have proven that identifying these matches is statistically no harder than the case where every point is guaranteed to have a match, provided the signal-to-noise ratio (SNR) is sufficiently high.

Methodology: $k$-Least Sum of Squares ($k$-LSS)

The proposed approach, $k$-Least Sum of Squares ($k$-LSS), consists of two main components: optimization via graph theory and data-driven model selection.

Optimization via Graph Theory

For a fixed number of matches $k$, finding the best matching map is a combinatorial problem. However, it can be reformulated as a Minimum Cost Flow (MCF) problem. By adding a "source" and "sink" node to a bipartite graph representing the datasets, the optimal $k$ matches can be found in polynomial time using standard solvers.

Minimum Cost Flow formulation for the $k$-LSS problem.

Data-Driven Model Selection

To find the unknown $k^*$, the algorithm evaluates candidate mappings for different values of $k$. It monitors the "error" (the sum of squared distances between matched pairs). When $k < k^*$, the error grows slowly as it mostly adds noise. Once $k$ exceeds $k^*$, the error jumps significantly because the algorithm is forced to match "outliers" that are far apart. The algorithm uses this "jump" to stop and select the correct $k$.

Experimental Validation

The authors validated their approach using synthetic data, computer vision datasets (IMC-PT 2020), and single-cell RNA sequencing data.

Key Results

  • Theoretical Optimality: The authors proved that their threshold for recovery is minimax optimal, meaning no other algorithm can theoretically perform better under these conditions.
  • Robustness to Outliers: In synthetic tests with 60 inliers and 40 outliers, the model selection accurately identified $k=60$ as soon as the SNR passed the predicted theoretical threshold.
  • Biological Accuracy: On the pancreatic islet dataset, the algorithm achieved 97.88% accuracy in matching cells of the same type, performing as well as specialized biological alignment tools.
Performance of the data-driven selection procedure as a function of the signal-to-noise ratio. The top panel shows the estimated number of matches $\hat{k}$ converging to the true $k^*=60$ as SNR increases.

Discussion and Insights

  • The "No-Gap" Surprise: One of the most significant theoretical findings is that the statistical threshold for recovering the map is the same whether $k^*$ is known or unknown. In high dimensions, the "cost" of not knowing how many matches exist is negligible.
  • Dimension Matters: The recovery threshold scales with $d^{1/4}$ in high dimensions. As the number of features grows, the separation between points doesn't need to grow linearly to remain detectable.
  • Noise Agnosticism: The procedure is robust even if the exact noise level ($\sigma$) is unknown, as it can be estimated on-the-fly.

Limitations and Future Work

The current work assumes Gaussian, isotropic, and homoscedastic noise. Real-world noise can be heavy-tailed or heteroscedastic. Additionally, the framework is limited to injective (one-to-one) mappings; future work could extend this to one-to-many or many-to-many matchings common in complex data integration.

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 of the first set have their corresponding vector in the second set. If $n$ and $m$ are the sizes of these two sets, we assume that the matching map that should be recovered is defined on a subset of unknown cardinality $k^*\le \min(n,m)$. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(d\log(4nm/\alpha))^{1/4}$, then the true matching map can be recovered with probability $1-\alpha$. Interestingly, this threshold does not depend on $k^*$ and is the same as the one obtained in prior work in the case of $k = \min(n,m)$. The procedure for which the aforementioned property is proved is obtained by a data-driven selection among candidate mappings $\{\hat\pi_k:k\in[\min(n,m)]\}$. Each $\hat\pi_k$ minimizes the sum of squares of distances between two sets of size $k$. The resulting optimization problem can be formulated as a minimum-cost flow problem, and thus solved efficiently. Finally, we report the results of numerical experiments on both synthetic and real-world data that illustrate our theoretical results and provide further insight into the properties of the algorithms studied in this work.
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},
}

Loading related content...

Figure