FFTs on the rotation group
Discrete polynomial transformFast Fourier transformPattern matchingRotation groupSpherical harmonics
Software, source code, etc. for problems pertaining to abstract harmonic analysis (43-04) Harmonic analysis on specific compact groups (43A75) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical algorithms for specific classes of architectures (65Y10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10)
An implementation is given of an algorithm for the numerical computation of Fourier transforms of band limited functions defined on the rotation group \(\text{SO}(3)\). The algorithm described herein uses \(\text{O}(B)\) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the \(\text{O}(B^3)\)) spherical harmonics of degree at most \(B\). This compares very favourably with the direct \(\text{O}(B^6)\) algorithm derived from a basic quadrature rule on \(\text{O}(B^3)\) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over \(\text{SO}(3)\) which has been used as the analytic engine for some new approaches to searching 3D databases: \textit{Funkhouser} et al. [ACM Trans Graph. 83--105 (2003)]; \textit{Kazhdan} et al. [Eurographics Symposium in Geometry Processing, 167--175 (2003)]. The implementation is based on the ``Separation of variables of \textit{D. K. Maslen} and \textit{D. N. Rockmore} [Workshop on groups and computation, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 183--237 (1997; Zbl 0892.20008)]. In conjunction with the techniques developed for the efficient computation of orthogonal polynomial expansions by \textit{J. R. Driscoll}, \textit{D. J. Healy jun.} and \textit{D. N. Rockmore} [SIAM J. Comput. 26, No. 4, 1066--1099 (1997; Zbl 0896.65094)], the fast \(\text{SO}(3)\) algorithm can be improved to give an algorithm of complexity \(O(B^3\log^2 B)\), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well.
- Fast summation of functions on the rotation group
- The crystallographic fast Fourier transform. I. p3 symmetry
- Computing Fourier transforms and convolutions on the 2-sphere
- Rotating a three-dimensional array in an optimal position for vector processing: Case study for a three-dimensional fast Fourier transform
- Fast Fourier transforms for space groups containing rotation axes of order three and higher
- FFTs for the 2-sphere-improvements and variations
- A fast algorithm for expansion over spherical harmonics
- A fast algorithm for nonequispaced Fourier transforms on the rotation group
- An Implementation of Multiple and Multivariate Fourier Transforms on Vector Processors
- Fast algorithms using orthogonal polynomials
- An empirical Bayes approach to directional data and efficient computation on the sphere
- Computation of spherical harmonic expansion coefficients via FFT's
- Computational harmonic analysis for tensor fields on the two-sphere
- Efficient computation of Fourier transforms on compact groups
- Fast Algorithms for Spherical Harmonic Expansions
- Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
- FFTs for the 2-sphere-improvements and variations
- Fourier transform summation of Legendre series and \(D\)-functions
- scientific article; zbMATH DE number 3427646 (Why is no real title available?)
- scientific article; zbMATH DE number 3130885 (Why is no real title available?)
- scientific article; zbMATH DE number 3140172 (Why is no real title available?)
- scientific article; zbMATH DE number 3743203 (Why is no real title available?)
- scientific article; zbMATH DE number 48956 (Why is no real title available?)
- scientific article; zbMATH DE number 3577138 (Why is no real title available?)
- scientific article; zbMATH DE number 1739749 (Why is no real title available?)
- scientific article; zbMATH DE number 3274385 (Why is no real title available?)
- scientific article; zbMATH DE number 3081828 (Why is no real title available?)
- Separation of variables and the computation of Fourier transforms on finite groups, I
- Towards safe and effective high-order Legendre transforms with applications to FFTs for the 2-sphere
- A fast algorithm for nonequispaced Fourier transforms on the rotation group
- Symmetry reduction of Fourier kernels
- Approximations on \(\mathrm{SO}(3)\) by Wigner D-matrix and applications
- Scale-free registrations in 3D: 7 degrees of freedom with Fourier Mellin SOFT transforms
- Closed solution of the Hill differential equation for short arcs and a local mass anomaly in the central body
- Nonuniform Fourier transforms for rigid-body and multidimensional rotational correlations
- Fast global optimization on the torus, the sphere, and the rotation group
- Kernel density estimation on the rotation group and its application to crystallographic texture analysis
- Non-commutative morphology: Shapes, filters, and convolutions
- Fast Fourier transforms for spherical Gauss-Laguerre basis functions
- A new algorithm for the nonequispaced fast Fourier transform on the rotation group
- Non-unique games over compact groups and orientation estimation in cryo-EM
- Radial recombination for rigid rotational alignment of images and volumes
- The concept of resolution in the domain of rotations
- Surface spline approximation on SO(3)
- Uncertainty propagation for general stochastic hybrid systems on compact Lie groups
- Probabilistic Marcinkiewicz-Zygmund inequalities on the rotation group
- Fast summation of functions on the rotation group
- Differentiable and accelerated spherical harmonic and Wigner transforms
- Optimal designs for regression on Lie groups
- On the role of the double Fourier sphere method in fast algorithms on \(\mathcal{SO} (3)\)
- Fast and Stable Harmonic Approximation from Ill-distributed Data using Moving Least Squares
- Stability results for scattered data interpolation on the rotation group
- Rosborough approach for the determination of regional time variability of the gravity field from satellite gradiometry data
- Correspondence-free structure from motion
This page was built for publication: FFTs on the rotation group
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483008)
