{"id":"b78bac50-7e4a-4d6f-a5ff-255ee7a749e2","arxiv_id":"2506.11547","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Rotation estimation is cast as finding the common intersection point of quaternion-circle curves, solved by a GPU-parallel Hough voting that tolerates 99% outliers.","lead":"A new method estimates the rotation between two point sets even when 99% of input correspondences are wrong, using a voting scheme on quaternion curves. It reports solving problems with a million correspondences in under half a second on a GPU.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 99%-outlier robustness claim rests on an unproven inlier-peak-dominance assumption; structured outliers at that rate are not tested, so the headline is an extrapolation.","rationale":"The paper's central claim has two parts: a linear reformulation via quaternion circles, and a Hough-style rotation voting method that is supposedly extremely robust and fast. The linear reformulation is well supported and, as the appendices acknowledge, is related to earlier OLAE and dual-quaternion formulations; I do not see a soundness problem there. The load-bearing part is the robustness claim. For the voting method to succeed at 99% outlier ratio, the true rotation's discretized accumulator cell must receive more votes than every false peak. That condition is plausible for random outliers, where the empirical results are indeed striking, but it is not guaranteed and is not tested for structured outliers at the advertised 99% rate. The reader's weakest assumption identifies exactly this: the absence of any dominance guarantee or structured-outlier test at extreme corruption. My concrete test—sweeping the same-axis outlier fraction at ρ=99% and measuring both success and the raw accumulator margin—would distinguish between a robust phenomenon and an artifact of the particular random-outlier generator used. If the margin stays positive across the sweep, the conditional concern is resolved; if not, the headline should be weakened. Since the reader's verdict is already CONDITIONAL and my concern does not move it, I recommend no change to the verdict.","tokens_in":33567,"tokens_out":21719,"duration_ms":226379,"concrete_test":"Run the §5.3.1 synthetic benchmark at N=10^5, δ=0.01, ρ=0.99, choosing the true rotation axis different from the shared outlier axis, and sweep the same-axis outlier fraction η from 0 to 0.99 while the remaining outliers are random. For each η cell, repeat 500 trials and record success (rotation error ≤5°) and the accumulator margin M = votes(true bin) − max_{bin≠true} votes(bin). If any cell yields success below 100% or M≤0, the extreme-robustness claim fails for structured outliers; if M>0 throughout the sweep, the reader's concern is empirically resolved. Repeat at N=10^6 to verify the runtime claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is that, at resolution ε=1/180 and sampling J=180, the true rotation's accumulator bin is always the global maximum even when 99% of N=10^5–10^6 inputs are outliers. This requires inlier circles—only about 1% of the data—to cast more votes at the true bin than any accidental or structured false peak. No worst-case or probabilistic dominance bound is provided; Algorithm 1 simply returns the argmax bin with no consensus certificate. The experiments do not cover the advertised structured-outlier regime: §5.3.1/Fig. 6 uses random mismatches at ρ=99%, while the same-axis structured-outlier benchmark in Table 1 is tested only up to η=40%, and at inlier ratios of 5–20%, not 1%. Thus the combination '99% outliers plus structured outlier geometry'—precisely where the no-guarantee assumption is weakest—is untested. A related gap is reproducibility: no code is released, so the 10^6-point/0.5s runtime and the 100% success rates cannot be independently checked. This does not undermine the quaternion-circle linearization, which is mathematically sound, but it leaves the extreme-robustness headline as an extrapolation rather than an established result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a reformulation of the rotation estimation problem Ra=b using quaternion circles: for each correspondence, the set of rotation quaternions satisfying the constraint lies on a great circle in S^3, which can be described by two linear equations. The authors use this to derive a closed-form linear least-squares solution for outlier-free cases and a Hough-style voting algorithm in a stereographically projected 3D space for outlier-robust cases. They claim linear time complexity O(N/ε^3), extreme robustness to 99% outliers at scale 10^6, and support these claims with synthetic and real-world experiments, including panoramic image stitching, 6D pose estimation, and multi-motion estimation.","tokens_in":33892,"tokens_out":5318,"duration_ms":59307,"significance":"If the central claims are correct, the quaternion-circle linearization is an elegant and potentially useful geometric insight that connects rotation estimation to linear model fitting and voting, with clear GPU parallelizability. The empirical results suggest the voting method is competitive with or faster than state-of-the-art robust estimators in several settings. The paper also demonstrates an interesting failure mode of decomposition-based axis-first methods. However, the significance is dampened by an incorrect complexity statement, an unproven central lemma in the main text, and a robustness claim that is experimentally supported only for random, unstructured outliers at the extreme 99% level, not for structured outlier geometries at that rate.","major_comments":[{"comment":"The stated time complexity O(N/ε^3) does not follow from Algorithm 1. In Algorithm 1, for each input the inner loop (lines 5–9) iterates over J samples and performs O(1) accumulator updates per sample; the algorithm never iterates over the O(1/ε^3) accumulator cells on a per-input basis. The total runtime is therefore O(NJ), independent of ε except through the memory footprint of the accumulator. The claimed complexity in the contribution bullet should be corrected to O(NJ) runtime with O(1/ε^3) memory, or the algorithm should be modified so that ε actually appears in the per-input cost.","section":"Section 4.3.2 and Contribution bullet (Section 3.1)"},{"comment":"The headline robustness claim of handling 99% outlier ratios is only demonstrated for random mismatches (Fig. 6). The structured same-axis outlier experiments in Table 1 are run only up to η=40% and with inlier ratios of 5–20%, not at the 1% inlier level implied by 99% outliers. No worst-case or probabilistic argument is provided to guarantee that the accumulator's global maximum coincides with the true rotation at ε=1/180 under such extreme structured corruption. The abstract's statement that the method can solve 'severely corrupted (99% outlier ratio) rotation estimation problems' is therefore an extrapolation beyond the tested regime; the authors should either add experiments with structured or adversarial outlier geometries at ρ=99% or explicitly restrict the claim to the settings actually tested.","section":"Section 5.3.1, Abstract, and Table 1"},{"comment":"Lemma 1 is the foundation of the two-linear-equations-per-correspondence formulation, but it is stated with only 'can be easily proved, and we omit trivial explanations.' While Appendix A derives related linear constraints via the eigen-decomposition of the matrix M, the main text should provide a self-contained proof of Lemma 1 or explicitly reference the appendix derivation and state the conditions under which the vectors q_b3 and q_b4 are well-defined, particularly in the degenerate cases a=b or a=-b. As written, the central linearization rests on an unproved lemma in the main text.","section":"Section 4.2, Lemma 1"}],"minor_comments":[{"comment":"The statement that the linear method and SVD are 'identical' is supported only by empirical agreement; the text should be reworded to say the results are numerically indistinguishable in the tested settings, since no formal equivalence is proven.","section":"Section 5.2"},{"comment":"There are several typos and wording issues, e.g., 'RASNAC' for RANSAC, 'homomorphically' for 'homeomorphically', 'quanternion' for 'quaternion', and 'explore the dual structure' where a more precise term may be intended. A careful proofread is recommended.","section":"Throughout"},{"comment":"The axis labels 'N=105' should read 'N=10^5' or 'N=10^5' with a superscript; similarly, the noise and error axes should include units (degrees and milliseconds) consistently.","section":"Figure 6"},{"comment":"The header layout is confusing: 'inlier ratio 20%' appears as a row label rather than as a column group label, and the same-axis ratio η is not clearly defined in the table itself. Please restructure the table for readability.","section":"Table 1"},{"comment":"The paper claims the formulation introduces no singularities, but stereographic projection has a singularity at the north pole. The authors should explicitly state that the choice of the lower hemisphere avoids this point and discuss the boundary case q3=0.","section":"Section 4.3.1"},{"comment":"The voting procedure returns only the center of the block with the highest count; no sub-grid refinement or peak verification is described. At 99% outlier ratios, spurious peaks could be a concern; a brief discussion or a refinement step would strengthen the method.","section":"Section 4.3.2"},{"comment":"No code or data are released. Given that the 10^6-point/0.5-second runtime and 100% success rates are central to the paper's claims, providing an implementation would greatly aid verification.","section":"Reproducibility"}],"recommendation":"major_revision","confidential_remarks":"The paper's core geometric derivation appears sound, but the complexity claim is demonstrably inconsistent with Algorithm 1, and the extreme-robustness headline is not supported for structured outliers at the claimed 99% rate. The authors also state a key lemma without proof in the main text, relying on an appendix that is only loosely connected. These are fixable with a revision, but they are load-bearing for the paper's central claims. I would not recommend rejection, as the quaternion-circle linearization and the voting framework are promising and the experimental comparisons are informative. However, the lack of code and the overextended claims need to be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi,\n\nQuick take: this paper's algebraic core is sound but not new, and it says so itself in Appendices C and D. The genuinely interesting part is the Hough-style voting on stereographically projected quaternion circles, which gives very fast GPU rotation estimation in synthetic and real tests. If the speed and robustness are real, it's a useful engineering tool. But the headline 99%-outlier result is not yet established.\n\nWhat it does well: the derivation of two linear constraints per correspondence is correct and standard (quaternion product, orthonormal basis, null space), and the closed-form solution matches SVD in the noise-free and noisy cases. The experiments are unusually broad: synthetic noise/outlier sweeps, panorama matching, 3DMatch/KITTI registration, multiple motions. The paper also deserves credit for acknowledging the overlap with OLAE [23] and dual-quaternion pairwise formulations [112,113]; that honesty makes the novelty claims easier to evaluate.\n\nSoft spots, in order of importance:\n\n1. The extreme-robustness claim is an extrapolation. At 99% outlier ratio, experiments only use random mismatches. The structured same-axis outliers are tested at η ≤ 40% with inlier ratios 5–20%, not 1% inliers. The voting argument needs inlier votes to dominate the true accumulator bin; no worst-case or probabilistic bound is given, and nothing in Algorithm 1 certifies the returned peak. So the abstract's \"99% outlier ratio\" sentence overstates what is demonstrated.\n\n2. The complexity statement O(N/ε^3) does not follow from Algorithm 1. Per input the cost is O(J) plus O(1) accumulator update; the number of bins is O(1/ε^3) but that's memory, not per-input time. Maybe they meant O(NJ) with J = O(1/ε), but as written it is wrong.\n\n3. Lemma 1 is stated without proof. It's trivial to prove from the orthonormal basis argument, so this is a minor presentation issue, not a substantive gap.\n\n4. No code. The 10^6-point/0.5s runtime and 100% success rates cannot be independently verified.\n\nWould I send this to peer review? Yes. The math is mostly sound, the empirical sweep is impressive, and the problem matters. But I'd make the authors either provide a formal robustness guarantee (or a certificate) or visibly narrow the claims, fix the complexity analysis, and release code. Roughly: a promising systems/speed paper wearing the clothes of a theory paper.\n\nFor a reading group, worth a maybe—good discussion of what \"linear\" means when you discretize a sphere and vote.","headline":"The quaternion-circle linearization is elegant but largely a repackaging of known linear attitude estimators; the real question is whether the GPU Hough voting's 99%-outlier claim survives structured outliers.","tokens_in":34351,"tokens_out":3850,"would_cite":false,"duration_ms":36872,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that robust rotation estimation reduces to a linear voting problem: each rotation constraint becomes a great circle on the quaternion sphere, and the rotation is the most-intersected projected curve.","keywords":["rotation estimation","robust model fitting","quaternion circle","Hough voting","stereographic projection","outlier robustness","Wahba's problem","rigid pose estimation"],"falsifier":"Run the voting algorithm at $\\varepsilon=1/180$ on a synthetic problem with $N=10^5$ and 99% outliers engineered so that a large block of outlier quaternion circles all pass close to one fake rotation point (for instance, many same-axis rotations with angles chosen to cluster in the accumulator) and check whether the global vote maximum corresponds to the fake rather than the true rotation.","tokens_in":33381,"feed_emoji":"🔄","tokens_out":5070,"duration_ms":54359,"temperature":0.7,"pith_summary":"Rotation estimation is normally treated as a nonlinear, non-convex optimization problem, but this paper seeks to show that it can be reformulated as a linear model-fitting problem with no constraints dropped and no singularities introduced. The key geometric fact is that the set of rotations carrying one unit vector to another forms a great circle on the unit quaternion sphere; equivalently, each such motion contributes two linear equations in the quaternion. Using a stereographic projection, these quaternion circles become ordinary circles in a 3D ball, so finding the rotation becomes finding the point where the most projected curves intersect. The authors build a GPU-friendly Hough-style voting algorithm around this, reporting linear-time behavior in the number of correspondences and empirical success at one million inputs with 99% outliers in under half a second. If the reformulation is right, the notoriously difficult robust rotation problem inherits the maturity of robust linear model fitting.","feed_headline":"Rotation estimation becomes a linear voting problem","feed_subtitle":"Each rotation constraint maps to a great circle; the true rotation is the point most circles cross, at 99% outlier ratios.","key_machinery":"The central object is the quaternion circle: for a given motion $Ra=b$, all quaternions representing compatible rotations form a great circle on the unit sphere $S^3$, spanned by two orthonormal quaternion basis vectors $q_{b1}$ and $q_{b2}$. The orthogonal complement space gives two linear equations per observation, so a rotation estimate becomes the least-squares null vector of a stacked linear system. For robust estimation, a stereographic projection from the north pole maps the half quaternion sphere into the unit 3D ball, and the circle-preserving property turns each quaternion circle into a circle or line in $\\mathbb{R}^3$; a Hough-style accumulator then votes for the intersecting point, with resolution $\\varepsilon$ controlling the grid. This three-step pipeline—quaternion circle, linear equations, projected voting—is what makes the rotation problem linear and embarrassingly parallel.","core_discovery":"The paper's central claim is that the constraint $Ra=b$, instead of living on the nonconvex manifold $\\mathrm{SO}(3)$, can be described exactly by a great circle on $S^3$, the quaternion circle. For each observation the circle is $C_{\\mathrm{quat}} = \\{q_{b1}\\cos(\\alpha/2) + q_{b2}\\sin(\\alpha/2)\\}$; the two basis quaternions $q_{b1},q_{b2}$ are orthonormal, and the complementary vectors $q_{b3},q_{b4}$ give two homogeneous linear equations $[q_{b3}^T; q_{b4}^T]q=0$. Thus $N$ correspondences yield a $2N\\times 4$ matrix $Q$ whose null vector is the sought quaternion; in the outlier-free case the rotation is the eigenvector belonging to the smallest eigenvalue of $Q^TQ$. In the outlier case, the same linear equations are projected by stereographic projection into 3D circles, and the rotation is recovered by voting for the point that intersects the greatest number of projected curves. The paper also claims this voting is the first linear-time algorithm for robust rotation estimation, with complexity $O(N/\\varepsilon^3)$, and that it extends directly to multiple rotations and to 6D rigid pose via pairwise constraints.","pith_inferences":["The same quaternion-circle linearization could be applied to rotation averaging or translation voting, possibly converting iterative averaging into one-shot voting; the paper does not pursue this direction.","The 99% robustness is demonstrated empirically, not certified; an adversarial outlier distribution engineered to concentrate votes at a fake rotation would provide a sharper test of whether the accumulator's global maximum is guaranteed.","The resolution $\\varepsilon$ and sampling number $J$ create a memory-accuracy tradeoff, and one could derive bounds on how fine $\\varepsilon$ must be as a function of noise level and outlier fraction; the paper does not provide such bounds.","The paper's closing conjecture that a similar linear formulation may exist for $\\mathrm{SE}(3)$ suggests a concrete next target: finding the analog of the quaternion circle for rotations plus translations."],"forward_implications":["If the reformulation is correct, robust rotation estimation can be solved by the same tools as robust linear model fitting, instead of specialized nonconvex optimization.","The claimed $O(N/\\varepsilon^3)$ complexity means the method scales linearly in input count at fixed accuracy, and the voting loop is embarrassingly parallel, so GPU speedups are direct.","At the tested resolution, the method reports 100% success at 5% inlier ratio with structured same-axis outliers, whereas decomposition-based axis-only methods can fail because they drop the angle constraint.","The method returns multiple high peaks in one pass, so multiple simultaneous rotations in one scene can be estimated without repeated RANSAC-style sequential fitting.","Embedded in a pairwise-decomposition pose pipeline, the method reaches comparable accuracy on 3DMatch, 3DLoMatch, and KITTI while running faster than compared baselines in the reported experiments."],"supporting_citations":[{"why":"Supplies the Hough-transform voting idea that the rotation voting method is built on.","marker":"[25]"},{"why":"Provides the quaternion closed-form solution used in deriving the alternative quaternion-circle formulation.","marker":"[31]"},{"why":"Gives the axis-decomposition baseline whose dropped angle constraint motivates the exact two-equation reformulation.","marker":"[34]"},{"why":"Provides the circle-preserving property of stereographic projection used to map quaternion circles into 3D circles.","marker":"[75]"},{"why":"Shows an earlier linearized attitude estimator with singularities, which the paper contrasts with its singularity-free formulation.","marker":"[23]"},{"why":"Supplies the RANSAC baseline against which success rate and running time are measured.","marker":"[35]"},{"why":"Supplies the guaranteed-outlier-removal baseline and rotation-search method compared on synthetic and real data.","marker":"[40]"},{"why":"Supplies the certifiable TEASER++ baseline for rigid pose and point cloud registration comparisons.","marker":"[49]"}],"fun_headline_variants":["Rotation estimation becomes linear voting","Great-circle voting solves rotation estimation","Rotation from linear equations and voting","Robust rotation via efficient voting method","Linear-time robust rotation estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The extreme robustness results rest on the unproved assumption that at the chosen accumulator resolution $\\varepsilon=1/180$, genuine inlier votes always form the global maximum while outlier votes stay dispersed, even for structured outlier mixes up to 99%; the paper supports this only empirically, with no worst-case or probabilistic guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Rotation estimation becomes linear voting","Great-circle voting solves rotation estimation","Rotation from linear equations and voting","Robust rotation via efficient voting method","Linear-time robust rotation estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000441,"raw_usage":{"total_tokens":2282,"prompt_tokens":1040,"completion_tokens":1242,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":1187}},"tokens_in":656,"tokens_out":1242,"duration_ms":11415,"temperature":1.0,"reasoning_tokens":1187,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:05:08.726566+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the voting algorithm at $\\varepsilon=1/180$ on a synthetic problem with $N=10^5$ and 99% outliers engineered so that a large block of outlier quaternion circles all pass close to one fake rotation point (for instance, many same-axis rotations with angles chosen to cluster in the accumulator) and check whether the global vote maximum corresponds to the fake rather than the true rotation.","supporting_citations":[{"cited_title":"The geometry of m ¨obius transformations,","cited_arxiv_id":null,"evidence_quote":"Provides the circle-preserving property of stereographic projection used to map quaternion circles into 3D circles."},{"cited_title":"Guaranteed outlier removal for point cloud registration with correspondences,","cited_arxiv_id":null,"evidence_quote":"Supplies the guaranteed-outlier-removal baseline and rotation-search method compared on synthetic and real data."},{"cited_title":"Teaser: Fast and certifiable point cloud registration,","cited_arxiv_id":null,"evidence_quote":"Supplies the certifiable TEASER++ baseline for rigid pose and point cloud registration comparisons."}],"review_version":1}