{"id":"92a949f2-9f5d-4c14-ad0d-1f62f0f746a8","arxiv_id":"2504.19140","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A signal and its non-uniform rotation distribution can in principle be recovered from the first two moments of noisy SO(2)-aligned observations, using frequency marching or a spectral eigenvector method.","lead":"This paper presents two algorithms that attempt to recover a signal from many noisy copies that were each rotated by an unknown angle, under a non-uniform distribution of rotation angles. A correct version would matter for cryo-electron microscopy, where such rotation-invariant alignment is a core computational obstacle.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 Step 6 and Eq. B.3 multiply by S[k,k-1] where the derivation requires division; as printed the recursion recovers ~1/rho[k], so Proposition II.2 is not established.","rationale":"The paper's headline contribution is the claim that Algorithm 1 provably recovers the orbit from the first two moments. That claim is carried by a short recursion in one diagonal of S. The printed recursion is algebraically inconsistent with the S formula derived immediately before it: the derivation requires division, the code line multiplies. Under exact moments the algorithm would output 1/rho[k] for low frequencies, so Proposition II.2 cannot hold as stated. I checked that this is not a matter of a missing assumption such as nonvanishing: even with all Fourier coefficients nonzero and exact moments, a simple B=2 example fails. Because the theorem's proof uses the same wrong formula, the proof is invalid, not merely incomplete. I do not view this as evidence of bad faith; the robust version in Appendix B-B uses the reciprocal, so the intended algorithm is likely recoverable by adding a division. But a reviewer cannot accept a 'provable algorithm' whose displayed central step does not compute what the theorem asserts. The finite-sample optimal-rate claim in the abstract is also unsupported by any theorem in the manuscript; I mention it as a secondary issue but do not base the verdict on it. A single numerical experiment with exact moments on a B=2 instance would settle whether the missing division is a real error or a typographical omission. If the corrected recursion reproduces the proposition, the paper could be revised; as submitted, the main theorem is unproven, so the reader's REJECT stands.","tokens_in":16990,"tokens_out":12411,"duration_ms":116110,"concrete_test":"Take B=2 with rho[0]=1/(2π), rho[1]=1, rho[2]=0.5+0.2i, negative frequencies conjugated, and any nonvanishing signal x. Form exact M1, M2 via Lemma II.1 and execute Algorithm 1 literally: Step 6 outputs rho_est[2]=1/rho[2], not rho[2], so Step 14 does not recover x. Re-run with Step 6 replaced by rho_est[k] ← rho_est[1]/(S[k,k-1] rho_est*[k-1]); then rho_est[2]=rho[2] and the proposition's conclusion holds. This single experiment distinguishes a substantive algebraic error from an OCR or typesetting omission in the displayed recursion.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition II.2 is the paper's central exact-recovery claim, but the recursion that drives it is algebraically inverted. From Lemma II.1 and the definition in Step 2, S[k1,k2] = rho[k1-k2]/(rho[k1] rho*[k2]). Hence S[k,k-1] = rho[1]/(rho[k] rho*[k-1]), and the correct low-frequency march is rho[k] = rho[1]/(S[k,k-1] rho*[k-1]). Algorithm 1 Step 6 and Eq. B.3 instead write multiplication by S[k,k-1]; substituting the expression gives rho_est[k] = rho_est[1]^2/rho[k], not rho[k], whenever the previous steps are exact and |rho[k]| != |rho[1]|. Thus Proposition II.2 is false for the displayed algorithm. The high-frequency extension Step 9 is the correct multiplicative form, so only the low-frequency cell is affected. Appendix B-B's robust version uses division, so the flaw is plausibly a typesetting omission; nevertheless, as printed, the main theorem is unproven and the algorithm does not recover the signal. The abstract's optimal-rate assertion is also unsupported by any finite-sample theorem, but the immediate blocker is the wrong recursion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17376,"tokens_out":7122,"duration_ms":66022,"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":[{"comment":"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.","section":"Algorithm 1 Step 6 / Eq. (B.3) / Algorithm 3 Step 9"},{"comment":"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.","section":"Abstract and Section I"},{"comment":"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).","section":"Theorem II.4, condition 3"}],"minor_comments":[{"comment":"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.","section":"Section II-A"},{"comment":"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":"Eq. (II.6)"},{"comment":"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).","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The frequency-marching recursion error appears to be a typographical slip, since the robust variant in Appendix B-B uses the correct division. The paper's central ideas are salvageable after a careful correction of all affected equations and algorithms. However, the abstract overstates the statistical guarantees, and the uncheckable condition in Theorem II.4(3) should be addressed before publication. I recommend major revision rather than rejection, provided the authors fix the algebraic error and substantially temper or prove the optimal-rate claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing you should know: the central recursion in Algorithm 1 and Eq. (B.3) multiplies by S[k,k-1] where the derivation requires division. From Eq. (B.2), S[k,k-1] = rho[1]/(rho[k] rho*[k-1]). Substituting that into Step 6 gives rho_est[k] = rho_est[1]^2/rho[k], not rho[k]. So as printed, Proposition II.2 is false and the algorithm fails even with exact moments. The same multiplication error appears in the 2D version, Algorithm 3, and in the proof of Proposition III.2. I checked the surrounding text: the robust version in Appendix B-B uses division, Eq. (B.5). That makes me think the displayed recursions lost their division bars in typesetting. But this is not a minor typo in a lemma; it invalidates the paper's main claim as written.\n\nWhat the paper does well: it extends frequency marching and spectral methods from discrete cyclic shifts to the continuous group SO(2) with a non-uniform distribution, for 1D bandlimited signals and 2D Fourier-Bessel images. That is a genuine step beyond [2] and [8]. The moment algebra, especially the block-Toeplitz structure for the 2D case, is nontrivial and cleanly derived. The robust averaging ideas in Appendices B-B and G-A are sensible and would likely help with empirical moments. The Davis-Kahan based error bound in Theorem II.4 is plausible, given its assumptions.\n\nWhere the soft spots are, in proportion: the recursion error is load-bearing and must be fixed. The abstract's claim of optimal estimation rate in high-noise regimes has no finite-sample theorem backing it; the paper only heuristically says n >> sigma^4 suffices. That is a significant overstatement. The spectral algorithm's Step 5, picking kappa by maximizing eigengap, has no proof that this kappa matches the isolated eigenvalue required by Proposition II.3. Theorem II.4 condition 3, requiring the phase-corrected eigenvector overlap to be non-negative, is uncheckable in practice and unproven. None of these are as fatal as the recursion error, but they should all be addressed.\n\nWho this is for: researchers working on provable algorithms for MRA and cryo-EM theory. They would find the moment derivations and the block-Toeplitz analysis useful even after the correction. The paper deserves a serious referee, but the version I read should not be accepted as is. My recommendation: send to peer review, require the division fix, add or soften the optimal-rate claim, and give a real argument for the kappa selection. If the authors can do that, this becomes a solid contribution.","headline":"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.","tokens_in":17827,"tokens_out":2485,"would_cite":false,"duration_ms":24339,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two provable algorithms recover signals from arbitrarily rotated noisy copies at the optimal statistical rate.","keywords":["multi-reference alignment","SO(2)","method of moments","spectral algorithm","frequency marching","sample complexity","Fourier-Bessel","cryo-EM"],"falsifier":"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.","tokens_in":16776,"feed_emoji":"🧭","tokens_out":11309,"duration_ms":98613,"temperature":0.7,"pith_summary":"The paper studies multi-reference alignment over the continuous rotation group $\\mathrm{SO}(2)$: recover a bandlimited signal or image from many noisy copies, each rotated by an unknown angle drawn from a non-uniform distribution. It claims that two computationally efficient algorithms achieve provable exact recovery from the first two population moments, up to an unavoidable global rotation, and that this second-moment strategy reaches the optimal estimation rate in the high-noise regime, with sample complexity proportional to $\\sigma^4$. The frequency marching algorithm reads Fourier coefficients of the rotation distribution off a transformed second-moment matrix one frequency at a time, while the spectral algorithm extracts the signal's Fourier phases from an isolated eigenvector. The practical significance is that these are the first provable, computationally efficient baselines for a continuous rotation-group MRA model, a step toward rigorous cryo-EM reconstruction.","feed_headline":"Provable algorithms recover rotated signals at optimal rate","feed_subtitle":"Two new methods match the statistical limit for aligning noisy rotated signals and images.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the frequency-marching and bispectrum inversion scheme for discrete MRA that the SO(2) frequency marching algorithm extends.","marker":"[2]"},{"why":"Introduces the spectral method and the aperiodic-distribution moment analysis that both SO(2) algorithms generalize.","marker":"[8]"},{"why":"Establishes that second-moment recovery gives the $\\sigma^4$ sample-complexity lower bound, which the optimal-rate claim relies on.","marker":"[9]"},{"why":"Provides the closed-form optimal circulant approximation used to define $v_{\\mathrm{opt}}$ and the mismatch $S_B(\\hat{\\rho})$.","marker":"[12]"},{"why":"Davis-Kahan sine theorem is the perturbation tool that yields the spectral algorithm's error bound in Theorem II.4.","marker":"[13]"}],"fun_headline_variants":["Two provable algorithms hit statistical limit for rotated signals","Optimal-rate recovery for rotated signals via provable algorithms","MRA over rotations: optimal recovery with provable algorithms","Provable algorithms achieve the statistical limit for rotated-signal alignment","Frequency marching and spectral method both hit optimal MRA rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two provable algorithms hit statistical limit for rotated signals","Optimal-rate recovery for rotated signals via provable algorithms","MRA over rotations: optimal recovery with provable algorithms","Provable algorithms achieve the statistical limit for rotated-signal alignment","Frequency marching and spectral method both hit optimal MRA rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000848,"raw_usage":{"total_tokens":3637,"prompt_tokens":843,"completion_tokens":2794,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":2713}},"tokens_in":459,"tokens_out":2794,"duration_ms":16622,"temperature":1.0,"reasoning_tokens":2713,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T06:01:11.844945+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bispectrum in- version with application to multireference alignment,","cited_arxiv_id":null,"evidence_quote":"Supplies the frequency-marching and bispectrum inversion scheme for discrete MRA that the SO(2) frequency marching algorithm extends."},{"cited_title":"Multireference alignment is easier with an aperiodic translation distri- bution,","cited_arxiv_id":null,"evidence_quote":"Introduces the spectral method and the aperiodic-distribution moment analysis that both SO(2) algorithms generalize."},{"cited_title":"The sample complexity of multireference alignment,","cited_arxiv_id":null,"evidence_quote":"Establishes that second-moment recovery gives the $\\sigma^4$ sample-complexity lower bound, which the optimal-rate claim relies on."},{"cited_title":"The rotation of eigenvectors by a perturbation. iii,","cited_arxiv_id":null,"evidence_quote":"Davis-Kahan sine theorem is the perturbation tool that yields the spectral algorithm's error bound in Theorem II.4."}],"review_version":1}