Pith. sign in

REVIEW 4 minor 69 references

Geometric planted matchings in high dimensions: The power of multiple views

T0 review · 0 major / 4 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Below b=2 two-view geometric matching is information-theoretically empty, but a third view recovers all correspondences efficiently.

desk verdict Solid all-or-nothing resolution of the two-view geometric matching threshold plus a clean multi-view algorithmic gain already nontrivial at K=3. read the letter →

arxiv 2607.09026 v1 pith:NIBK45JS submitted 2026-07-10 math.ST cs.DSmath.PRstat.TH

Timothy L. H. Wee , Kaylee Y. Yang , Zhou Fan , Cheng Mao This is my paper · ORCID
classification math.STcs.DSmath.PRstat.TH MSC 62H1260C0568Q87
keywords plantedmatchinggeometricall-or-nothingmulti-viewrecoveryfreeenergyhigh-dimensionalstatisticsposteriorconcentration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

When you observe a high-dimensional point cloud and one noisy, randomly permuted copy of it, earlier work already showed that almost-exact recovery of the hidden matching is possible precisely when a noise parameter b exceeds 2. This paper proves the complementary statement: for every fixed b less than 2 the posterior puts exponentially small mass on any permutation that agrees with the truth on a positive fraction of points. Consequently no estimator can recover a non-vanishing fraction of the matching, and even Euclidean estimation of the matched cloud is asymptotically no better than random guessing. The same paper then introduces a multi-view model in which K independently permuted noisy copies of the same latent cloud are observed. A simple polynomial-time row-wise scoring algorithm recovers every relative matching up to o(n) errors as soon as b exceeds K/(K-1). Already for K=3 the new threshold drops below 2, so a third view can break the two-view impossibility barrier.

What carries the argument

Conditional second-moment analysis of the free energy (Franz-Parisi potential) of the posterior partition function, together with a multi-view score that counts consistent pairwise inner products across candidate tuples; the score gap is minimized by one-outlier patterns, which forces the threshold K/(K-1).

What would settle it

Simulate the two-view model at fixed b=1.9 with n=10^4 and d=100 log n; if any estimator recovers more than 5 percent of the matching or reduces Euclidean risk of the matched cloud by more than 5 percent relative to the dummy estimator, the nothing-phase claim fails.

Watch

Extended reading notes

Core claim

In the high-dimensional Gaussian planted matching model the threshold b=2 is all-or-nothing: for every fixed b<2 the posterior mass on permutations with overlap at least δn decays as exp(-C n log n), so both combinatorial and geometric estimation fail completely. With K independent views the same scaling admits efficient almost-exact recovery of all relative matchings whenever b>K/(K-1).

Load-bearing premise

Everything rests on exact Gaussian rows for both the latent cloud and every noise matrix, together with the high-dimensional regime d much larger than log n; non-Gaussian or low-dimensional analogues are left open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies geometric planted matching of n Gaussian points in R^d under the high-dimensional scaling d=ω(log n) and noise variance σ^{2}=d/(b log n). For the classical two-view model it proves that the known almost-exact-recovery threshold b=2 is all-or-nothing: for every fixed b<2 the posterior mass on permutations with overlap ≥δn is at most exp(-C_{b,δ} n log n), which implies that both the permutation MMSE and the Euclidean Y-MMSE of the matched cloud are asymptotically no better than random guessing (Theorem 2.1(i), Corollary 2.2). For the K-view extension the authors give a simple polynomial-time row-wise scoring algorithm that recovers all relative matchings up to o(n) errors whenever b>K/(K-1) (Theorem 2.5). Parallel all-or-nothing statements are obtained for the non-geometric Gaussian weighted matching model.

Significance. The work closes a natural gap left by earlier almost-exact-recovery analyses (KNW22, DCK23, WWXY22) by ruling out any nontrivial “something” phase below b=2, both combinatorially and geometrically. The multi-view threshold K/(K-1) is a clean, quantitative demonstration that additional independent views can break the two-view impossibility barrier; already for K=3 the interval 3/2<b<2 becomes efficiently recoverable. The technical core—a carefully truncated second-moment method for the assignment partition function together with an explicit spectral analysis of cycle-type quadratic forms—is self-contained and of independent interest for other high-dimensional matching problems. The arguments are written out in full in the appendices and do not rely on fitted parameters or circular reductions.

