Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A global approach to the refinement of manifold data


Authors: Nira Dyn and Nir Sharon
Journal: Math. Comp. 86 (2017), 375-395
MSC (2010): Primary 65D99, 40A99, 58E10
DOI: https://doi.org/10.1090/mcom/3087
Published electronically: April 13, 2016
MathSciNet review: 3557803
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

References References
  • 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 https://doi.org/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 https://doi.org/10.1016/0167-8396%2887%2990001-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 https://doi.org/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 https://doi.org/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 https://doi.org/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
  • 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1093/imanum/drn065

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D99, 40A99, 58E10

Retrieve articles in all journals with MSC (2010): 65D99, 40A99, 58E10


Additional Information

Nira Dyn
Affiliation: School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel
MR Author ID: 61245
Email: niradyn@post.tau.ac.il

Nir Sharon
Affiliation: School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel
MR Author ID: 974347
Email: Nir.Sharon@math.tau.ac.il

Keywords: Manifold data, geodesic average, convergence analysis
Received by editor(s): August 14, 2014
Published electronically: April 13, 2016
Article copyright: © Copyright 2016 American Mathematical Society