{"id":"2b30bc3a-dcc9-44b1-bc90-80c9fadddece","arxiv_id":"2501.11980","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For circular translations, MTD in high noise needs Θ(σ^6) samples; SO(2) rotations get a lower bound and translation-free gets an upper bound.","lead":"This paper derives sample complexity bounds for multi-target detection (MTD), the problem of recovering a signal repeated at unknown locations in a long noisy measurement. For 1D circular translations the sample complexity scales as the sixth power of the noise level, with partial bounds for rotations and translation-free cases, relevant to cryo-EM.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition V.2's proof applies an upper-bound theorem to establish a lower bound; the MRA σ^6 lower bound is asserted without proof, so the 2D MTD lower bound is currently unsupported.","rationale":"The paper's main 1D results are likely correct: the upper bound follows from the autocorrelation convergence framework of Proposition III.4 together with known uniqueness of the third-order autocorrelation for signals with non-vanishing DFT, and the lower bound follows from a valid reduction to MRA whose σ^6 sample complexity is established in [1]. The autocorrelation convergence proof in Proposition III.3 is careful and correctly handles the well-separated structure via i.i.d. blocks. The general upper-bound theorem (Proposition III.4) is plausible, though its proof invokes Newey-McFadden without fully specifying the likelihood or uniform convergence; this can likely be repaired by a direct continuity argument on the compact parameter space. The weakest point is Proposition V.2's lower bound for 2D rotations: the proof text explicitly applies Proposition III.4, an upper-bound theorem, to prove a lower bound, and it does not supply the missing minimax or Fisher-information step connecting the minimal identifying moment order to the sample-complexity exponent. The reader's weakest_assumption identified the same general gap, but not the specific category error in the proof's final sentence. This does not overturn the paper's central claims, because the 2D upper bound is already stated as a conjecture and the 1D Θ(σ^6) result does not depend on Proposition V.2; however, the 2D lower-bound claim needs a corrected proof or citation before full acceptance, so the conditional verdict is appropriate.","tokens_in":14516,"tokens_out":18204,"duration_ms":184010,"concrete_test":"Check whether reference [4] (Bandeira, Blum-Smith, Kileel, Niles-Weed, Perry, Wein, 'Estimation under group actions') contains a theorem stating that for MRA with generic signals under a compact group action, the sample complexity scales as σ^{2p}, where p is the smallest moment order that separates orbits. If such a theorem applies to uniform SO(2) rotations with non-vanishing Fourier-Bessel coefficients, replace the last paragraph of Appendix E with a direct invocation of that theorem; if no such theorem exists, Proposition V.2 should be downgraded to a conjecture.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix E's proof of Proposition V.2 contains a category error: after Theorem A.9 shows that the combined power spectrum and bispectrum determine an image up to rotation, the text says 'applying Proposition III.4 and Theorem A.9 proves the lower bound.' Proposition III.4 is an upper-bound statement (sample complexity ≤ ω(σ^{2\\bar d}) when autocorrelations identify the orbit); it cannot imply N*_{MTD_SO(2)} ≥ ω(σ^6). The lower bound must come from a minimax or Fisher-information argument for the associated MRA model, and the paper merely asserts that the MRA sample complexity is ω(σ^6) 'as the minimal moment required to determine uniquely the signal x is the third moment.' That inference is nontrivial: the sample-complexity exponent does not follow from the mere order of the identifying moment without a quantitative argument (e.g., [4] proves such results under specific genericity conditions). Because the upper bound for this model is explicitly conjectural, Proposition V.2 is the only claimed 2D result, and without a valid lower-bound proof the 2D claim is unsupported as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the sample complexity of multi-target detection (MTD), where a signal x appears N times at unknown locations in a long noisy observation, each occurrence acted on by a random group element. The authors propose a general framework: an upper bound via autocorrelation analysis (if the d-th order ensemble autocorrelations uniquely determine the orbit, then N = ω(σ^{2d}) observations suffice), and a lower bound via a reduction to multi-reference alignment (MRA). They apply the framework to three models: 1D circular translations (matching upper/lower bounds of ω(σ^6)), 2D images with uniform SO(2) rotations (a claimed lower bound of ω(σ^6), with the upper bound left as a conjecture), and 1D signals without group action (an upper bound of ω(σ^6)). The proofs are in the appendix, including an almost-sure convergence result for empirical autocorrelations in the well-separated case and a measurable-mapping argument for the MRA reduction.","tokens_in":14729,"tokens_out":13340,"duration_ms":127927,"significance":"If correct, the 1D result would provide a clean Θ(σ^6) characterization and the reduction to MRA is a useful conceptual contribution. The autocorrelation convergence theorem under the well-separated assumption is a genuine extension of previous work, and the paper is careful to identify which upper bounds are conjectural. However, the only 2D result (Proposition V.2) rests on an invalid proof: moment-order identifiability does not imply a sample-complexity lower bound, and an upper-bound theorem is invoked to prove a lower bound. Consequently the 2D claim is currently unsupported. The paper is perhaps best viewed as a working note consolidating the 1D bounds and identifying open problems.","major_comments":[{"comment":"The proof of the lower bound N*_{MTD_SO(2)} ≥ ω(σ^6) is invalid. The statement 'as the minimal moment required to determine uniquely the signal x is the third moment' is an unsupported inference from identifiability to sample complexity: [20, Theorem II.1] shows only that the combined power spectrum and bispectrum determine the image up to rotation, which is an identifiability result, not a minimax or Fisher-information lower bound. Furthermore, the final step 'applying Proposition III.4 and Theorem A.9 proves the lower bound' is a category error, since Proposition III.4 is an upper-bound statement (it gives N = ω(σ^{2\\bar d}) sufficient for consistency when autocorrelations identify the orbit). An upper-bound theorem cannot yield N* ≥ ω(σ^6); a lower bound would require a dedicated argument (e.g., a minimax bound for the uniform-SO(2) MRA model, as in [4] for specific regimes) or a citation to such a result. As written, Proposition V.2 is unsupported, and because Section V.B leaves the upper bound as a conjecture, no 2D MTD rate is established.","section":"Appendix E (proof of Proposition V.2)"},{"comment":"The proof of the upper-bound framework is incomplete. Lemma A.7 applies [22, Theorem 2.1] to the extremum estimator defined in (A.39), but it verifies only pointwise convergence of the empirical autocorrelations (Corollary A.6), not the uniform convergence in probability over the compact parameter space that the theorem requires. Without uniform convergence (or an explicit stochastic equicontinuity argument for the polynomial objective), consistency of the estimated orbit does not follow. In addition, the variance bound E[(a_z^{(d)} - \\bar\\mu^{(d)})^2] = O(σ^{2d}/N) in Corollary A.5 is asserted on the basis of a nonexistent 'Lemma A.3' (likely Corollary A.3) and with no derivation; this bound is the quantitative engine behind the claimed N = ω(σ^{2\\bar d}) rate, so it needs a proof or citation. These gaps affect the upper-bound claims in Propositions V.1(1) and V.3.","section":"Appendix B (Lemma A.7, Proposition III.4)"}],"minor_comments":[{"comment":"The notation ω(σ^6) is used in a nonstandard way: phrases such as 'bounded from above by ω(σ^6)' are not meaningful in standard asymptotic notation, since ω(f) denotes a class of functions growing faster than f. Please define the intended meaning (e.g., 'N = ω(σ^6) is sufficient' vs. 'N = O(σ^6)') or replace with Θ/O notation.","section":"Throughout"},{"comment":"The set C_M^{(i)} is defined by |m - r_i| < L, but the sum in (A.19) ranges over k = -L,...,L-1, including the index r_i - L. The definition should be r_i - L ≤ m ≤ r_i + L - 1 to match the decomposition.","section":"Appendix A, Eq. (A.16)"},{"comment":"The text refers to 'Lemma A.3' when the variance bound is established earlier in Corollary A.3; please correct the citation.","section":"Appendix B, proof of Corollary A.5"},{"comment":"The last sentence of the proof of Proposition IV.1 says 'which completes the proof of the proportion'; this should be 'proposition'.","section":"Appendix C"},{"comment":"Please clarify the status of Proposition V.2 in the main text: the proof in Appendix E is not valid, and the upper bound is explicitly conjectural, so the proposition should be labeled as a conjecture or re-proven.","section":"Section V.B"}],"recommendation":"major_revision","confidential_remarks":"The strengths of the paper are the clean reduction from MTD to MRA (Proposition IV.1) and the autocorrelation convergence result (Proposition III.3), which together give a solid Θ(σ^6) result for 1D circular translations. The SO(2) lower bound is the advertised novel 2D result and is unsupported as written; since the upper bound is already conjectural, the 2D section currently provides no proven bound. This is the main reason for major revision rather than rejection: the flaw is in the proof strategy of one proposition, and it may be repairable by either proving a proper lower bound for uniform-SO(2) MRA or by downgrading the claim to a conjecture."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper’s real contribution is the reduction from MTD to MRA (Prop. IV.1) and the general upper-bound framework built on autocorrelations (Prop. III.4). The concrete result for 1D circular translations — Θ(σ^6) in the high-noise regime — is new and, as far as I can tell, correct. The proof is transparent: the lower bound comes from the known MRA rate, and the upper bound from the fact that the third-order autocorrelation identifies the orbit. That part deserves to be in the literature.\n\nThe paper is also honest about its limits. It explicitly leaves the translation-free lower bound open and labels the SO(2) upper bound as conjectural. That is good practice.\n\nWhere it falls short is Proposition V.2. The lower bound for SO(2) rotations is not actually proved. The argument in Appendix E reduces to MRA and then cites [20, Thm II.1] for uniqueness from the bispectrum. But uniqueness of the third moment does not by itself imply a sample-complexity rate of σ^6. That requires a minimax or Fisher-information argument, and the paper does not supply one. The sentence \"as the minimal moment required to determine uniquely the signal x is the third moment\" is an assertion, not a proof. As written, the 2D lower bound is unsupported. This matters because it is the only claimed 2D result.\n\nA second, minor issue: the notation is confusing. They use ω(σ^6) for both upper and lower bounds. Standard usage would be O(σ^6) and Ω(σ^6), or Θ(σ^6) if the matching is meant. As written, a reader has to reverse-engineer what \"ω\" means in each sentence.\n\nThe proof of Prop. III.4 is a bit terse. The variance bound in Cor. A.5 is stated as O(σ^{2d}/N) with the heuristic \"the number of Gaussian noise terms multiplied is at most d.\" That is plausible but deserves a more careful derivation, especially because the whole upper-bound story rests on it.\n\nWorth refereeing? Yes. The 1D result is solid and the reduction is a useful tool for the subfield. But the SO(2) lower bound needs to be either proved, replaced by a citation to a rigorous rate, or explicitly demoted to a conjecture. I would send it to peer review with a request for major revision on that section.","headline":"A clean MTD-to-MRA reduction and a plausible Θ(σ^6) rate for circular translations; the SO(2) lower bound is asserted rather than proved.","tokens_in":15261,"tokens_out":1919,"would_cite":true,"duration_ms":21718,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","62F12"],"pacs":[],"model":"deepseek-v4-flash","headline":"For multi-target detection in high noise, the sample-complexity cost is of order σ^6.","keywords":["multi-target detection","sample complexity","autocorrelation analysis","multi-reference alignment","cryo-EM","high-noise regime","circular translations","Fourier-Bessel basis"],"falsifier":"For a concrete check, pick a signal in $\\mathbb{R}^L$ with non-vanishing DFT, simulate the 1-D circular-translation MTD model at noise level $\\sigma$ with $N \\sim \\sigma^4$ well-separated occurrences, and see whether an estimator built from the empirical covariance (second-order autocorrelation) drives the orbit MSE to zero as $\\sigma \\to \\infty$. The paper's lower bound predicts that no such second-order estimator can succeed at this rate; if one does, the claimed $\\Theta(\\sigma^6)$ sample complexity is wrong.","tokens_in":14287,"feed_emoji":"🎯","tokens_out":9705,"duration_ms":91346,"temperature":0.7,"pith_summary":"This paper asks how many signal occurrences are needed to recover the shape of a target signal from one long, very noisy recording in which the target appears many times at unknown locations and in unknown orientations. Its central result is that in the high-noise regime the answer is of order $\\sigma^6$, where $\\sigma$ is the noise level, for the one-dimensional model with uniform circular translations: the authors prove both that autocorrelations up to third order give a recovery method needing only on the order of $\\sigma^6$ occurrences and that no estimator can succeed with substantially fewer. The same third-order mechanism gives a lower bound of order $\\sigma^6$ for two-dimensional rotations and an upper bound of order $\\sigma^6$ when there is no group action, with matching lower bound conjectured. The broader message is that the sample complexity of these models is governed by the lowest order of autocorrelation that uniquely determines the orbit of the signal under the group, and that a reduction to multi-reference alignment turns known sample-complexity results into lower bounds for the harder unknown-location problem.","feed_headline":"Hidden-target recovery costs σ^6 samples in high noise","feed_subtitle":"Autocorrelations up to third order set both upper and lower bounds in the uniform circular-translation model.","key_machinery":"The load-bearing objects are the empirical autocorrelations of the recorded trace, $a_z^{(d)}[\\ell_1,\\dots,\\ell_{d-1}]$, which average products of entries at fixed lags and are invariant to unknown target locations. Under the well-separated assumption, Proposition III.3 shows that these empirical autocorrelations converge almost surely to the ensemble mean of a single randomized target, which turns location uncertainty into a clean statistical limit. The two other load-bearing tools are a reduction from MTD to multi-reference alignment (any estimator for MTD would solve the easier known-location MRA problem, so MTD's sample complexity is at least MRA's) and a compactness-plus-continuity argument that promotes convergence of autocorrelation tensors to convergence of the estimated orbit.","core_discovery":"For the multi-target detection (MTD) model, in the high-noise regime where $\\sigma, N, M\\to\\infty$ with fixed density $\\gamma=N/M$, the paper establishes that sample complexity is controlled by the lowest autocorrelation order that identifies the signal orbit. For one-dimensional MTD with uniformly distributed circular translations, Propositions V.1 and III.4 together give an upper bound of order $\\sigma^6$ for well-separated targets and a lower bound of order $\\sigma^6$ for merely non-overlapping targets, so the high-noise sample complexity is exactly $\\Theta(\\sigma^6)$. For two-dimensional band-limited images rotated by uniform SO(2), the paper proves the lower bound of order $\\sigma^6$ and conjectures the upper bound; for the no-group-action case it proves the $\\sigma^6$ upper bound and conjectures the lower. The mechanism behind the upper bounds is Proposition III.4: whenever autocorrelation ensemble means up to order $\\bar d$ uniquely determine the orbit, recovery from the empirical autocorrelations is achievable with sample complexity at most order $\\sigma^{2\\bar d}$. The mechanism behind the lower bounds is Proposition IV.1: unknown locations cannot make estimation any easier than the corresponding multi-reference alignment problem, so any sample-complexity lower bound for MRA transfers directly to MTD.","pith_inferences":["The reduction in Proposition IV.1 suggests a testable invariance: the asymptotic sample-complexity exponent for MTD should equal that of the corresponding MRA problem whenever the target spacing satisfies the non-overlapping condition, so empirical comparisons of MRA and MTD estimators at matched densities would directly check the tightness.","The general $\\sigma^{2\\bar d}$ upper bound implies that searching for group actions and measurement geometries with uniquely identifying low-order moments is a practical design principle: lower-order identification means cheaper recovery from noisy micrographs.","If the conjectured 2-D SO(2) upper bound is confirmed by a provable algorithm, the same machinery would likely extend to cryo-EM projection models, where the relevant moments are projection-rotation invariants; the paper's outlook already points in that direction."],"forward_implications":["For the 1-D uniform circular-translation model, the sample complexity is $\\Theta(\\sigma^6)$ in high noise; any estimator, autocorrelation-based or not, must use on the order of $\\sigma^6$ signal occurrences to reach a fixed small MSE, and the autocorrelation method achieves this rate.","For non-uniform translation distributions, the lower bound falls to order $\\sigma^4$, so the distribution over the group, not just the group itself, determines the exponent in the sample complexity.","For 2-D band-limited images under uniform SO(2) rotations, the sample complexity is at least order $\\sigma^6$; if the conjectured upper bound holds, the exponent matches the 1-D circular-translation case.","When no group acts on the signal, the third-order autocorrelation still gives an upper bound of order $\\sigma^6$, so unknown locations alone already force this rate.","General principle: whenever the autocorrelation ensemble mean up to order $\\bar d$ uniquely determines the orbit, recovery is possible with at most order $\\sigma^{2\\bar d}$ occurrences; this is the engine behind all the upper bounds."],"supporting_citations":[{"why":"Introduces the MTD observation model and proves that the first three autocorrelations determine a generic signal in the no-group-action case, the uniqueness input for Proposition V.3.","marker":"[7]"},{"why":"Establishes the $\\sigma^6$ sample-complexity lower bound for circular-translation multi-reference alignment, which Proposition IV.1 transfers to the MTD lower bound.","marker":"[1]"},{"why":"Shows that autocorrelations up to order three uniquely determine the orbit when the DFT is non-vanishing, giving the upper bound in Proposition V.1.","marker":"[11]"},{"why":"Provides the power-spectrum-plus-bispectrum uniqueness theorem for band-limited images, the basis for the 2-D SO(2) lower bound in Proposition V.2.","marker":"[20]"},{"why":"Supplies sample-complexity results for general MRA and cryo-EM models that the outlook uses to extend the lower-bound framework.","marker":"[4]"},{"why":"Theorem 2.1 supplies the likelihood-consistency step that turns convergence of autocorrelation tensors into convergence of the estimated orbit in Proposition III.4.","marker":"[22]"}],"fun_headline_variants":["Hidden-target recovery: σ^6 samples suffice and are needed","MTD sample complexity pinned to σ^6 in high noise","Autocorrelation order dictates MTD sample cost","Multi-target detection: sample complexity scales as σ^6","High-noise MTD sample bound: Θ(σ^6)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The matching $\\sigma^6$ story depends on the claim that the third autocorrelation moment is the first one that can uniquely identify the signal's orbit: the upper bounds require third-order autocorrelations to be sufficient, and the lower bound for rotation-invariant images imports from a cited theorem that the power spectrum and bispectrum together determine an image up to rotation, but does not independently prove that no lower-order statistic could determine the orbit at finite sample size.","fun_headline_variants_meta":{"raw":{"variants":["Hidden-target recovery: σ^6 samples suffice and are needed","MTD sample complexity pinned to σ^6 in high noise","Autocorrelation order dictates MTD sample cost","Multi-target detection: sample complexity scales as σ^6","High-noise MTD sample bound: Θ(σ^6)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001008,"raw_usage":{"total_tokens":4266,"prompt_tokens":958,"completion_tokens":3308,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":3226}},"tokens_in":574,"tokens_out":3308,"duration_ms":24329,"temperature":1.0,"reasoning_tokens":3226,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:38:01.566112+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a concrete check, pick a signal in $\\mathbb{R}^L$ with non-vanishing DFT, simulate the 1-D circular-translation MTD model at noise level $\\sigma$ with $N \\sim \\sigma^4$ well-separated occurrences, and see whether an estimator built from the empirical covariance (second-order autocorrelation) drives the orbit MSE to zero as $\\sigma \\to \\infty$. The paper's lower bound predicts that no such second-order estimator can succeed at this rate; if one does, the claimed $\\Theta(\\sigma^6)$ sample complexity is wrong.","supporting_citations":[{"cited_title":"Multi-target detection with application to cryo- electron microscopy","cited_arxiv_id":null,"evidence_quote":"Introduces the MTD observation model and proves that the first three autocorrelations determine a generic signal in the no-group-action case, the uniqueness input for Proposition V.3."},{"cited_title":"Multireference alignment is easier with an aperiodic translation distribution","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\sigma^6$ sample-complexity lower bound for circular-translation multi-reference alignment, which Proposition IV.1 transfers to the MTD lower bound."},{"cited_title":"Multi-target detection with rotations","cited_arxiv_id":null,"evidence_quote":"Shows that autocorrelations up to order three uniquely determine the orbit when the DFT is non-vanishing, giving the upper bound in Proposition V.1."},{"cited_title":"Heterogeneous multireference alignment for images with application to 2D classification in single particle reconstruc- tion","cited_arxiv_id":null,"evidence_quote":"Provides the power-spectrum-plus-bispectrum uniqueness theorem for band-limited images, the basis for the 2-D SO(2) lower bound in Proposition V.2."},{"cited_title":"Estimation under group actions: recovering orbits from invariants","cited_arxiv_id":null,"evidence_quote":"Supplies sample-complexity results for general MRA and cryo-EM models that the outlook uses to extend the lower-bound framework."},{"cited_title":"Chapter 36 large sample estimation and hypothesis testing","cited_arxiv_id":null,"evidence_quote":"Theorem 2.1 supplies the likelihood-consistency step that turns convergence of autocorrelation tensors into convergence of the estimated orbit in Proposition III.4."}],"review_version":1}