2023/11/28 by Owen Howell, Howell, Owen, Haoen Huang +3
Biochemistry, Genetics and Molecular Biology · Medicine · #Advanced MRI Techniques and Applications #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Mathematics #Gene Regulatory Network Analysis #Group Theory (math.GR) #Medical Imaging Techniques and Applications #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2311.16544
openalex publication_date 2023/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Rotation averaging (RA) is a fundamental problem in robotics and computer vision. In RA, the goal is to estimate a set of N unknown orientations R1, ..., RN ∈ SO(3), given noisy measurements Rij ∼ R-1i Rj of a subset of their pairwise relative rotations. This problem is both nonconvex and NP-hard, and thus difficult to solve in the general case. We apply harmonic analysis on compact groups to derive a (convex) spectral relaxation constructed from truncated Fourier decompositions of the individual summands appearing in the RA objective; we then recover an estimate of the RA solution by computing a few extremal eigenpairs of this relaxation, and (approximately) solving a consensus problem. Our approach affords several notable advantages versus prior RA methods: it can be used in conjunction with any smooth loss function (including, but not limited to, robust M-estimators), does not require any initialization, and is implemented using only simple (and highly scalable) linear-algebraic computations and parallelizable optimizations over band-limited functions of individual rotational states. Moreover, under the (physically well-motivated) assumption of multiplicative Langevin measurement noise, we derive explicit performance guarantees for our spectral estimator (in the form of probabilistic tail bounds on the estimation error) that are parameterized in terms of graph-theoretic quantities of the underlying measurement network. By concretely linking estimator performance with properties of the underlying measurement graph, our results also indicate how to devise measurement networks that are guaranteed to achieve accurate estimation, enabling such downstream tasks as sensor placement, network compression, and active sensing.