A Greedy Randomized Progressive and Iterative Approximation Method for Least Squares Fitting

Abstract

In this paper, we develop a novel greedy randomized progressive and iterative approximation method for least square fitting (GRLSPIA). By introducing a simpler greedy criterion, the GRLSPIA method adjusts the control points randomly and generates a sequence of curves and surfaces. The limit curve and surface converge to the unique least-norm fitting result in expectation. And the convergence rate of the GRLSPIA method can be smaller with the appropriate parameter. Numerical experiments verify its convergence and show its benefits.

Keywords

The GRLSPIA method / Convergence / In expectation / Least square fitting / 65D10 / 65D17 / 41A15

References

[1] Bai Z-Z, Wu W-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 40(1): A592-A606

[2] Bai Z-Z, Wu W-T. On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl., 2019, 26(4 e2237

[3] Carnicer JM, García-Esnaola M, Peña JM. Convexity of rational curves and total positivity. J. Comput. Appl. Math., 1996, 71(2): 365-382

[4] Cheng, F., Fan, F., Huang, C., et al.: Smooth surface reconstruction using Doo-Sabin subdivision surfaces. In: Proceedings of 3rd International Conference on Geometric Modeling and Imaging. Los Alamitos: IEEE Compute Society Press, 27-33 (2008)

[5] Cheng F, Fan F, Lai S, et al.. Loop subdivision surface based progressive interpolation. J. Comput. Sci. Technol., 2009, 24(1): 39-46

[6] Chen Z, Luo X, Tan L, et al.. Progressive interpolation based on Catmull-Clark subdivision surfaces. Comput. Graph. Forum, 2008, 27(7): 1823-1827

[7] Chen J, Wang G. Progressive-iterative approximation for triangular Bézier surfaces. Comput. Aided Des., 2011, 43(8): 889-895

[8] de Boor, C.: How does Agee’s smoothing method work? Proceedings of the 1979 Army Numerical Analysis and Computers Conference, ARO Report 79-3, 299-302 (1979)

[9] Delgado J, Pena JM. Progressive iterative approximation and bases with the fastest convergence rates. Comput. Aided Geom. Des., 2007, 24(1): 10-18

[10] Deng C, Lin H. Progressive and iterative approximation for least squares B-spline curve and surface fitting. Comput. Aided Des., 2014, 47: 32-44

[11] Deng C, Ma W. Weighted progressive interpolation of Loop subdivision surfaces. Comput. Aided Des., 2012, 44(5): 424-431

[12] Deng C, Yang X. A simple method for interpolating meshes of arbitrary topology by Catmull-Clark surfaces. Vis. Comput., 2010, 26(2): 137-146

[13] Du K, Si W-T, Sun X-H. Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput., 2020, 42(6): A3541-A3559

[14] Ebrahimi A, Loghmani GB. A composite iterative procedure with fast convergence rate for the progressive-iteration approximation of curves. J. Comput. Appl. Math., 2020, 359: 1-15

[15] Hamza YF, Lin H, Li Z. Implicit progressive-iterative approximation for curve and surface reconstruction. Comput. Aided Geom. Des., 2020, 77 101817

[16] Huang Z-D, Wang H. On progressive and iterative approximation method with memory for least square fitting. Comput. Aided Geom. Des., 2020, 82 101931

[17] Jiang Y, Lin H, Huang W. Fairing-PIA: progressive-iterative approximation for fairing curve and surface generation. Vis. Comput., 2024, 40: 1467-1484

[18] Lin H. Local progressive-iterative approximation format for blending curves and patches. Comput. Aided Geom. Des., 2010, 27(4): 322-339

[19] Lin H. The convergence of the geometric interpolation algorithm. Comput. Aided Des., 2010, 42(6): 505-508

[20] Lin H, Bao H, Wang G. Totally positive bases and progressive iteration approximation. Comput. Math. Appl., 2005, 50: 575-586

[21] Lin H, Maekawa T, Deng C. Survey on geometric iterative methods and their applications. Comput. Aided Des., 2018, 95: 40-51

[22] Lin H, Wang G, Dong C. Constructing iterative non-uniform B-spline curve and surface to fit data points. Sci. China Series Inf. Sci., 2004, 47(3): 315-331

[23] Lin H, Zhang Z. An extended iterative format for the progressive iteration approximation. Comput. Graph., 2011, 35(5): 967-975

[24] Lin H, Zhang Z. An efficient method for fitting large data sets using T-splines. SIAM J. Sci. Comput., 2013, 35(6): 3052-3068

[25] Liu C, Han X, Li C. Preconditioned progressive iterative approximation for triangular Bézier patches and its application. J. Comput. Appl. Math., 2020, 366 112389

[26] Liu M, Li B, Guo Q, et al.. Progressive iterative approximation for regularized least square bivariate B-spline surface fitting. J. Comput. Appl. Math., 2018, 327: 175-187

[27] Li S, Xu H, Deng C. Data-weighted least square progressive and iterative approximation and related B-spline curve fitting. J. Comput. Aided Des. Comput. Graph., 2019, 31(9): 1574-1580

[28] Lu L. Weighted progressive iteration approximation and convergence analysis. Comput. Aided Geom. Des., 2010, 27(2): 129-137

[29] Lu L, Zhao S. High-quality point sampling for B-spline fitting of parametric curves with feature recognition. J. Comput. Appl. Math., 2019, 345: 286-294

[30] Maekawa T, Matsumoto Y, Namiki K. Interpolation by geometric algorithm. Comput. Aided Des., 2007, 39(4): 313-323

[31] Necoara I. Faster randomized block Kaczmarz algorithms. SIAM J. Matrix Anal. Appl., 2019, 40(4): 1425-1452

[32] Qi D, Tian Z, Zheng Y, Feng J. The method of numeric Polish in curve fitting. Acta Math. Sin., 1975, 18(3): 173-184

[33] Rios D, Jüttler B. LSPIA, (stochastic) gradient descent, and parameter correction. J. Comput. Appl. Math., 2022, 406 113921

[34] Shi L, Wang R. An iterative algorithm of NURBS interpolation and approximation. J. Math. Res. Expo., 2006, 26(4): 735-743

[35] Wang H. On extended progressive and iterative approximation for least square fitting. Vis. Comput., 2021, 38(2): 591-602

[36] Wu N-C, Liu C-Z. Randomized progressive iterative approximation for B-spline curve and surface fittings. Appl. Math. Comput., 2024, 473 128699

[37] Xie J, Xu JL, Dong ZY, et al.. Interpolatory Catmull-Clark volumetric subdivision over unstructured hexahedral meshes for modeling and simulation applications. Comput. Aided Geom. Des., 2020, 80 101867

[38] Xiong Y, Li G, Mao A. Convergence analysis for B-spline geometric interpolation. Comput. Graph., 2012, 36(7): 884-891

[39] Zhang L, Ge X, Tan J. Least square geometric iterative fitting method for generalized B-spline curves with two different kinds of weights. Vis. Comput., 2016, 32: 1109-1120

[40] Zhang M, Li Y, Deng C. Optimizing NURBS curves fitting by least squares progressive and iterative approximation. J. Comput. Aided Des. Comput. Graph., 2020, 32(4): 568-574

[41] Zhang L, Tan J, Ge X, Zheng G. Generalized B-splines’ geometric iterative fitting method with mutually different weights. J. Comput. Appl. Math., 2018, 329: 331-343

Funding

National Natural Science Foundation of China(12401501)

Rights & permissions

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.