Source-linked AI summary
Recovery Theory for Projected Power Iterations in Permutation Synchronization
Vahan Huroyan, Gilad Lerman
TL;DR
Permutation synchronization asks whether unknown permutations can be recovered from sparse, corrupted relative measurements. The paper analyzes projected power iteration with a spectral initializer and proves a basin-uniform trajectory contraction. Under the stated conditions, one update yields vanishing block error and subsequent iterates remain almost exact uniformly over time.
Problem
The task is to recover unknown permutations, up to a common right permutation, from noisy relative-permutation observations that may be sparse and corrupted.
Source: §1 · p. 1Method
The paper proves prescribed-block one-step recovery and a contraction that holds simultaneously for every estimate in a fixed-margin majority basin, including data-dependent estimates.
Source: §1 · pp. 2–3Results
δ_k+1 ≤ γ_nδ_k + ξ_n, with γ_n=O(m/(npπ0^2)) and ξ_n=O(e^-cnpπ0+e^-cnpπ0^2+log n/n), yielding uniform-in-iteration almost-exact recovery.
Source: §1 · p. 2Takeaways & Limitations
Under a stronger all-block signal condition, PPM reaches exact recovery after finitely many iterations.
Source: §1 · p. 3For varying supports in partial-permutation synchronization, the paper gives co-visibility bounds but does not establish general end-to-end recovery.
Source: §5 · p. 20
Abstract
from arXiv · showhide
We study the projected power method (PPM) for synchronizing \(n\) unknown permutations of \(m\) objects under a possibly sparse uniform corruption model. Each pair is observed with probability \(p\), and an observed measurement is uncorrupted with probability \(\pi_0\) and is otherwise an independent uniform permutation. Under \(\log m=o(np\pi_0^2)\), we prove exact one-step recovery (with high probability) of each prescribed block for an independent estimate with a fixed positive majority of correct blocks. When \(np\ge C_0\log n\) and \(m=o(np\pi_0^2)\), we prove that one high-probability event yields a block-error contraction simultaneously for every estimate whose optimally aligned error is at most \(0.5-\epsilon\). The contraction factor is \(O(m/(np\pi_0^2))\) and the error floor is \(O(e^{-cnp\pi_0}+e^{-cnp\pi_0^2}+{\log n}/{n})\). Consequently, one update maps every possibly data-dependent estimate in this basin to vanishing block error, and all subsequent iterates remain almost exact uniformly over the iteration index. The one-step and trajectory results extend to independent, non-identically distributed, permutation-valued corruptions with mean \(m^{-1} \mathbf{1}\mathbf{1}^{\top}\). Under the uniform model, a reference-block spectral initializer has aligned block error \(O_{\mathbb P}(m/(np\pi_0^2))\), yielding an end-to-end almost-exact recovery guarantee. Under a stronger all-block signal condition, PPM reaches exact recovery after finitely many iterations. The theory transfers exactly to partial permutations with common support; for varying supports, we establish deterministic and probabilistic co-visibility margins.
1. Introduction
Permutation synchronization recovers unknown object correspondences from noisy relative permutations, up to a common right permutation. This paper analyzes projected power iteration under sparse uniform corruption and establishes recovery guarantees for its data-dependent trajectory.
1. Introduction
- An independent estimate with a fixed positive majority of correct blocks permits exact one-step recovery of each prescribed block with high probability.The one-step result cannot be iterated directly because later PPM iterates depend on the same measurements.Source: §1 · p. 2
- δ_k+1 ≤ γ_nδ_k + ξ_n contracts block error simultaneously throughout the majority basin, yielding uniform-in-iteration almost-exact recovery.The contraction factor is O(m/(npπ0^2)); the error floor is O(e^-cnpπ0 + e^-cnpπ0^2 + log n/n).Source: §1 · p. 2
- The reference-block spectral initializer has aligned block error O_P(m/(npπ0^2)) under the uniform model.The stated trajectory theorem gives each fixed refinement an additional factor m/(npπ0^2) until the error floor is reached.Source: §1 · p. 3
- One-step and trajectory results extend to independent, non-identically distributed permutation-valued corruptions with mean m^-1 11^T.Extending the fixed-reference spectral initializer and end-to-end result beyond the uniform law additionally requires block-exchangeability.Source: §1 · p. 3
- Under a stronger all-block signal condition, the PPM trajectory reaches exact recovery after finitely many iterations.This is stronger than vanishing error fraction: uniform-in-iteration almost-exact recovery does not require the number of incorrect blocks to vanish.Source: §1 · pp. 2–3
- For fixed m and π0, np ≥ C0 log n yields end-to-end uniform-in-iteration almost-exact recovery, and a sufficiently large constant at that degree scale suffices for exact recovery.The expected number of observed pairs is then of order n log n rather than n^2.Source: §1 · p. 3
- When p and π0 are bounded below, m=o(n) suffices; with p=1 and fixed m, almost-exact recovery holds for π0≫n^-1/2, while exact recovery needs a stronger signal scale.More generally, the stated almost-exact regime is m=o(npπ0^2), while exact recovery additionally requires the all-block log n scale.Source: §1 · p. 3
- With common support, partial-permutation synchronization inherits the full-permutation end-to-end theory; varying supports receive co-visibility bounds, not a general recovery guarantee.The common-support result replaces m with the support size.Source: §1 · p. 4
2. Mathematical Setting for Permutation Synchronization
The setting represents each observation by an unknown permutation and measures noisy relative permutations between pairs. The paper studies sparse uniform corruption and contrasts blockwise projected power iteration with spectral estimation.
2. Mathematical Setting for Permutation Synchronization
- Each pair is observed independently; in the complete-observation specialization, a measurement is drawn from the uncorrupted or uniform-random permutation component.A uniform random permutation can coincide with the ground-truth relative permutation, so the equality probability is π0+(1−π0)/m!.Source: §2 · p. 4
- Permutation synchronization seeks the unknown permutation matrices up to a common right permutation, using noisy measurements of their relative permutations.The measurements are stored as off-diagonal blocks of a block matrix.Source: §2 · p. 4
- PPM alternates multiplication by the measurement matrix with blockwise projection onto permutations, keeping every iterate feasible for the discrete problem.The spectral alternative computes an eigenspace and then rounds its blocks; PPM instead repeats multiplication and projection.Source: §2 · p. 5
3. Projected Power Method
The projected power method initializes from the leading eigenspace of the measurement matrix and repeatedly updates each block by multiplication and projection. The paper's stated analysis shows that this spectral initializer enters the positive-overlap regime under the trajectory assumptions.
3. Projected Power Method
- Each PPM update multiplies the current estimate by the preprocessed measurement matrix and projects each resulting block onto the permutation set.The assignment problem uses a fixed deterministic tie-breaking rule when the maximizer is not unique.Source: §3 · p. 5
- The spectral initializer projects each block of the leading m-dimensional eigenspace onto the permutation set, with a factor n in the assignment weights.The factor n does not change the assignment solution and places population blocks on the scale of permutation matrices.Source: §3 · p. 5
- Under np ≥ C0 log n and m=o(npπ0^2), the initializer has vanishing aligned block error and enters the positive-overlap regime.The Hungarian algorithm is used to solve the linear assignment problem.Source: §3 · p. 5
4. Theoretical Analysis
The theoretical analysis establishes exact one-step recovery and high-probability uniform contraction for estimates in a positive-overlap basin, then develops the iteration analysis and spectral initialization. It also identifies an extension to non-identically distributed permutation-valued corruptions under a mean condition.
4.1. Definitions and Assumptions.
- One-step recovery and uniform contraction extend to independent, not necessarily identically distributed, permutation-valued corruptions whose means equal m^-1 11^T.The stated results retain their conclusions under the other assumptions of the corresponding theorems; uniform corruption from a transitive subgroup is one example.Source: §4.1 · p. 6
- The spectral-initialization guarantees also extend under the mean condition when the gauged corruption array is block-exchangeable.Block exchangeability is used in the final fixed-reference step transferring the global spectral-projector bound to the first reference block.Source: §4.1 · p. 6
4.2. Supporting Lemmas.
- The supporting analysis uses concentration bounds for sparse permutation noise, the observed signal gap, centered randomly observed blocks, and read-2 families.These bounds support the one-step recovery and data-dependent iterative contraction analyses.Source: §4.2 · pp. 7–8
4.3. One-step recovery under independent estimates.
- The one-step proof separates the observed uncorrupted signal gap from centered corrupted noise, then controls both to recover each prescribed block.The estimate’s independence permits conditioning on it; the signal gap is controlled uniformly over competing permutations, while the centered corrupted contribution is bounded separately.Source: §4.3 · pp. 9–10
- Under positive overlap and an independent estimate, the per-block error probability is at most C exp(-cnpπ0) + 2m exp(-c0npπ0^2).The theorem’s per-block scaling assumption absorbs the dimension factor to give its cleaner bound; log m = o(npπ0^2) is stated as a convenient sufficient condition.Source: §4.3 · p. 9
- Simultaneous exact recovery of all blocks holds with probability at least 1−Cn exp(−cnpπ0)−Cn exp(−cnpπ0²), with an additional log n cost over per-block recovery.The per-block theorem requires log m=o(npπ0²).Source: §4.3 · p. 11
4.4. Basin-Uniform Contraction for Data-Dependent Estimates.
- On a single event of probability at least 1−O(n^−β), the contraction bound holds for every estimate with δt≤0.5−ϵ, including estimates chosen after observing measurements.The stated contraction scale is bounded by Cβϵ^−2m/(npπ0²)+C[e^−cnpπ0+e^−cnpπ0²+log n/n].Source: §4.4 · pp. 11, 13
- The contraction guarantee worsens at order ϵ^−2 near the 0.5 block-error boundary, and the theorem makes no uniform claim as ϵ decreases to zero.Its stated result takes ϵ fixed in (0, 0.5).Source: §4.4 · pp. 13–14
4.5. Uniform-in-Iteration Almost-Exact and Finite-Step Exact Recovery.
- For PPM iterates initialized with δ0≤0.5−ϵ, the section defines γn=Cm/(npπ0²)+log n/n and notes that γn and ξn tend to zero under Assumption 4.6.The supplied passage begins the iteration analysis but does not include its recovery conclusion.Source: §4.5 · p. 14
0. Consequently, for all sufficiently large n,
On a shared high-probability event, PPM contracts error uniformly throughout the positive-overlap basin, giving almost-exact recovery across all iterations and finite-step exact recovery under a stronger condition. Under the same dimension-to-signal condition, the reference-block spectral initializer has vanishing aligned block error and supplies the trajectory initialization.
0. Consequently, for all sufficiently large n,
- On one high-probability event, sup_k≥1 δ_k = o(1), so the fraction of incorrectly recovered blocks vanishes simultaneously over all iterations, though their number may still diverge.The contraction factor is O(m/(npπ0^2)) and the basin remains invariant for sufficiently large n.Source: §0 · p. 14
- Under the stronger condition cnpπ0^2 − log n → ∞, PPM achieves exact recovery after finitely many iterations with probability tending to one.The exact-recovery condition is sufficient, not an information-theoretically sharp threshold.Source: §0 · p. 14
4.6. Spectral Initialization.
- Under np ≥ C0 log n and m = o(npπ0^2), the reference-block spectral initializer has aligned block error O_P(m/(npπ0^2)) and converges to zero in probability.Its error is on the same dimension-to-signal scale as the uniform-contraction condition, so the initializer enters the positive-overlap basin.Source: §4.6 · pp. 15–16
- With the spectral initializer, PPM achieves uniform-in-iteration almost-exact recovery, and each fixed refinement contributes another factor of the dimension-to-signal scale until the additive floor is reached.The end-to-end result combines spectral initialization, uniform contraction, and the finite-step exact-recovery result.Source: §4.6 · p. 17
5. Partial Permutations: Formulation and Scope of the Theory
With a common visible support, partial-permutation synchronization reduces exactly to permutation synchronization on that support, transferring the full recovery theory when iterates preserve it. With varying supports, the paper gives a deterministic local projection margin and a random-support lower bound, but not a general end-to-end recovery theorem.
5. Partial Permutations: Formulation and Scope of the Theory
- A common support of size r reduces the problem exactly to size-r permutation synchronization, transferring one-step, contraction, exact-recovery, and spectral-initialization results when iterates preserve that support.The full theory is not asserted for unrestricted projection over Inj(r,m), which may change the support.Source: §5 · p. 18
- Under the common-support model, the lifted PPM trajectory achieves uniform-in-iteration almost-exact recovery, with finite-step exact recovery also covered under the corresponding stronger condition.The conclusions apply with the support size r replacing m.Source: §5 · pp. 18–19
- For varying supports, each coordinate’s uncorrupted signal depends on how many observed uncorrupted neighbors also contain that latent element.The coordinatewise count replaces the scalar signal count used in the full-permutation analysis.Source: §5 · p. 19
- If the block-score perturbation satisfies ∥E_i∥_F < κ_i/2, the true partial permutation is its unique projection, where κ_i is the minimum co-visibility count over visible elements.The deterministic margin compares the minimum coordinatewise co-visibility to the perturbation size.Source: §5 · p. 19
- Under independent uniformly sampled supports, κ_i ≥ (1 − η)μ_i simultaneously for every i with probability tending to one when log M/μ_min → 0.These margins do not establish end-to-end recovery for general varying supports; further model and perturbation conditions are needed.Source: §5 · pp. 19–20