minor comments (4)
  1. The multi-view model is introduced with noise parameter τ while the two-view model uses σ; the asymptotic equivalence σ^{2}∼ au^{4} is stated only in Remark B.1. A short forward pointer in §2.2 would help the reader compare the two thresholds immediately.
  2. In the proof overview of Theorem 2.1 the high-probability event E is defined with an auxiliary scale k_{0}=c_{0} n; the subsequent dependence of the second-moment bound on the free parameters ε and c_{0} is correct but slightly opaque. A one-sentence remark that any sufficiently small ε,c_{0} work for b<2 would improve readability.
  3. The Gaussian weighted matching results (Theorem 2.7, Corollary 2.9) are stated as “analogous” and their proofs are omitted. A brief pointer to the precise places where the geometric argument simplifies (replacement of XZ⊤/√d by an i.i.d. Gaussian matrix) would make the claim fully self-contained.
  4. Typographical: “Franz–Parisi potential” is introduced without a citation; a standard reference (e.g., Franz–Parisi 1995 or a modern survey) would be appropriate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: free-energy and multi-view thresholds are derived from first-principles Gaussian calculations under the stated model.

full rationale

The paper's central claims (Theorem 2.1(i), Corollary 2.2, Theorem 2.5) are obtained by direct analysis of the Gaussian planted matching model. The restricted free-energy upper bound (Proposition A.1) follows from chi-squared maxima and a spectral analysis of cycle-type moment-generating functions that identifies the maximizing derangement as a product of 2-cycles; the unrestricted free-energy lower bound (Proposition 2.3 / Theorem A.3) is proved by a truncated second-moment method with an explicit high-probability event E that caps sub-permutation scores, followed by Paley–Zygmund. The multi-view positive result is a transparent union bound whose worst-case multiplicity pattern yields the threshold K/(K-1). Self-citations (KNW22, DCK23, WWXY22, DWXY23) supply only background almost-exact recovery statements for the complementary regime b>2 or for the non-geometric companion model; they are not used to force the nothing-phase or multi-view thresholds by algebraic identity or uniqueness. No fitted parameters are renamed as predictions, and no uniqueness theorem of the present authors is imported as an external fact. The derivation is therefore self-contained against the paper's own Gaussian assumptions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper works entirely inside the classical Gaussian planted-matching model. No numerical parameters are fitted; b and K are free model parameters whose critical values are derived. All probabilistic tools (Gaussian concentration, Hanson–Wright, chi-squared tails, Paley–Zygmund) are standard. The only modeling axioms are the i.i.d. Gaussian generative assumptions and the high-dimensional scaling, both stated explicitly.

assumptions (3)
  • domain assumption Latent point cloud X and all noise matrices have i.i.d. standard Gaussian entries; permutations are uniform and independent.
    Stated in equations (3) and (9); every moment-generating-function calculation and concentration bound relies on it.
  • domain assumption Dimension satisfies d=ω(log n) and noise scales as σ^{2}=d/(b log n) (or au^{4}=d/(b log n) for multi-view).
    Critical high-dimensional regime fixed throughout Sections 2–3 and the appendices; used to obtain the precise free-energy limits and the union-bound exponents.
  • standard math Standard Gaussian concentration, Hanson–Wright inequality, and chi-squared tail bounds hold.
    Invoked repeatedly for free-energy concentration (Lemma A.4), high-probability event E, and moderate-deviation tails of Ti.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Geometric planted matchings in high dimensions: The power of multiple views." pith.science (2026). https://pith.science/paper/NIBK45JS

@misc{pith2026260709026,
  author       = {Pith},
  title        = {Pith review of: Geometric planted matchings in high dimensions: The power of multiple views},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NIBK45JS}},
  note         = {Machine review of arXiv:2607.09026}
}
abstract

