×

Nonlinear least-squares spline fitting with variable knots. (English) Zbl 1429.65130

Summary: In this paper, we present a nonlinear least-squares fitting algorithm using B-splines with free knots. Since its performance strongly depends on the initial estimation of the free parameters (i.e., the knots), we also propose a fast and efficient knot-prediction algorithm that utilizes numerical properties of first-order B-splines. Using \(\ell_p\) (\(p = 1, 2, \infty\)) norm solutions, we also provide three different strategies for properly selecting the free knots. Our initial predictions are then iteratively refined by means of a gradient-based variable projection optimization. Our method is general in nature and can be used to estimate the optimal number of knots in cases in which no a priori information is available. To evaluate the performance of our method, we approximated a one-dimensional discrete time series and conducted an extensive comparative study using both synthetic and real-world data. We chose the problem of electrocardiogram (ECG) signal compression as a real-world case study. Our experiments on the well-known PhysioNet MIT-BIH Arrhythmia database show that the proposed method outperforms other knot-prediction techniques in terms of accuracy while requiring much lower computational complexity.

MSC:

65K10 Numerical optimization and variational techniques
65D07 Numerical computation using splines
65D10 Numerical smoothing, curve fitting
90C59 Approximation methods and heuristics in mathematical programming
92C55 Biomedical imaging and signal processing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Scolnik, H. D., On the solution of linear and non-linear least squares problems, Proceedings of the IFIP Congress, 71, 1258-1265 (1972), North Holland: North Holland Amsterdam
[2] Guttman, I.; Pereyra, V.; Scolnik, H. D., Least squares estimation for a class of non-linear models, Technometrics, 15, 2, 209-218 (1973) · Zbl 0263.65011
[3] Lawton, W. H.; Sylvestre, E. A., Estimation of linear parameters in nonlinear regression, Technometrics, 13, 3, 461-467 (1971) · Zbl 0219.62014
[4] Golub, G. H.; Pereyra, V., The differentiation of pseudo-inverses and nonlinear least squares problems whosevariables separate, SIAM J. Numer. Anal., 10, 2, 413-432 (1973) · Zbl 0258.65045
[5] Golub, G. H.; Pereyra, V., Separable nonlinear least squares: the variable projection method and its applications, Inverse Prob., 19, 2, R1-R26 (2003) · Zbl 1022.65014
[6] Chung, J.; Nagy, J. G., An efficient iterative approach for large-scale separable nonlinear inverse problems, SIAM J. Scient. Comput., 31, 6, 4654-4674 (2010) · Zbl 1205.65160
[7] Cornelio, A.; Piccolomini, E. L.; Nagy, J. G., Constrained numerical optimization methods for blind deconvolution, Numer. Algor., 65, 1, 23-42 (2014) · Zbl 1281.65066
[8] O’Leary, D. P.; Rust, B. W., Variable Projection for Nonlinear Least Squares Problems, Comput. Optim. Appl., 54, 3, 579-593 (2013) · Zbl 1271.90055
[9] Jupp, D. L.B., Approximation to data by splines with free knots, SIAM J. Numer. Anal., 15, 2, 328-343 (1978) · Zbl 0403.65004
[10] (Dierckx, P., Curve and Surface Fitting with Splines (1993), Oxford University Press: Oxford University Press Oxford) · Zbl 0782.41016
[11] (Guertin, M. C., Sur Les Splines De rgression Noeuds Variables (1992), Mmoire Matrise es Sciences: Mmoire Matrise es Sciences Universit de Montral)
[12] Lindstrom, M. J., Penalized estimation of free-knot splines, J. Comput. Graph. Stat., 8, 333-352 (1999)
[13] Molinari, N.; Durand, J.-F.; Sabatier, R., Bounded optimal knots for regression splines, Comput. Stat. Data Anal., 45, 2, 159-178 (2004) · Zbl 1429.62131
[14] Beliakov, G., Least squares splines with free knots: global optimization approach, Appl. Math. Comput., 149, 783-798 (2004) · Zbl 1038.65051
[15] Borges, C. F.; Pastva, T., Total least squares fitting of Bézier and B-spline curves to ordered data, Comput. Aided Geomet. Des., 19, 4, 275-289 (2002) · Zbl 0995.68137
[16] Yoshimoto, F.; Harada, T.; Yoshimoto, Y., Data fitting with a spline using a real-coded genetic algorithm, Comput. Aided Des., 35 (2003)
[17] Karczewicz, M.; Gabbouj, M., ECG data compression by spline approximation, Signal Process., 59, 43-59 (1997) · Zbl 1005.94525
[18] Curry, H. B.; Schoenberg, I. J., On Pólya frequency functions IV: The fundamental spline functions and their limits, J. Anal. Math., 17, 71-107 (1966) · Zbl 0146.08404
[19] Schoenberg, I. J.; Whitney, A., On Pólya frequency functions III: The positivity of translation determinants with an application to the interpolation problem by spline curves, Trans. Am. Math. Soc., 74, 246-259 (1953) · Zbl 0051.33606
[20] Jupp, D. L.B., The Lethargy Theorem - A Property of Approximation by \(γ\)-Polynomials, J. Approx. Theory, 14, 204-217 (1975) · Zbl 0305.41004
[21] Cadzow, J. A., Minimum \(ℓ_1, ℓ_2\) and \(ℓ_∞\) norm approximate solutions to an overdetermined system of linear equations, Digital Signal Process., 12, 524-560 (2002)
[22] Hegedűs, J. C., The method IRLS for some best \(ℓ_p\) norm solutions of under- or overdetermined linear systems, Ann. Univ. Sci. Budapest, Sect. Comp., 45, 303-317 (2016) · Zbl 1413.65117
[23] Natanson (Ed.), I. P., Constructive Function Theory, I-III. (1964-1965), Frederick Ungar Publishing: Frederick Ungar Publishing New York, USA · Zbl 0178.39701
[24] (Watson, G. A., Approximation Theory and Numerical Methods (1980), John Wiley & Sons: John Wiley & Sons New York, USA) · Zbl 0442.65005
[25] (Stewart, G. W., Afternotes Goes to Graduate School: Lectures on Advanced Numerical Analysis (1998), SIAM: SIAM PA, USA) · Zbl 0898.65001
[26] Kaufman, L., A variable projection method for solving seperable nonlinear least squares problems, BIT, 15, 49-57 (1975) · Zbl 0307.65019
[27] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B. (Methodol.), 58 (1996) · Zbl 0850.62538
[28] Uyar, K.; Ülker, E., B-spline curve fitting with invasive weed optimization, Appl. Math. Model., 52 (2017) · Zbl 1480.65039
[29] Goldberger, A. L.; Amaral, L. A.N.; Glass, L.; Hausdorff, J. M.; Ivanov, P. C.; Mark, R. G.; Mietus, J. E.; Moody, G. B.; Peng, C. K.; Stanley, H. E., PhysioBank, PhysioToolkit, and PhysioNet: Components of a new research resource for complex physiologic signals, Circulation, 101, 23, 215-220 (2000)
[30] de Chazal, P.; O’Dwyer, M.; Reilly, R. B., Automatic classification of heartbeats using ecg morphology and heartbeat interval features, IEEE Trans. Biomed. Eng., 51, 7, 1196-1206 (2004)
[31] Yuan, Y.; Chen, N.; Zhou, S., Adaptive B-spline knot selection using multi-resolution basis set, IIE (Inst. Ind. Eng.) Trans., 45 (2013)
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.