Perfect Matching Map Recovery Under Unknown Scalar Affine Transformation

Tigran Galstyan, Avetik Karagulyan, Arshak Minasyan
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1628-1649, 2026.

Abstract

We study the problem of matching two sets of noisy feature vectors when underlying true features are related by an unknown scalar affine transformation. Our method comprises two primary steps. First, we standardize the feature vectors to estimate the unknown scalar affine transformation. Subsequently, we estimate the permutation by minimizing the Least Sum of Logarithms (LSL) between two sets of observations using the estimated transformation. Our main result shows that the unknown permutation can be perfectly recovered given that the minimal separation distance of true feature vectors scales as $\sqrt{\rho_\sigma} \vee (d\log n)^{1/4} \vee \sqrt{\log n}$, where $d$ is the ambient dimension, $n$ is the sample size, and $\rho_\sigma$ is the maximal ratio of noise magnitudes. Interestingly, the obtained rate, under mild heteroscedasticity, coincides with that of the non-affine setting. We additionally demonstrate that there exist configurations requiring a larger minimal separation distance for perfect recovery. The latter makes the matching problem more challenging from minimax perspective compared to the non-affine setting. Consequently, we show that in the problem of feature matching, standardizing the data implicitly estimates the scalar affine parameters. As part of our analysis, we prove non-asymptotic concentration bounds for the affine parameter estimators in the presence of heterogeneous noise magnitudes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-galstyan26a, title = {Perfect Matching Map Recovery Under Unknown Scalar Affine Transformation}, author = {Galstyan, Tigran and Karagulyan, Avetik and Minasyan, Arshak}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1628--1649}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/galstyan26a/galstyan26a.pdf}, url = {https://proceedings.mlr.press/v337/galstyan26a.html}, abstract = {We study the problem of matching two sets of noisy feature vectors when underlying true features are related by an unknown scalar affine transformation. Our method comprises two primary steps. First, we standardize the feature vectors to estimate the unknown scalar affine transformation. Subsequently, we estimate the permutation by minimizing the Least Sum of Logarithms (LSL) between two sets of observations using the estimated transformation. Our main result shows that the unknown permutation can be perfectly recovered given that the minimal separation distance of true feature vectors scales as $\sqrt{\rho_\sigma} \vee (d\log n)^{1/4} \vee \sqrt{\log n}$, where $d$ is the ambient dimension, $n$ is the sample size, and $\rho_\sigma$ is the maximal ratio of noise magnitudes. Interestingly, the obtained rate, under mild heteroscedasticity, coincides with that of the non-affine setting. We additionally demonstrate that there exist configurations requiring a larger minimal separation distance for perfect recovery. The latter makes the matching problem more challenging from minimax perspective compared to the non-affine setting. Consequently, we show that in the problem of feature matching, standardizing the data implicitly estimates the scalar affine parameters. As part of our analysis, we prove non-asymptotic concentration bounds for the affine parameter estimators in the presence of heterogeneous noise magnitudes.} }
Endnote
%0 Conference Paper %T Perfect Matching Map Recovery Under Unknown Scalar Affine Transformation %A Tigran Galstyan %A Avetik Karagulyan %A Arshak Minasyan %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-galstyan26a %I PMLR %P 1628--1649 %U https://proceedings.mlr.press/v337/galstyan26a.html %V 337 %X We study the problem of matching two sets of noisy feature vectors when underlying true features are related by an unknown scalar affine transformation. Our method comprises two primary steps. First, we standardize the feature vectors to estimate the unknown scalar affine transformation. Subsequently, we estimate the permutation by minimizing the Least Sum of Logarithms (LSL) between two sets of observations using the estimated transformation. Our main result shows that the unknown permutation can be perfectly recovered given that the minimal separation distance of true feature vectors scales as $\sqrt{\rho_\sigma} \vee (d\log n)^{1/4} \vee \sqrt{\log n}$, where $d$ is the ambient dimension, $n$ is the sample size, and $\rho_\sigma$ is the maximal ratio of noise magnitudes. Interestingly, the obtained rate, under mild heteroscedasticity, coincides with that of the non-affine setting. We additionally demonstrate that there exist configurations requiring a larger minimal separation distance for perfect recovery. The latter makes the matching problem more challenging from minimax perspective compared to the non-affine setting. Consequently, we show that in the problem of feature matching, standardizing the data implicitly estimates the scalar affine parameters. As part of our analysis, we prove non-asymptotic concentration bounds for the affine parameter estimators in the presence of heterogeneous noise magnitudes.
APA
Galstyan, T., Karagulyan, A. & Minasyan, A.. (2026). Perfect Matching Map Recovery Under Unknown Scalar Affine Transformation. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1628-1649 Available from https://proceedings.mlr.press/v337/galstyan26a.html.

Related Material