REVIEW 3 major objections 3 minor 16 references
Provable algorithms for multi-reference alignment over $\SO(2)$
T0 review · 3 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Two provable algorithms recover signals from arbitrarily rotated noisy copies at the optimal statistical rate.
desk verdict The frequency-marching recursion is algebraically inverted as printed, so Algorithm 1 does not recover the signal; the paper has a real contribution but needs a major correction before the main theorem can be believed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the second-moment matrix in Fourier coordinates, $M_2 = 2\pi D_{\hat{x}} T_{\rho} D_{\hat{x}}^* + \sigma^2 I$, where $D_{\hat{x}}$ is the diagonal matrix of the signal's Fourier coefficients and $T_{\rho}$ is the Toeplitz matrix with entries $\hat{\rho}[k_1-k_2]$ built from the rotation distribution. Conjugating $M_2$ by $D_{M_1}^{-1}$ removes the signal entirely and leaves the matrix $S[k_1,k_2] = \hat{\rho}[k_1-k_2]/(\hat{\rho}[k_1]\hat{\rho}^*[k_2])$; the frequency marching algorithm evaluates this expression along a path of adjacent frequencies to recover $\hat{\rho}$ one coefficient at a time. The spectral algorithm instead conjugates $M_2$ by $D_{1/\sqrt{P_{\hat{x}}}}$, compares $T_{\rho}$ with its optimal circulant approximation $C_{v_{\mathrm{opt}}}$, and uses an isolated eigenvector of the conjugated matrix, equal to the signal phases up to rotation, combined with the power spectrum to reconstruct $\hat{x}$. The error analysis then rests on the Davis-Kahan sine theorem, with the spectral gap $\delta_\kappa$ and the mismatch $S_B(\hat{\rho})$ controlling the bound.
What would settle it
A decisive test is to search over non-vanishing bandlimited pairs $(\hat{x}, \hat{\rho})$ for two distinct orbits sharing the same first two moments: finding one would refute the exact-recovery propositions, while for the finite-sample rate one would simulate $n = c\sigma^4$ observations and check that the normalized reconstruction error decays as $n$ grows.
Extended reading notes
Core claim
On its own terms, the paper establishes that the map from a signal and a rotation distribution to the first two moments is injective up to the global group action, provided the signal's Fourier coefficients and the distribution's Fourier coefficients are all non-zero. Concretely, with exact first and second moments, Algorithm 1 (frequency marching) recovers both $\hat{x}$ and $\hat{\rho}$ exactly for non-vanishing $\hat{x}, \hat{\rho}$; the analogous 2-D algorithm does the same for bandlimited images. The spectral algorithm recovers the signal exactly when the Toeplitz matrix $T_{\rho}$ is circulant, and otherwise its reconstruction error is bounded by an explicit function of the distance $S_B(\hat{\rho})$ between $T_{\rho}$ and its optimal circulant approximation, under a spectral-gap condition. The paper further claims that in high noise the required number of observations is governed by the second moment, so the sample complexity scales like $\sigma^4$, matching the known lower bound for MRA.
Load-bearing premise
The whole finite-sample story rests on the assumption that empirical moments coincide with population moments; the paper posits $n \gg \sigma^4$ but proves no concentration bound connecting moment error to reconstruction error.
Editorial extensions
If this is right
- Under the exact-moment assumption, the orbit of a bandlimited signal under $\mathrm{SO}(2)$ is identifiable from its first two moments whenever the relevant Fourier coefficients are non-vanishing.
- Because only the second moment is needed, the high-noise sample complexity is $\Theta(\sigma^4)$, the optimal rate for this MRA model; adding higher moments would not change the exponent.
- The spectral algorithm is provably stable in a precise sense: its reconstruction error degrades continuously with $S_B(\hat{\rho})$, the distance of the rotation distribution's Toeplitz matrix from circulant, controlled by the spectral gap.
- The 2-D extension supplies the first provable moment-based estimators for a continuous-group MRA model, which can serve as testable prototypes for the harder cryo-EM estimation problem.
- The averaged variant of frequency marching, which combines redundant moment entries, reduces cascading error in practice and remains exact in the ideal setting.
Reading between the lines
- A natural next step the paper does not take is a concentration theorem: bounding the empirical moment errors in probability and propagating them through the two algorithms would turn the asserted $\sigma^4$ rate into a proven finite-sample guarantee.
- The non-vanishing assumptions on $\hat{x}$ and $\hat{\rho}$ look removable by a limiting or perturbation argument; a cheap test is to run both algorithms on signals with a single zero Fourier coefficient and see whether the moment map remains locally injective.
- The numerical stagnation of the spectral algorithm at high SNR suggests a hybrid estimator: initialize with the spectral method, then switch to frequency marching, using the spectral output to align the marching step; the paper's numerics already hint that such a combination would beat either alone.
- Condition 3 of Theorem II.4 (non-negative phase-corrected eigenvector overlap) is assumed rather than verified; replacing it by a generic-position argument or an algorithmic check would make the spectral guarantee directly testable from data.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies multi-reference alignment (MRA) over the continuous group SO(2) for 1-D bandlimited signals and 2-D Fourier-Bessel images, assuming a non-uniform unknown distribution over rotations. The authors propose two algorithms: a frequency-marching algorithm that recursively recovers the Fourier coefficients of the rotation distribution from the first two moments, and a spectral algorithm that diagonalizes a phase-normalized second-moment matrix. They claim exact recovery from population moments for the frequency-marching method and a Davis-Kahan perturbation bound for the spectral method, and they state in the abstract that both methods achieve the optimal estimation rate in high-noise regimes. Numerical experiments illustrate the behavior of the 2-D variants.
Significance. If the central frequency-marching recursion is corrected, the paper would offer a genuinely new constructive method-of-moments inversion for a non-uniform distribution over a continuous group, complementing existing discrete-shift results. The spectral algorithm, with its explicit bound in terms of the Toeplitz-to-circulant distance SB(\hat{\rho}), is also a valuable contribution. The numerical section is informative and honestly reports the expected trade-offs. However, as submitted, the main exact-recovery proposition is not established by the displayed algorithm, and the advertised statistical optimality is not backed by any finite-sample theorem. These issues are load-bearing for the paper's central claims.
major comments (3)
- [Algorithm 1 Step 6 / Eq. (B.3) / Algorithm 3 Step 9] The frequency-marching recursion is algebraically inverted. From Eq. (B.2), S[k1,k2] = \hat{\rho}[k1-k2]/(\hat{\rho}[k1]\hat{\rho}^*[k2]), so S[k,k-1] = \hat{\rho}[1]/(\hat{\rho}[k]\hat{\rho}^*[k-1]). The correct low-frequency update is therefore \hat{\rho}[k] = \hat{\rho}[1] / (S[k,k-1] \hat{\rho}^*[k-1]), i.e., division. Algorithm 1 Step 6 and Eq. (B.3) instead set \hat{\rho}_{est}[k] = \hat{\rho}_{est}[1] S[k,k-1] \hat{\rho}_{est}^*[k-1]. Substituting the exact expression gives \hat{\rho}_{est}[k] = |\hat{\rho}[1]| \hat{\rho}[1]/\hat{\rho}[k], which is not \hat{\rho}[k] in general. Thus Proposition II.2 is false for the displayed algorithm, and the same defect appears in Algorithm 3 Step 9, undermining Proposition III.2 for the 2-D case. The robust version in Eq. (B.5) correctly uses division, so this is plausibly a typographical slip, but the manuscript must be corrected consistently in Algorithm 1, Eq. (B.3), Algorithm 3, and the proofs that rely on them.
- [Abstract and Section I] The abstract claims that both algorithms achieve the optimal estimation rate in high-noise regimes, but the paper contains no finite-sample theorem or sample-complexity analysis. Section I asserts that the empirical moments approximate the population moments when n >> \sigma^4, but no concentration or stability result connects this approximation to the reconstruction error of either algorithm. Theorem II.4 is a deterministic perturbation bound in terms of SB(\hat{\rho}) and eigenvalue gaps, not a statistical bound; the numerical error rates in Section IV are empirical only. The optimal-rate claim should be either proved with explicit finite-sample bounds or removed from the abstract and introduction.
- [Theorem II.4, condition 3] Condition 3 of Theorem II.4 assumes that the phase-corrected eigenvector overlap \tilde{x}_{est}^*[\Phi_{2\pi l/(2B+1)} \odot \tilde{x}] is non-negative. This is an assumption on the algorithm's output rather than on the model, and the paper gives no mechanism to verify or guarantee it from the data. The proof of Theorem II.4 uses this condition in Eq. (D.9) to drop the absolute value of the inner product; without it, the stated bound may fail. Please either prove that Step 8 of Algorithm 2 always achieves this sign condition via an appropriate phase choice, or generalize the bound to hold without the non-negativity assumption (e.g., by bounding the absolute value).
minor comments (3)
- [Section II-A] The paragraph after Proposition II.2 states that the algorithm uses only a single diagonal of M2, but the frequency-marching steps actually use one superdiagonal of S for low frequencies and a specific off-diagonal column for high frequencies; the wording should be adjusted for precision.
- [Eq. (II.6)] The closed-form solution v_opt for the circulant approximation problem is cited to [12], but the connection between the minimization in Eq. (II.5) and the formula in Eq. (II.6) is not derived. A short derivation or a more specific reference would improve readability.
- [Section IV] In the description of Figure 1, the text says 'the error of the spectral algorithm stagnates because SB(\hat{\rho}) \neq 0' but the figure caption and the surrounding discussion could more clearly distinguish the SNR behavior in panel (a) from the sample-size behavior in panel (b).
Circularity Check
No circularity found: both algorithms invert closed-form moment identities with self-contained proofs.
full rationale
The derivation chain is self-contained and non-circular. Lemma II.1 derives explicit moment formulas M1 = 2π \hat{x}⊙\hat{ρ} and M2 = 2π D_\hat{x} T_ρ D_\hat{x}^* + σ²I directly from the model. Algorithm 1's normalized matrix S is defined from these moments as S = 2π D_{M1}^{-1} M2 D_{M1}^{-*} = D_{ρ}^{-1} T_ρ D_{ρ}^{-*}, so each recovered coefficient \hat{ρ}[k] is obtained by solving the algebraic equation S[k,k′] = \hat{ρ}[k−k′]/(\hat{ρ}[k]\hat{ρ}^*[k′]); the target is not inserted into the input. The spectral Algorithm 2 likewise uses a unitary diagonalization of M2 after power-spectrum normalization; its proof in Appendix C shows that the isolated eigenvector equals the phase vector up to a rotation, with no fitted constants. Theorem II.4's stability bound is a Davis–Kahan argument whose assumptions are stated independently of the conclusion. Self-citations ([2], [8], [9]) are used for motivation, comparisons, and prior sample-complexity results, not as the proof of the current recovery claims. Any concerns about the correctness of the printed low-frequency recursion in Algorithm 1 Step 6 and equation (B.3), or about the absence of a finite-sample concentration theorem for the optimal-rate claim, are non-circularity issues and do not affect this verdict.
Assumptions & free parameters
assumptions (7)
- domain assumption Observations are exactly y_i = g_i * x + epsilon_i with i.i.d. Gaussian noise in the chosen coefficient basis (Section I, Eq. I.1).
- ad hoc to paper All Fourier coefficients of the signal and of the rotation distribution are non-vanishing (Propositions II.2, II.3, III.2, Theorem II.4).
- domain assumption Population moments are available exactly, M1_est = M1 and M2_est = M2, for the recovery guarantees (Propositions II.2, II.3, III.2).
- domain assumption The rotation distribution rho is real and its Fourier coefficients are 2B-bandlimited (Section II, after Eq. II.1).
- ad hoc to paper For the 2D spectral analysis, each angular frequency has the same radial bandwidth Q_k = Q (Appendix H, Eq. H.1).
- standard math Davis-Kahan sin(theta) theorem applies to the perturbed eigenvector problem (Appendix D, Eq. D.10).
- ad hoc to paper The overlap condition in Theorem II.4 condition 3 is non-negative, with no proof that the algorithm output satisfies it.
Cite this review
Pith. "Pith review of Provable algorithms for multi-reference alignment over $\SO(2)$." pith.science (2026). https://pith.science/paper/BDKE4X2R
@misc{pith2026250419140,
author = {Pith},
title = {Pith review of: Provable algorithms for multi-reference alignment over $\SO(2)$},
year = {2026},
howpublished = {\url{https://pith.science/paper/BDKE4X2R}},
note = {Machine review of arXiv:2504.19140}
}
abstract
The multi-reference alignment (MRA) problem involves reconstructing a signal from multiple noisy observations, each transformed by a random group element. In this paper, we focus on the group \(\mathrm{SO}(2)\) of in-plane rotations and propose two computationally efficient algorithms with theoretical guarantees for accurate signal recovery under a non-uniform distribution over the group. The first algorithm exploits the spectral properties of the second moment of the data, while the second utilizes the frequency marching principle. Both algorithms achieve the optimal estimation rate in high-noise regimes, marking a significant advancement in the development of computationally efficient and statistically optimal methods for estimation problems over groups.
Figures
Reference graph
Works this paper leans on
-
[1]
Multireference alignment using semidefinite programming,
A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu, “Multireference alignment using semidefinite programming,” in Proceedings of the 5th conference on Innovations in theoretical computer science , 2014, pp. 459–470
work page 2014
-
[2]
Bispectrum in- version with application to multireference alignment,
T. Bendory, N. Boumal, C. Ma, Z. Zhao, and A. Singer, “Bispectrum in- version with application to multireference alignment,” IEEE Transactions on signal processing , vol. 66, no. 4, pp. 1037–1050, 2017. 11
work page 2017
-
[8]
Multireference alignment is easier with an aperiodic translation distri- bution,
E. Abbe, T. Bendory, W. Leeb, J. M. Pereira, N. Sharon, and A. Singer, “Multireference alignment is easier with an aperiodic translation distri- bution,” IEEE Transactions on Information Theory , vol. 65, no. 6, pp. 3565–3584, 2018
work page 2018
-
[3]
Estimation under group actions: recovering orbits from invariants,
A. S. Bandeira, B. Blum-Smith, J. Kileel, J. Niles-Weed, A. Perry, and A. S. Wein, “Estimation under group actions: recovering orbits from invariants,” Applied and Computational Harmonic Analysis , vol. 66, pp. 236–319, 2023
work page 2023
-
[4]
T. Bendory, N. Dym, D. Edidin, and A. Suresh, “A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM,” arXiv preprint arXiv:2405.04354 , 2024
arXiv 2024
-
[5]
RELION: implementation of a Bayesian approach to cryo-EM structure determination,
S. H. Scheres, “RELION: implementation of a Bayesian approach to cryo-EM structure determination,” Journal of structural biology, vol. 180, no. 3, pp. 519–530, 2012
work page 2012
-
[6]
Single-particle cryo-EM—how did it get here and where will it go,
Y . Cheng, “Single-particle cryo-EM—how did it get here and where will it go,” Science, vol. 361, no. 6405, pp. 876–880, 2018
work page 2018
-
[7]
T. Bendory, A. Bartesaghi, and A. Singer, “Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and oppor- tunities,” IEEE signal processing magazine , vol. 37, no. 2, pp. 58–76, 2020
work page 2020
Show all 16 references
-
[9]
The sample complexity of multireference alignment,
A. Perry, J. Weed, A. S. Bandeira, P. Rigollet, and A. Singer, “The sample complexity of multireference alignment,” SIAM Journal on Mathematics of Data Science , vol. 1, no. 3, pp. 497–517, 2019
2019
-
[10]
Dihedral multi-reference alignment,
T. Bendory, D. Edidin, W. Leeb, and N. Sharon, “Dihedral multi-reference alignment,” IEEE Transactions on Information Theory , vol. 68, no. 5, pp. 3489–3499, 2022
2022
-
[11]
Method of moments for 3d single particle ab initio modeling with non-uniform distribution of viewing angles,
N. Sharon, J. Kileel, Y . Khoo, B. Landa, and A. Singer, “Method of moments for 3d single particle ab initio modeling with non-uniform distribution of viewing angles,” Inverse Problems, vol. 36, no. 4, p. 044003, 2020
2020
-
[12]
An optimal circulant preconditioner for toeplitz systems,
T. F. Chan, “An optimal circulant preconditioner for toeplitz systems,” SIAM Journal on Scientific and Statistical Computing , vol. 9, no. 4, pp. 766–771, 1988. [Online]. Available: https://doi.org/10.1137/0909051
1988 doi
-
[13]
The rotation of eigenvectors by a perturbation. iii,
C. Davis and W. M. Kahan, “The rotation of eigenvectors by a perturbation. iii,” SIAM Journal on Numerical Analysis , vol. 7, no. 1, pp. 1–46, 1970
1970
-
[14]
Fast steerable principal component analysis,
Z. Zhao, Y . Shkolnisky, and A. Singer, “Fast steerable principal component analysis,” IEEE transactions on computational imaging, vol. 2, no. 1, pp. 1–12, 2016
2016
-
[15]
Avoiding the pitfalls of single particle cryo-electron microscopy: Einstein from noise,
R. Henderson, “Avoiding the pitfalls of single particle cryo-electron microscopy: Einstein from noise,” Proceedings of the National Academy of Sciences, vol. 110, no. 45, pp. 18 037–18 041, 2013
2013
-
[16]
Einstein from noise: Statistical analysis,
A. Balanov, W. Huleihel, and T. Bendory, “Einstein from noise: Statistical analysis,” bioRxiv, pp. 2024–07, 2024
2024
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.