We study the problem of recovering the correspondence between a collection of $n$ points in $\mathbb{R}^d$ and a noisy, permuted version of those points. In the high-dimensional regime $d=\omega(\log n)$, under a Gaussian model with noise variance $\sigma^2=d/(b\log n)$, prior work identifies $b=2$ as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed $b<2$, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where $K$ noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to $o(n)$ errors whenever $b>K/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2 < b < 2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 2 canonical work pages

  1. [1]

    Combinatorics, Probability and Computing , volume=

    The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph , author=. Combinatorics, Probability and Computing , volume=. 1994 , publisher=

    1994

  2. [2]

    2000 , publisher=

    Asymptotic statistics , author=. 2000 , publisher=

    2000

  3. [3]

    1994 , publisher=

    Orthogonal decompositions and functional limit theorems for random graph statistics , author=. 1994 , publisher=

    1994

  4. [4]

    Random matrix theory, interacting particle systems, and integrable systems , volume=

    Three lectures on free probability , author=. Random matrix theory, interacting particle systems, and integrable systems , volume=

  5. [5]

    Les Houches , year=

    A short course on cluster expansions , author=. Les Houches , year=

  6. [6]

    Enumerative combinatorics. Vol. 2, volume 62 of , author=. Cambridge studies in advanced mathematics , pages=

  7. [7]

    2012 , publisher=

    Normal approximations with Malliavin calculus: from Stein's method to universality , author=. 2012 , publisher=

    2012

  8. [8]

    2016 , url=

    Probability in High Dimension , author=. 2016 , url=

    2016

