×

Automatic multivector differentiation and optimization. (English) Zbl 1367.65034

Summary: In this work, we present a novel approach to nonlinear optimization of multivectors in the Euclidean and conformal model of geometric algebra by introducing automatic differentiation. This is used to compute gradients and Jacobian matrices of multivector valued functions for use in nonlinear optimization where the emphasis is on the estimation of rigid body motions.

MSC:

65D25 Numerical differentiation
65K05 Numerical mathematical programming methods
15A66 Clifford algebras, spinors
90C30 Nonlinear programming
70E15 Free motion of a rigid body
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, S., Mierle, K. et al.: Ceres Solver. http://ceres-solver.org
[2] Agarwal, S., Snavely, N., Seitz, S.M., Szeliski, R.: Bundle Adjustment in the Large. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV (2), vol. 6312, Lecture Notes in Computer Science, pp. 29-42. Springer, Berlin (2010)
[3] Baydin, A.G., Barak, A.: Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: a survey. CoRR (2015). arXiv:abs/1502.05767 · Zbl 06982909
[4] Bayro-Corrochano E., Daniilidis K., Sommer G.: Motor algebra for 3D kinematics: the case of the hand-eye calibration. J. Math. Imaging Vis. 13(2), 79-100 (2000) · Zbl 0969.68645
[5] Cibura, C.: Fitting Model Parameters in Conformal Geometric Algebra to Euclidean Observation Data. PhD thesis, University of Amsterdam (2012) · Zbl 1177.65020
[6] Clifford W.K.: Preliminary Sketch of Biquaternions. Proc. Lond. Math. Soc. 4, 361-395 (1873) · JFM 05.0280.01
[7] Colapinto, P.: Versor: Spatial Computing with Conformal Geometric Algebra. Master’s thesis, University of California at Santa Barbara (2011). http://versor.mat.ucsb.edu · Zbl 1177.65020
[8] Colapinto P.: Boosted surfaces: synthesis of meshes using point pair generators as curvature operators in the 3d conformal model. Adv. Appl. Clifford Algebras 24(1), 71-88 (2014) · Zbl 1298.65032
[9] Colapinto, P.: Composing Surfaces with Conformal Rotors. In: Advances in Applied Clifford Algebras. pp. 1-22 (2016) · Zbl 1367.15033
[10] Dagum L., Menon R.: OpenMP: an industry standard API for shared-memory programming. Comput. Sci. Eng. IEEE. 5(1), 46-55 (1998)
[11] Davis, T.: SuiteSparse. http://faculty.cse.tamu.edu/davis/suitesparse.html. Online Accessed 25 July 2016
[12] Dorst, L.: The Representation of Rigid Body Motions in the Conformal Model of Geometric Algebra. In: Rosenhahn, B., Klette, R., Metaxas, D. (eds.) Human Motion, vol. 36, Computational Imaging and Vision, pp. 507-529. Springer (2008) · Zbl 1298.65032
[13] Dorst, L.: Conformal Geometric Algebra by Extended Vahlen Matrices. Methods of Information in Medicine, 1 (2009)
[14] Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Morgan Kaufmann Publishers Inc., San Francisco (2007)
[15] Dorst, L., Fontijne, D., Mann, S.: Gaviewer. http://www.geometricalgebra.net/gaviewer_download.html (2010). Online Accessed 25 July 2016
[16] Fontijne, D.: Gaigen 2.5. http://sourceforge.net/projects/g25/. Online Accessed 25 July 2016
[17] Fontijne, D.: Efficient Implementation of Geometric Algebra. PhD thesis, University of Amsterdam (2007)
[18] Fontijne, D., Dorst, L., Bouma, T.: Gaigen. https://sourceforge.net/projects/gaigen/. Online Accessed 07 July 2016
[19] Fowler, M.: Domain Specific Languages, 1st edn. Addison-Wesley Professional(2010)
[20] Gebken, C.: Conformal Geometric Algebra in Stochastic Optimization Problems of 3D-Vision Applications. PhD thesis, University of Kiel (2009)
[21] Gebken C., Perwass C., Sommer G.: Parameter estimation from uncertain data in geometric algebra. Adv. Appl. Clifford Algebras 18(3-4), 647-664 (2008) · Zbl 1177.65020
[22] Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2 edn. SIAM, Philadelphia (2008) · Zbl 1159.65026
[23] Guennebaud, G., Jacob, B. et al.: Eigen v3. http://eigen.tuxfamily.org (2010). Online; Accessed 25 July 2016
[24] Hartley R., Zisserman A.: Multiple View Geometry in Computer Vision, 2 edn. Cambridge University Press, New York (2003) · Zbl 0956.68149
[25] Hestenes, D.: New Foundations for Classical Mechanics, vol. 15, Fundamental Theories of Physics. Springer (1986) · Zbl 0612.70001
[26] Hestenes, D., Sobczyk, G.: Clifford Algebra to Geometric Calculus—A Unified Language for Mathematics and Physics, vol. 5, Fundamental Theories of Physics. Springer (1984) · Zbl 0541.53059
[27] Hildenbrand, D., Pitt, J., Koch, A.: Gaalop—High Performance Parallel Computing Based on Conformal Geometric Algebra. In: Bayro-Corrochano, E., Scheuermann, G. (eds.) Geometric Algebra Computing, pp. 477-494. Springer, Berlin (2010) · Zbl 1214.68434
[28] Hoffmann, P.H.W.: A Hitchhiker’s Guide to Automatic Differentiation. In: Numerical Algorithms. pp. 1-37 (2015)
[29] Hogan R.J.: Fast reverse-mode automatic differentiation using expression templates in C++. ACM Trans. Math. Softw. 40(4), 26-12616 (2014) · Zbl 1369.65037
[30] Iglberger K., Hager G., Treibig J., de Ulrich R.: Expression templates revisited:a performance analysis of current methodologies. SIAM J. Sci. Comput. 34(2), C42-C69 (2012)
[31] Lasenby J., Fitzgerald W.J., Lasenby A.N., Doran C.J.L.: New geometric methods for computer vision: an application to structure and motion estimation. Int. J. Comput. Vis. 26(3), 191-213 (1998)
[32] Li, H., Hestenes, D., Rockwood, A.: Generalized Homogeneous Coordinates for Computational Geometry. In: Sommer, G. (ed.) Geometric Computing with Clifford Algebras, pp. 27-59. Springer, Berlin (2001) · Zbl 1073.68849
[33] Madsen, K., Nielsen, H.B., Tingleff, O.: Methods for Non-Linear Least Squares Problems (2004) · Zbl 1369.65037
[34] Munaro, M., Basso, F., Menegatti, E.: OpenPTrack: Open source multi-camera calibration and people tracking for RGB-D camera networks. Robot. Auton. Syst. 75(Part B), 525-538 (2016)
[35] Nickolls J., Buck I., Garland M., Skadron K.: Scalable Parallel Programming with CUDA. Queue. 6(2), 40-53 (2008)
[36] Nocedal, J., Wright, S.J.: Numerical Optimization, 2 edn. Springer, New York (2006)
[37] Perwass, C.: Applications of Geometric Algebra in Computer Vision—The geometry of multiple view tensors and 3D-reconstruction. PhD thesis, University of Cambridge (2000)
[38] Perwass, C.: CLUCalc Interactive Visualization. http://www.clucalc.info/ (2010). Online; Accessed 25 July 2016 · Zbl 1242.20060
[39] Perwass, C., Gebken, C., Sommer, G.: Estimation of Geometric Entities and Operators from Uncertain Data. In: Pattern Recognition, vol. 3663, Lecture Notes in Computer Science, pp. 459-467. Springer, Berlin (2005)
[40] Schmidt, J., Niemann, H.: Using Quaternions for Parametrizing 3-D Rotations in Unconstrained Nonlinear Optimization. In: VMV, pp. 399-406. Aka GmbH (2001)
[41] Schwan, C.: hep-ga: An Efficient Numeric Template Library for Geometric Algebra
[42] Snygg, J.: Clifford Algebra in Euclidean 3-Space. In: A New Approach to Differential Geometry using Clifford’s Geometric Algebra, pp. 3-25. Birkhäuser, Boston (2012) · Zbl 1232.53002
[43] Sobczyk G.: Geometric matrix algebra. Linear Algebra Appl. 429(5-6), 1163-1173 (2008) · Zbl 1149.15024
[44] Sommer, H., Pradalier, C., Furgale, P.: Automatic Differentiation on Differentiable Manifolds as a Tool for Robotics. In: Int. Symp. on Robotics Research (ISRR) (2013)
[45] Stone J.E., Gohara D., Shi G.: OpenCL: a parallel programming standard for heterogeneous computing systems. IEEE Des. Test. 12(3), 66-73 (2010)
[46] Tingelstad, L.: GAME—Geometric Algebra Multivector Estimation. http://github.com/tingelst/game/ (2016)
[47] Umeyama S.: Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. Pattern Anal. Mach. Intell. 13(4), 376-380 (1991)
[48] Valkenburg, R., Alwesh, N.: Calibration of Target Positions Using Conformal Geometric Algebra. In: Dorst, L., Lasenby, J., (eds.) Guide to Geometric Algebra in Practice, pp. 127-148. Springer, London (2011) · Zbl 1290.68125
[49] Valkenburg, R., Dorst, L.: Estimating Motors from a Variety of Geometric Data in 3D Conformal Geometric Algebra. In: Dorst, L., Lasenby, J. (eds.) Guide to Geometric Algebra in Practice, pp. 25-45. Springer, London (2011) · Zbl 1290.68126
[50] Wareham, R., Cameron, J., Lasenby, J.: Applications of Conformal Geometric Algebra in Computer Vision and Graphics. In: Li, H., Olver, P.J., Sommer, G. (eds.) Computer Algebra and Geometric Algebra with Applications, pp. 329-349. Springer, Berlin (2005) · Zbl 1078.68812
[51] Woo, M., Neider, J., Davis, T., Shreiner, D.: OpenGL Programming Guide: The Official Guide to Learning OpenGL, Version 1.2, 3rd edn. Addison-Wesley Longman Publishing Co., Inc., Boston (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.