A global approach to the refinement of manifold data

Dyn, Nira; Sharon, Nir

doi:10.1090/mcom/3087

A global approach to the refinement of manifold data
HTML articles powered by AMS MathViewer

by Nira Dyn and Nir Sharon PDF

Math. Comp. 86 (2017), 375-395 Request permission

Abstract:

A refinement of manifold data is a computational process, which produces a denser set of discrete data from a given one. Such refinements are closely related to multiresolution representations of manifold data by pyramid transforms, and approximation of manifold-valued functions by repeated refinements schemes. Most refinement methods compute each refined element separately, independently of the computations of the other elements. Here we propose a global method which computes all the refined elements simultaneously, using geodesic averages. We analyse repeated refinements schemes based on this global approach, and derive conditions guaranteeing strong convergence.

References

Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR 1744486, DOI 10.1007/978-3-662-12494-9
Thomas J. Cashman, Kai Hormann, and Ulrich Reif, Generalized Lane-Riesenfeld algorithms, Comput. Aided Geom. Design 30 (2013), no. 4, 398–409. MR 3027876, DOI 10.1016/j.cagd.2013.02.001
G. M. Chaikin, An algorithm for high-speed curve generation, Comput. Graph. Image Process 3 (1974), 346–349.
K. Crane, C. Weischedel, and M. Wardetzky, Geodesics in heat: A new approach to computing distance based on heat flow, ACM Transactions on Graphics (TOG) 32 (2013), no. 5, p. 152.
Gilles Deslauriers and Serge Dubuc, Symmetric iterative interpolation processes, Constr. Approx. 5 (1989), no. 1, 49–68. Fractal approximation. MR 982724, DOI 10.1007/BF01889598
Manfredo Perdigão do Carmo, Riemannian geometry, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the second Portuguese edition by Francis Flaherty. MR 1138207, DOI 10.1007/978-1-4757-2201-7
N. Dyn, Subdivision schemes in computer-aided geometric design, Advances in numerical analysis, Vol. II (Lancaster, 1990) Oxford Sci. Publ., Oxford Univ. Press, New York, 1992, pp. 36–104. MR 1172120
Nira Dyn, Three families of nonlinear subdivision schemes, Topics in multivariate approximation and interpolation, Stud. Comput. Math., vol. 12, Elsevier B. V., Amsterdam, 2006, pp. 23–38. MR 2410694, DOI 10.1016/S1570-579X(06)80003-0
Nira Dyn and Elza Farkhi, Spline subdivision schemes for compact sets with metric averages, Trends in approximation theory (Nashville, TN, 2000) Innov. Appl. Math., Vanderbilt Univ. Press, Nashville, TN, 2001, pp. 93–102. MR 1938002
Nira Dyn and Ron Goldman, Convergence and smoothness of nonlinear Lane-Riesenfeld algorithms in the functional setting, Found. Comput. Math. 11 (2011), no. 1, 79–94. MR 2754190, DOI 10.1007/s10208-010-9080-2
Nira Dyn, David Levin, and John A. Gregory, A $4$-point interpolatory subdivision scheme for curve design, Comput. Aided Geom. Design 4 (1987), no. 4, 257–268. MR 937365, DOI 10.1016/0167-8396(87)90001-X
N. Dyn and N. Sharon, The convergence of manifold-valued subdivision schemes based on geodesic averaging, in prepration. Available at http://arxiv.org/abs/1407.8361.
Oliver Ebner, Convergence of refinement schemes on metric spaces, Proc. Amer. Math. Soc. 141 (2013), no. 2, 677–686. MR 2996972, DOI 10.1090/S0002-9939-2012-11331-0
Abbas M. Faridi and E. L. Schucking, Geodesics and deformed spheres, Proc. Amer. Math. Soc. 100 (1987), no. 3, 522–525. MR 891157, DOI 10.1090/S0002-9939-1987-0891157-0
Svatopluk Fučík and Alois Kufner, Nonlinear differential equations, Studies in Applied Mechanics, vol. 2, Elsevier Scientific Publishing Co., Amsterdam-New York, 1980. MR 558764
Daniel Genin, Boris Khesin, and Serge Tabachnikov, Geodesics on an ellipsoid in Minkowski space, Enseign. Math. (2) 53 (2007), no. 3-4, 307–331. MR 2455947
Philipp Grohs and Johannes Wallner, Definability and stability of multiscale decompositions for manifold-valued data, J. Franklin Inst. 349 (2012), no. 5, 1648–1664. MR 2917547, DOI 10.1016/j.jfranklin.2011.02.010
Fumio Hiai and Dénes Petz, Riemannian metrics on positive definite matrices related to means, Linear Algebra Appl. 430 (2009), no. 11-12, 3105–3130. MR 2517863, DOI 10.1016/j.laa.2009.01.025
Arieh Iserles, Hans Z. Munthe-Kaas, Syvert P. Nørsett, and Antonella Zanna, Lie-group methods, Acta numerica, 2000, Acta Numer., vol. 9, Cambridge Univ. Press, Cambridge, 2000, pp. 215–365. MR 1883629, DOI 10.1017/S0962492900002154
Uri Itai and Nir Sharon, Subdivision schemes for positive definite matrices, Found. Comput. Math. 13 (2013), no. 3, 347–369. MR 3047004, DOI 10.1007/s10208-012-9131-y
Shay Kels and Nira Dyn, Subdivision schemes of sets and the approximation of set-valued functions in the symmetric difference metric, Found. Comput. Math. 13 (2013), no. 5, 835–865. MR 3105947, DOI 10.1007/s10208-013-9146-z
R. Kimmel and J. A. Sethian, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci. USA 95 (1998), no. 15, 8431–8435. MR 1639135, DOI 10.1073/pnas.95.15.8431
J. M. Lane and R. F. Riesenfeld, A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-2(1) (1980), 35–46.
Yongdo Lim and Miklós Pálfia, Approximations to the Karcher mean on Hadamard spaces via geometric power means, Forum Math. 27 (2015), no. 5, 2609–2635. MR 3393373, DOI 10.1515/forum-2013-0088
Valery Marenich, Geodesics in Heisenberg groups, Geom. Dedicata 66 (1997), no. 2, 175–185. MR 1458790, DOI 10.1023/A:1004916117293
Facundo Mémoli and Guillermo Sapiro, Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces, J. Comput. Phys. 173 (2001), no. 2, 730–764. MR 1866863, DOI 10.1006/jcph.2001.6910
Lyle Noakes, Nonlinear corner-cutting, Adv. Comput. Math. 8 (1998), no. 3, 165–177. MR 1628245, DOI 10.1023/A:1018940112654
Lyle Noakes, Accelerations of Riemannian quadratics, Proc. Amer. Math. Soc. 127 (1999), no. 6, 1827–1836. MR 1486744, DOI 10.1090/S0002-9939-99-04809-1
Inam Ur Rahman, Iddo Drori, Victoria C. Stodden, David L. Donoho, and Peter Schröder, Multiscale representations for manifold-valued data, Multiscale Model. Simul. 4 (2005), no. 4, 1201–1232. MR 2203850, DOI 10.1137/050622729
S. Schaefer and R. Goldman, Non-uniform subdivision for B-splines of arbitrary degree, Comput. Aided Geom. Design 26 (2009), no. 1, 75–81. MR 2484438, DOI 10.1016/j.cagd.2007.12.005
S. Schaefer, E. Vouga, and R. Goldman, Nonlinear subdivision through nonlinear averaging, Comput. Aided Geom. Design 25 (2008), no. 3, 162–180. MR 2389938, DOI 10.1016/j.cagd.2007.07.003
Nir Sharon and Uri Itai, Approximation schemes for functions of positive-definite matrix values, IMA J. Numer. Anal. 33 (2013), no. 4, 1436–1468. MR 3119723, DOI 10.1093/imanum/drs049
John Stillwell, Naive Lie theory, Undergraduate Texts in Mathematics, Springer, New York, 2008. MR 2431402, DOI 10.1007/978-0-387-78214-0
J. Wallner, E. Nava Yazdani, and P. Grohs, Smoothness properties of Lie group subdivision schemes, Multiscale Model. Simul. 6 (2007), no. 2, 493–505. MR 2338492, DOI 10.1137/060668353
J. Wallner, On convergent interpolatory subdivision schemes in Riemannian geometry.
Johannes Wallner and Nira Dyn, Convergence and $C^1$ analysis of subdivision schemes on manifolds by proximity, Comput. Aided Geom. Design 22 (2005), no. 7, 593–622. MR 2169051, DOI 10.1016/j.cagd.2005.06.003
Gang Xie and Thomas P.-Y. Yu, Smoothness equivalence properties of interpolatory Lie group subdivision schemes, IMA J. Numer. Anal. 30 (2010), no. 3, 731–750. MR 2670112, DOI 10.1093/imanum/drn065
Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften : a series of comprehensive studies in mathematics, vol. 319, Springer, 1999.
Thomas J Cashman, Kai Hormann, and Ulrich Reif, Generalized Lane–Riesenfeld algorithms, Computer Aided Geometric Design 30 (2013), no. 4, 398–409.
George M. Chaikin, An algorithm for high-speed curve generation., Comput. Graph. Image Process 3 (1974), 346–349.
Keenan Crane, Clarisse Weischedel, and Max Wardetzky, Geodesics in heat: A new approach to computing distance based on heat flow, ACM Transactions on Graphics (TOG) 32 (2013), no. 5, 152.
Gilles Deslauriers and Serge Dubuc, Symmetric iterative interpolation processes, Constr. Approx. 5 (1989), no. 1, 49–68. Fractal approximation. MR 982724, DOI 10.1007/BF01889598
Manfredo P. DoCarmo, Riemannian geometry, Springer, 1992.
N. Dyn, Subdivision schemes in computer-aided geometric design, Advances in numerical analysis, Vol. II (Lancaster, 1990) Oxford Sci. Publ., Oxford Univ. Press, New York, 1992, pp. 36–104. MR 1172120
Nira Dyn, Three families of nonlinear subdivision schemes, Studies in Computational Mathematics 12 (2006), 23–38.
Nira Dyn and Elza Farkhi, Spline subdivision schemes for compact sets with metric averages, Trends in approximation theory, 2001, pp. 1–10.
Nira Dyn and Ron Goldman, Convergence and smoothness of nonlinear Lane–Riesenfeld algorithms in the functional setting, Foundations of Computational Mathematics 11 (2011), no. 1, 79–94.
Nira Dyn, David Levin, and John A. Gregory, A $4$-point interpolatory subdivision scheme for curve design, Comput. Aided Geom. Design 4 (1987), no. 4, 257–268. MR 937365, DOI 10.1016/0167-8396(87)90001-X
Nira Dyn and Nir Sharon, The convergence of manifold-valued subdivision schemes based on geodesic averaging. In prepration. Available at http://arxiv.org/abs/1407.8361.
Oliver Ebner, Convergence of refinement schemes on metric spaces, Proceedings of the American Mathematical Society 141 (2013), no. 2, 677–686.
Abbas M Faridi and EL Schucking, Geodesics and deformed spheres, Proceedings of the American Mathematical Society (1987), 522–525.
Svatopluk Fucik and Alois Kufner, Nonlinear differential equations, New York (1980).
Daniel Genin, Boris Khesin, and Serge Tabachnikov, Geodesics on an ellipsoid in minkowski space, Enseign.Math. (2) 53 (2007), 307–331.
Philipp Grohs and Johannes Wallner, Definability and stability of multiscale decompositions for manifold-valued data, Journal of the Franklin Institute 349 (2012), no. 5, 1648–1664.
Fumio Hiai and Dénes Petz, Riemannian metrics on positive definite matrices related to means, Linear Algebra Appl. 430 (2009), no. 11-12, 3105–3130. MR 2517863, DOI 10.1016/j.laa.2009.01.025
Arieh Iserles, Hans Z Munthe-Kaas, Syvert P Nørsett, and Antonella Zanna, Lie-group methods, Acta Numerica 2000 9 (2000), no. 1, 215–365.
Uri Itai and Nir Sharon, Subdivision schemes for positive definite matrices, Foundations of Computational Mathematics 13 (2013), no. 3, 347–369.
Shay Kels and Nira Dyn, Subdivision schemes of sets and the approximation of set-valued functions in the symmetric difference metric, Foundations of Computational Mathematics 13 (2013), no. 5, 835–865.
Ron Kimmel and James A Sethian, Computing geodesic paths on manifolds, Proceedings of the National Academy of Sciences 95 (1998), no. 15, 8431–8435.
Jeffrey M. Lane and Richard F. Riesenfeld, A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-2 (1980), no. 1, 35–46.
Yongdo Lim and Miklós Pálfia, Approximations to the karcher mean on hadamard spaces via geometric power means, Forum mathematicum, 2013.
Valery Marenich, Geodesics in heisenberg groups, Geometriae Dedicata 66 (1997), no. 2, 175–185.
Facundo Mémoli and Guillermo Sapiro, Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces, Journal of computational Physics 173 (2001), no. 2, 730–764.
Lyle Noakes, Nonlinear corner-cutting, Advances in Computational Mathematics 8 (1998), no. 3, 165–177.
Lyle Noakes, Accelerations of Riemannian quadratics, Proceedings of the American Mathematical Society 127 (1999), no. 6, 1827–1836.
Inam Ur Rahman, Iddo Drori, Victoria C. Stodden, David L. Donoho, and Peter Schröder, Multiscale representations for manifold-valued data, Multiscale Model. Simul. 4 (2005), no. 4, 1201–1232. MR 2203850, DOI 10.1137/050622729
Scott Schaefer and Ron Goldman, Non-uniform subdivision for b-splines of arbitrary degree, Computer Aided Geometric Design 26 (2009), no. 1, 75–81.
S. Schaefer, E. Vouga, and R. Goldman, Nonlinear subdivision through nonlinear averaging, Comput. Aided Geom. Design 25 (2008), no. 3, 162–180. MR 2389938, DOI 10.1016/j.cagd.2007.07.003
Nir Sharon and Uri Itai, Approximation schemes for functions of positive-definite matrix values, IMA Journal of Numerical Analysis 33 (2013), no. 4, 1436–1468.
John Stillwell, Naive Lie theory, Undergraduate Texts in Mathematics, Springer, New York, 2008. MR 2431402, DOI 10.1007/978-0-387-78214-0
J. Wallner, E. Nava Yazdani, and P. Grohs, Smoothness properties of Lie group subdivision schemes, Multiscale Model. Simul. 6 (2007), no. 2, 493–505. MR 2338492, DOI 10.1137/060668353
Johannes Wallner, On convergent interpolatory subdivision schemes in Riemannian geometry.
Johannes Wallner and Nira Dyn, Convergence and $C^1$ analysis of subdivision schemes on manifolds by proximity, Comput. Aided Geom. Design 22 (2005), no. 7, 593–622. MR 2169051, DOI 10.1016/j.cagd.2005.06.003
Gang Xie and Thomas P.-Y. Yu, Smoothness equivalence properties of interpolatory Lie group subdivision schemes, IMA J. Numer. Anal. 30 (2010), no. 3, 731–750. MR 2670112, DOI 10.1093/imanum/drn065