Exact Permutation Recovery Under Unknown Scalar Affine Transformation
Source: arXiv:2607.08628 · Published 2026-07-09 · By Tigran Galstyan, Avetik Karagulyan, Arshak Minasyan
TL;DR
This paper addresses the challenging problem of exact permutation recovery between two sets of noisy feature vectors when the underlying true features differ by an unknown scalar affine transformation (scaling and translation). Prior work considered permutation matching under additive noise without affine transformations, but real-world data often undergo unknown scalings and shifts, for example due to sensor calibration or coordinate changes. The authors propose a two-step approach: first estimate the unknown scalar affine parameters via data standardization (estimating scale and translation), then estimate the permutation by minimizing a Least Sum of Logarithms (LSL) cost function between the transformed datasets. Their main theoretical result establishes precise conditions on the minimal separation distance of the features under which exact permutation recovery is guaranteed with high probability. Crucially, they prove near-optimal minimax rates that match the non-affine setting under mild noise heteroscedasticity, despite the additional affine unknowns. The authors provide novel non-asymptotic concentration bounds on the affine parameter estimators and characterize how noise heterogeneity influences recovery. Extensive analysis links the permutation estimator to a tractable linear assignment problem solvable via the Hungarian algorithm. Experiments on synthetic data validate the method’s superiority over naive LSL ignoring affine effects, showing sharp phase transitions in recovery with respect to noise and separation distance.
Key findings
- Exact permutation recovery is achieved when the minimal separation distance κ(Z) among centralized observations Z scales as at least max{(d log n)^{1/4}, √log n, √ρ_σ} with probability ≥ 1-4δ (Theorem 2), where ρ_σ is the maximal noise magnitude ratio.
- The affine scaling estimator \hat{τ}_n, defined as the ratio of sample standard deviations of X and X#, concentrates tightly around the true scaling τ* with error bounds that scale as α_σ/√(λ^2 + d) up to log factors, where α_σ measures noise concentration and λ is the distortion-to-noise ratio (Theorem 1).
- Under mild heteroscedasticity (ρ_σ ≤ (d log n)^{1/2} ∨ log n), the required separation distance matches minimax lower bounds known for the non-affine case, showing optimality of standardization plus LSL approach.
- When the noise magnitude ratio ρ_σ is large (strong heteroscedasticity), a larger minimal separation is required, indicating that affine matching is statistically harder than non-affine.
- Directly applying LSL without affine parameter estimation leads to poor recovery, evidenced by a precision drop from 95% to 3% in synthetic experiments visualized via PCA (Fig 1).
- The optimization for permutation reduces to a linear assignment problem with cost matrix based on log distances after affine parameter estimation, solvable efficiently by the Hungarian algorithm.
- Noise heterogeneity influences both estimation error of affine parameters and permutation recovery conditions — the ratio of maximum to minimum noise variances drives the difficulty.
- The paper provides non-asymptotic high-probability concentration inequalities on sums of squared norms of centralized Gaussian vectors which underpin the affine parameter estimates.
Threat model
An adversary is implicitly modeled as additive Gaussian noise with unknown, possibly heterogeneous magnitudes corrupting two independent sets of high-dimensional feature vectors, composed with an unknown permutation and unknown scalar affine transform consisting of a positive scale and translation. The adversary cannot alter the overall generative model outside these constraints, such as inducing non-affine distortions or dependent noise.
Methodology — deep read
Threat Model & Assumptions: The authors assume two independent sets of noisy d-dimensional feature vectors X = {X_i} and X# = {X#_i}, related by an unknown permutation π*, scaling τ*, translation β*, and heterogeneous Gaussian noise. The adversary is abstracted as additive noise with unknown magnitudes σ_i, σ#_i, and unknown affine parameters τ*, β*. The objective is exact recovery of π* from noisy, affinely transformed observations.
Data: The model is synthetic and theoretical. Observations follow X_i = θ_i + σ_i ξ_i and X#_j = θ#_j + σ#_j ξ#_j with ξ and ξ# i.i.d standard Gaussian vectors. The key structural assumption is θ_i = τ* θ#_{π*(i)} + β*, and σ_i = τ* σ#_{π*(i)} for all i. No explicit real datasets are used, enabling precise control and analysis.
Algorithm: The affine parameters are estimated via data standardization: scale τ* estimated as the ratio of norms of centralized data (equation 3), translation β* as difference of means corrected by scale. The permutation π* is then estimated by minimizing the Least Sum of Logarithms (LSL) cost function over permutations (equation 4), which uses log squared distances between transformed centralized vectors. This leads to a computationally tractable linear assignment problem solvable by the Hungarian algorithm.
Training Regime: Not applicable — method and results are analytical and algorithmic rather than learned models. Bounds and estimators are derived theoretically.
Evaluation Protocol: Exact recovery is probabilistically bounded via high probability inequalities with failure δ. Conditions are given in Theorem 2 on minimal separation distance κ(Z) involving dimension d, sample size n, noise ratio ρ_σ, and confidence level δ. Precision is evaluated in synthetic experiments (Fig 1) comparing proposed affine LSL versus vanilla LSL.
Reproducibility: Code and datasets are not explicitly mentioned as released. Results rely on synthetic Gaussian models with specified parameters. Proofs are included in appendices. Implementation details for optimization via Hungarian algorithm are standard.
Example end-to-end: Given two sets X, X# with unknown affine relation, first compute mean vectors ¯X_n, ¯X#_n and norm sums; estimate scale \hat{τ}_n = sqrt(Σ||X_i − ¯X_n||^2 / Σ||X#_i − ¯X#_n||^2), translation \hat{β}_n = ¯X_n − \hat{τ}_n ¯X#_n; centralize and scale X and X#. Then build cost matrix M_{ij} = log(||Z_i − \hat{τ}_n Z#_j||^2). Finally solve assignment problem to find permutation \hat{π}_n minimizing total cost. Theory guarantees that under minimal separation conditions, \hat{π}_n = π* with high probability.
Technical innovations
- Novel two-step approach combining affine parameter estimation via data standardization with permutation estimation via minimizing Least Sum of Logarithms (LSL), enabling exact recovery under unknown scalar affine transformations.
- Derivation of non-asymptotic high-probability concentration bounds for the affine scaling parameter estimator \hat{τ}_n in the presence of heterogeneous, non-isotropic noise.
- Establishment of minimax optimal rates for minimal separation distance ensuring exact permutation recovery under unknown affine transformations, matching known lower bounds in mild heteroscedasticity regimes.
- Identification and theoretical quantification of the maximal noise magnitude ratio ρ_σ as a key parameter controlling difficulty and recovery thresholds in affine permutation matching.
Baselines vs proposed
- Vanilla Least Sum of Logarithms (LSL) ignoring affine transformation: precision = 0.03 vs proposed Affine LSL: precision = 0.95 (Fig 1 synthetic experiment).
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.08628.
Fig 5: Accuracies of vanilla LSL and Affine LSL (ours) on sentence matching task. For each pair we match 500 English sentences
Fig 6: PCA visualization of OPUS-100 en-fr (easy) and en-ky (hard) sentence embeddings. Note that here standardization changes the
Limitations
- Theoretical results require relatively strong assumptions, including Gaussian noise with known distribution and independence across samples.
- Affine transformation is restricted to scalar scaling and translation; more general affine or nonlinear transforms are not addressed.
- The noisy permutation recovery analysis focuses on exact recovery, leaving partial or approximate recovery unexamined.
- Strong heteroscedastic noise (large ρ_σ) leads to looser bounds and potentially suboptimal rates; the optimal dependence on ρ_σ remains an open question.
- No evaluation on real-world or benchmark datasets is presented, limiting practical validation.
- The estimation of the translation β* is analyzed implicitly and less explicitly than the scaling τ*, which may affect recovery nuances.
Open questions / follow-ons
- Can the recovery theory be extended beyond scalar affine transformations to full unknown affine or nonlinear transformations?
- What are the minimax lower bounds and tightness of recovery rates under strong heteroscedasticity (very large ρ_σ)?
- How robust is the method to model misspecifications, including non-Gaussian noise or dependent observations?
- Can the framework be adapted for partial or approximate permutation recovery, important for practical noisy data scenarios?
Why it matters for bot defense
Bot-defense and CAPTCHA systems often rely on robust feature matching under adversarially perturbed inputs or transformations caused by different acquisition conditions. This paper’s methodology and theoretical guarantees provide a principled approach to recover exact correspondences between feature sets despite unknown scalar scaling and translation. For CAPTCHA practitioners, understanding and implementing affine-invariant feature matching can improve resilience against evasion tactics that rely on subtle transformations of challenge elements. The Least Sum of Logarithms cost with standardized data may serve as a computationally feasible matching strategy. However, large noise heterogeneity, which might occur due to varying environmental factors or distortions from bots, can increase recovery difficulty, highlighting a potential vulnerability if noise characteristics are adversarially manipulated. Overall, integrating affine-invariant permutation recovery mechanisms could improve CAPTCHA validation robustness but requires careful consideration of noise heterogeneity effects.
Cite
@article{arxiv2607_08628,
title={ Exact Permutation Recovery Under Unknown Scalar Affine Transformation },
author={ Tigran Galstyan and Avetik Karagulyan and Arshak Minasyan },
journal={arXiv preprint arXiv:2607.08628},
year={ 2026 },
url={https://arxiv.org/abs/2607.08628}
}