Show all 69 references
  1. [9]

    2017 , publisher=

    Statistical mechanics of lattice systems: a concrete mathematical introduction , author=. 2017 , publisher=

    2017

  2. [10]

    Moscow Mathematical Journal , volume=

    Cluster expansions and correlation functions , author=. Moscow Mathematical Journal , volume=. 2004 , publisher=

    2004

  3. [11]

    2016 , publisher=

    Combinatorics and complexity of partition functions , author=. 2016 , publisher=

    2016

  4. [12]

    Statistical mechanics: foundations and applications , pages=

    Convergence of fugacity expansions for classical systems , author=. Statistical mechanics: foundations and applications , pages=

  5. [13]

    Communications in Mathematical Physics , volume=

    Cluster expansion for abstract polymer models , author=. Communications in Mathematical Physics , volume=. 1986 , publisher=

    1986

  6. [14]

    Journal of Mathematical Physics , volume=

    A mean-field monomer-dimer model with attractive interaction: Exact solution and rigorous results , author=. Journal of Mathematical Physics , volume=. 2014 , publisher=

    2014

  7. [15]

    Banerjee, Debapratim and Ma, Zongming , TITLE =. Ann. Statist. , FJOURNAL =. 2022 , NUMBER =. doi:10.1214/21-aos2150 , URL =

    2022 doi

  8. [16]

    El Alaoui, Ahmed and Krzakala, Florent and Jordan, Michael , TITLE =. Ann. Statist. , FJOURNAL =. 2020 , NUMBER =. doi:10.1214/19-AOS1826 , URL =

    2020 doi

  9. [17]

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron , author=. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2021

  10. [18]

    On the probability of nonexistence in binomial subsets , author=

  11. [19]

    All-Something-Nothing

    " All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery , author=. arXiv preprint arXiv:2503.08984 , year=

    arXiv

  12. [20]

    Physical Review E , volume=

    Planted matching problems on random hypergraphs , author=. Physical Review E , volume=. 2022 , publisher=

    2022

  13. [21]

    Combinatorics, Probability and Computing , volume=

    Triangle factors in random graphs , author=. Combinatorics, Probability and Computing , volume=. 1997 , publisher=

    1997

  14. [22]

    Random Structures & Algorithms , volume=

    Factors in random graphs , author=. Random Structures & Algorithms , volume=. 2008 , publisher=

    2008

  15. [23]

    Acta Math

    On the existence of a factor of degree one of a connected random graph , author=. Acta Math. Acad. Sci. Hungar , volume=

  16. [24]

    Combinatorica , volume=

    Embedding nearly-spanning bounded degree trees , author=. Combinatorica , volume=. 2007 , publisher=

    2007

  17. [25]

    General properties of polymer systems , author=

  18. [26]

    Proceedings of the Royal Society of London

    Some properties of adsorbed films of oxygen on tungsten , author=. Proceedings of the Royal Society of London. Series A-Mathematical and Physical Sciences , volume=. 1935 , publisher=

    1935

  19. [27]

    Communications in mathematical Physics , volume=

    Theory of monomer-dimer systems , author=. Communications in mathematical Physics , volume=. 1972 , publisher=

    1972

  20. [28]

    The Annals of Statistics , volume=

    Asymptotic power of sphericity tests for high-dimensional data , author=. The Annals of Statistics , volume=. 2013 , publisher=

    2013

  21. [29]

    The Annals of Applied Probability , volume=

    Sharp thresholds in inference of planted subgraphs , author=. The Annals of Applied Probability , volume=. 2025 , publisher=

    2025

  22. [30]

    The Annals of Applied Probability , volume=

    The planted matching problem: Phase transitions and exact results , author=. The Annals of Applied Probability , volume=. 2021 , publisher=

    2021

  23. [31]

    Probability Theory and Related Fields , volume=

    The planted matching problem: Sharp threshold and infinite-order phase transition , author=. Probability Theory and Related Fields , volume=. 2023 , publisher=

    2023

  24. [32]

    arXiv preprint arXiv:2512.14567 , year=

    Cluster expansion of the log-likelihood ratio: Optimal detection of planted matchings , author=. arXiv preprint arXiv:2512.14567 , year=

  25. [33]

    arXiv preprint arXiv:2602.07669 , year=

    The statistical threshold for planted matchings and spanning trees , author=. arXiv preprint arXiv:2602.07669 , year=

  26. [34]

    arXiv preprint arXiv:2512.00610 , year=

    Statistical-computational gap in multiple Gaussian graph alignment , author=. arXiv preprint arXiv:2512.00610 , year=

  27. [35]

    arXiv preprint arXiv:2307.02459 , year=

    Gaussian database alignment and gaussian planted matching , author=. arXiv preprint arXiv:2307.02459 , year=

    arXiv

  28. [36]

    Proceedings of the National Academy of Sciences , volume=

    Inference in particle tracking experiments by passing messages between images , author=. Proceedings of the National Academy of Sciences , volume=. 2010 , publisher=

    2010

  29. [37]

    arXiv preprint arXiv:2403.17469 , year=

    Geometric planted matchings beyond the Gaussian model , author=. arXiv preprint arXiv:2403.17469 , year=

    arXiv

  30. [38]

    arXiv preprint arXiv:2603.08542 , year=

    Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit , author=. arXiv preprint arXiv:2603.08542 , year=

  31. [39]

    Nature Biotechnology , volume=

    Batch effects in single-cell RNA-sequencing data are corrected by matching mutual nearest neighbors , author=. Nature Biotechnology , volume=. 2018 , publisher=

    2018

  32. [40]

    Journal of Computational Biology , volume=

    SCOT: single-cell multi-omics alignment with optimal transport , author=. Journal of Computational Biology , volume=. 2022 , publisher=

    2022

  33. [41]

    International Journal of Computer Vision , volume=

    Image matching from handcrafted to deep features: A survey , author=. International Journal of Computer Vision , volume=. 2021 , publisher=

    2021

  34. [42]

    International Journal of Epidemiology , volume=

    Probabilistic record linkage , author=. International Journal of Epidemiology , volume=. 2016 , publisher=

    2016

  35. [43]

    2012 , publisher=

    Data Matching: Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection , author=. 2012 , publisher=

    2012

  36. [44]

    Foundations and Trends in Robotics , volume=

    A review of point cloud registration algorithms for mobile robotics , author=. Foundations and Trends in Robotics , volume=. 2015 , publisher=

    2015

  37. [45]

    IEEE Signal Processing Magazine , volume=

    Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities , author=. IEEE Signal Processing Magazine , volume=. 2020 , publisher=

    2020

  38. [46]

    2009 Ninth IEEE International Conference on Data Mining , pages=

    Algorithms for large, sparse network alignment problems , author=. 2009 Ninth IEEE International Conference on Data Mining , pages=. 2009 , organization=

    2009

  39. [47]

    Physical Review E , volume=

    Recovery thresholds in the sparse planted matching problem , author=. Physical Review E , volume=. 2020 , publisher=

    2020

  40. [48]

    Journal of Combinatorial Theory, Series B , volume=

    An introduction to matching polynomials , author=. Journal of Combinatorial Theory, Series B , volume=. 1979 , publisher=

    1979

  41. [49]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Strong recovery of geometric planted matchings , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  42. [50]

    The annals of mathematical statistics , volume=

    The large-sample distribution of the likelihood ratio for testing composite hypotheses , author=. The annals of mathematical statistics , volume=. 1938 , publisher=

    1938

  43. [51]

    Probability theory and related fields , volume=

    The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square , author=. Probability theory and related fields , volume=. 2019 , publisher=

    2019

  44. [52]

    The Annals of Statistics , number =

    Zhidong Bai and Dandan Jiang and Jian-Feng Yao and Shurong Zheng , title =. The Annals of Statistics , number =. 2009 , doi =

    2009

  45. [53]

    The Annals of Statistics , number =

    Tiefeng Jiang and Fan Yang , title =. The Annals of Statistics , number =. 2013 , doi =

    2013

  46. [54]

    Journal of Machine Learning Research , volume=

    Contextual stochastic block model: Sharp thresholds and contiguity , author=. Journal of Machine Learning Research , volume=

  47. [55]

    Johnstone and Alexei Onatski , title =

    Iain M. Johnstone and Alexei Onatski , title =. The Annals of Statistics , number =. 2020 , doi =

    2020

  48. [56]

    Probability Theory and Related Fields , volume=

    Reconstruction and estimation in the planted partition model , author=. Probability Theory and Related Fields , volume=. 2015 , publisher=

    2015

  49. [57]

    Combinatorics, Probability and Computing , volume=

    Random regular graphs: asymptotic distributions and contiguity , author=. Combinatorics, Probability and Computing , volume=. 1995 , publisher=

    1995

  50. [58]

    Communications in mathematical physics , volume=

    Broken replica symmetry bounds in the mean field spin glass model , author=. Communications in mathematical physics , volume=. 2003 , publisher=

    2003

  51. [59]

    2010 , publisher=

    Mean field models for spin glasses: Volume I: Basic examples , author=. 2010 , publisher=

    2010

  52. [60]

    The Annals of Applied Probability , number =

    Wei-Kuo Chen and Madeline Handschy and Gilad Lerman , title =. The Annals of Applied Probability , number =. 2021 , doi =

    2021

  53. [61]

    Conference on Learning Theory , pages=

    Consistent recovery threshold of hidden nearest neighbor graphs , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  54. [62]

    2014 , publisher=

    Superconcentration and related topics , author=. 2014 , publisher=

    2014

  55. [63]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    2018

  56. [64]

    The Annals of Statistics , volume=

    Adaptive estimation of a quadratic functional by model selection , author=. The Annals of Statistics , volume=. 2000 , doi=

    2000

  57. [65]

    arXiv preprint arXiv:2204.13858 , year=

    One-way matching of datasets with low rank signals , author=. arXiv preprint arXiv:2204.13858 , year=

    arXiv

  58. [66]

    Advances in Physics , volume=

    Statistical physics of inference: Thresholds and algorithms , author=. Advances in Physics , volume=. 2016 , publisher=

    2016

  59. [67]

    IEEE Transactions on Information Theory , volume=

    Mutual information and minimum mean-square error in Gaussian channels , author=. IEEE Transactions on Information Theory , volume=. 2005 , publisher=

    2005

  60. [68]

    Proceedings of Thirty Fifth Conference on Learning Theory , series=

    Random graph matching in geometric models: the case of complete graphs , author=. Proceedings of Thirty Fifth Conference on Learning Theory , series=. 2022 , publisher=

    2022

  61. [69]

    arXiv preprint arXiv:2606.14335 , year=

    Recovery thresholds for hidden weighted sparse graphs , author=. arXiv preprint arXiv:2606.14335 , year=

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.