×

zbMATH — the first resource for mathematics

A review of the parameter estimation problem of fitting positive exponential sums to empirical data. (English) Zbl 1023.65009
Summary: Exponential sum models are used frequently: in heat diffusion, diffusion of chemical compounds, time series in medicine, economics, physical sciences and technology. Thus it is important to find good methods for the estimation of parameters in exponential sums.
In this paper we review and discuss results from the last forty years of research. There are many different ways of estimating parameters in exponential sums and model of fit criterion, which gives a valid result from the fit. We find that a good choice is a weighted two-norm objective function, with weights based on the maximum likelihood (ML) criterion. If the number of exponential terms is unknown, statistical methods based on an information criterion or cross-validation can be used to determine the optimal number.
It is suitable to use hybrid Gauss-Newton and quasi-Newton algorithm to find the unknown parameters in the constrained weighted nonlinear least-squares problem formulated using an maximal likelihood objective function. The problem is highly ill conditioned and it is crucial to find good starting values for the parameters. To find the initial parameter values, a modified Prony method or a method based upon rewriting partial sums as geometrical sums is proposed.

MSC:
65D10 Numerical smoothing, curve fitting
65C60 Computational problems in statistics (MSC2010)
62F10 Point estimation
11L03 Trigonometric and exponential sums, general
11Y60 Evaluation of number-theoretic constants
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agha, M., A direct method for Fitting linear combinations of exponentials, Biometrics, 27, 399-413, (1971)
[2] Akaike, H., Fitting autoregressive models for prediction, Ann. inst. stat. math., 20, 425-439, (1969)
[3] H. Akaike, Information theory and an extension of the maximum likelihood principle, in: B.N. Petrov, F. Csaki, (Eds.), Proceedings from Second International Symposium on Information Theory, Budapest, Supp. to Problems of Control and Information Theory, 1972, pp. 267-281
[4] Akaike, H., A new look at the statistical model identification, IEEE trans. autom. control, AC-19, 6, 716-723, (1974) · Zbl 0314.62039
[5] Akhiezer, N.L., The classical moment problem and some related questions in analysis, (1965), Oliver and Boyd Edinburgh · Zbl 0135.33803
[6] Al-Baali, M.; Fletcher, R., Variational methods for nonlinear least squares, J. oper. res. soc., 36, 405-421, (1985) · Zbl 0578.65064
[7] Ammar, G.; Dayawansa, W.; Martin, C., Exponential interpolation: theory and numerical algorithms, Appl. math. comput., 41, 189-232, (1991) · Zbl 0716.65001
[8] Avrett, E.; Hummer, D., Mon. notic. roy. astron. soc., 130, 865, (1965)
[9] M. Bertero, P. Boccacci, E.R. Pike, On the recovery and resolution of exponential relaxation rates from experimental data ii – the optimum choice of experimental sampling points for Laplace transform inversion, Proc. Roy. Soc. 393 (51) (1984) · Zbl 0541.65094
[10] Bertero, M.; Brianzi, P.; Pike, E.R., On the recovery and resolution of exponential relaxation rates from experimental data: Laplace transform inversions in weighted spaces, Inverse problems, 1, 1-15, (1985) · Zbl 0603.44001
[11] Braess, D., On the nonuniqueness of monosplines with least L2-norm, J. approximation theory, 12, 1, 91-93, (1974) · Zbl 0288.41003
[12] Braess, D., On rational Lp-approximation, J. approximation theory, 18, 2, 136-151, (1976) · Zbl 0335.41008
[13] Braess, D., Chebyshev approximation by γ-polynomials. III on the number of best approximations, J. approximation theory, 24, 2, 119-145, (1978) · Zbl 0399.41019
[14] D. Braess, Global analysis and nonlinear approximation and its application to exponential approximation. 2. Applications to exponential approximation, in: Z. Ziegler, Approximation Theory and Applications, Academic Press Technicon, Haifa, Israel, 1981, pp. 39-63
[15] D. Braess, Global analysis in nonlinear approximation and its application to exponential approximation. 1. The uniqueness theorem for Haar-Embedded manifolds, in: Z. Ziegler, Approximation Theory and Applications, Academic Press Technicon, Haifa, Israel, 1981, pp. 23-37
[16] R. Brockett, The geometry of the partial realization problem, in: Proceedings of the1978 IEEE Conference on Decision and control, 1978, pp. 1048-1052
[17] Burstein, J., Approximations by exponentials, their extensions and differential equations, (1997), Metric Press Boston, MA
[18] Cantor, D.G.; Evans, J.W., On approximation by positive sums of powers, SIAM J. appl. math., 18, 2, 380-388, (1970) · Zbl 0219.41006
[19] Coleman, T.F.; Plassmann, P.E., Solution of nonlinear least-squares problems on a multiprocessor, (), 44-60
[20] Coleman, T.F.; Plassmann, P.E., A parallel nonlinear least-squares solver: theoretical analysis and numerical results, SIAM J. sci. statist. comput., 13, 3, 771-793, (1992) · Zbl 0761.65047
[21] R.G. Cornell, A method for fitting linear combinations of exponentials, Biometrics (1962) 104-113 · Zbl 0107.14202
[22] Cromme, L., Eine klasse von verfahren zur ermittlung bester nichtlinearer tschebyscheff-approximationen, Numerische Mathematik, 25, 447-459, (1976) · Zbl 0333.65005
[23] Cromme, L., Strong uniqueness – a far-reaching criterion for the convergence analysis of iterative procedures, Numerische Mathematik, 29, 179-193, (1978) · Zbl 0352.65012
[24] L. Cromme, A unified approach to differential characterizations of local best approximations for exponential sums and splines, Technical Report, Lehrstühle für Numerische und Angewandte Mathematik, Universität Göttingen, University of Berkeley, CA, May 1981 · Zbl 0504.41030
[25] Cromme, L.J., Regular C1-parametrizations for exponential sums and splines, J. approximation theory, 35, 1, 30-44, (1982) · Zbl 0486.41017
[26] Della Corte, M.; Buricchi, L.; Romano, S., On the Fitting of linear combinations of exponentials, Biometrics, 30, 367-369, (1974) · Zbl 0286.62048
[27] Dennis, J.E.; Schnabel, R.B., Numerical methods for unconstrained optimization and nonlinear equations, (1983), Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[28] Dennis Jr, J.E.; Gay, D.M.; Welch, R.E., An adaptive nonlinear least-squares algorithm, ACM trans. math. software, 7, 3, 348-368, (1981) · Zbl 0464.65040
[29] Duncan, G.T., An empirical study of jackknife-constructed confidence regions in nonlinear regression, Technometrics, 20, 2, 123-129, (1978) · Zbl 0394.62048
[30] Evans, J.W.; Gragg, W.B.; LeVeque, R.J., On least-squares exponential sum approximation with positive coefficients, Math. comput., 34, 149, 203-211, (1980) · Zbl 0424.65002
[31] Fletcher, R.; Xu, C., Hybrid methods for nonlinear least squares, IMA J. numer. anal., 7, 371-389, (1987) · Zbl 0648.65051
[32] Fletcher, R., Practical methods of optimization, (1987), Wiley New York · Zbl 0905.65002
[33] Gragg, W.; Lindquist, A., On the partial realization problem, Linear algebra appl., 50, 277-319, (1983) · Zbl 0519.93024
[34] Guddat, J.; Jongen, H.Th., Structural stability in nonlinear optimization, Optimization, 18, 617-631, (1987) · Zbl 0638.90093
[35] Gustafson, S.-Å., A computational scheme for exponential approximation, Z. angew. math. mech., 61, 284-287, (1981)
[36] Hilebrand, F., Introduction to numerical analysis, (1956), McGraw-Hill New York
[37] K. Holmström, NLPLIB TB 1.0 - A MATLAB toolbox for nonlinear optimization and parameter estimation, Technical Report IMa-TOM-1997-02, Department of Mathematics and Physics, Mälardalen University, Sweden, 1997
[38] K. Holmström, The NLPLIB toolbox for nonlinear programming, in: MATLAB, Advanced Modeling and Optimization 1 (1999) 70-86 · Zbl 1115.90302
[39] K. Holmström, The TOMLAB optimization environment in MATLAB, Advanced Modeling and Optimization 1 (1999) 47-69
[40] K. Holmström, A. Ahnesjö, J. Petersson, Algorithms for exponential sum fitting in radiotherapy planning, Advanced Modeling and Optimization 3 (2001)
[41] Hunt, G.; Grant, I., J. atmos. sci., 26, 963, (1969)
[42] Huschens, J., On the use of product structure in secant methods for nonlinear least-squares problems, SIAM J. opt., 4, 1, 108-129, (1994) · Zbl 0798.65064
[43] Jennrich, R.I.; Bright, P.B., Fitting systems of linear differential equations using computer generated exact derivatives, Technometrics, 18, 4, 385-392, (1976) · Zbl 0342.62066
[44] Jongen, H.Th.; Weber, G.-W., Nonlinear optimization, characterization of structural stability, J. global opt., 1, 1, 47-64, (1991) · Zbl 0745.90067
[45] Kahn, M.; Mackisack, M.S.; Osborne, M.R.; Smyth, G.K., On the consistency of Prony’s method and related algorithms, J. comput. graphical statist., 1, 329-349, (1992)
[46] T. Kaijser, A simple inversion method for determining aerosol size distributions, Technical Report C 30231-E, FOA, Huvudavdelning 3, 581 11 Linköping, September 1981 · Zbl 0513.65090
[47] Kammler, D.W., Least squares approximation of completely monotonic functions by sums of exponentials, SIAM J. numer. anal., 16, 801-818, (1979) · Zbl 0444.41012
[48] Kirkegaard, P.; Eldrup, M., POSITRONFIT: a versatile program for analysing positron lifetime spectra, Comput. phys. comm., 3, 240-255, (1972)
[49] Kirkegaard, P.; Eldrup, M., POSITRONFIT extended: a new version of a program for analysing positron lifetime spectra, Comput. phys. comm., 7, 401-409, (1974)
[50] Kojima, M., Strongly stable stationary solutions in nonlinear programs, () · Zbl 0478.90062
[51] S.Y. Kung, Multivariable and multidimensional systems: analysis and design, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, CA, June 1977
[52] P. Lindström and P. Wedin, Methods and software for nonlinear least-squares problems, Technical Report UMINF-133.87, Inst. of Information Processing, University of Umeå, Sweden, 1988
[53] Ljung, L., System identification: theory for the user, (1987), Prentice-Hall Englewood Cliffs, NJ · Zbl 0615.93004
[54] Mackisack, M.S.; Osborne, M.R.; Smyth, G.K., A modified prony algorithm for estimating sinusoidal frequencies, J. statist. comput. simulation, 49, 111-124, (1994) · Zbl 0833.62087
[55] L. Marple, Spectral line analysis by Pisarenko and Prony methods, Technical Report CH1379-7/79/0000-0159, Advent systems INC, 1183 Bourdeaux Dr. Sunnyvale, CA 94086, 1979
[56] Martin, C.; Smith, J., Approximation, interpolation and sampling, Contemp. math., 68, 227-252, (1987)
[57] M. Nakamura, T. Takahashi, Inversion of the chi-square transform, 1978 (Translated paper from the original Japanese paper)
[58] Nakamura, M.; Takahashi, T.; Kodama, S., Parameter estimation of a linear combination of exponential decays by a method of the gamma transformation – a investigation, Trans. IECE jpn. E, 63, 6, 500-501, (1980)
[59] Nazareth, L., Some recent approaches to solving large residual nonlinear least-squares problems, SIAM, 22, 1, 1-11, (1980) · Zbl 0424.65031
[60] M.R. Osborne, A class of nonlinear regression problems, in: R.S. Anderssen, M.R. Osborne, (Eds.), Data Representation, University of Queensland Press, 1970, pp. 94-101
[61] Osborne, M.R., Some special nonlinear least-squares problems, SIAM J. numer. anal., 12, 4, 571-592, (1975) · Zbl 0322.65007
[62] Osborne, M.R., Nonlinear least squares – the Levenberg algorithm revisited, J. aust. math. soc. B, 19, 343-357, (1976) · Zbl 0364.90100
[63] M.R. Osborne, G.K. Smyth, An algorithm for exponential fitting revisited, in: J. Gani, M.B. Priestly, (Eds.), Essays in Time Series and Allied Processes: Papers in Honour of E. LJ. Hannan, Applied Probability Trust, Sheffield, 1986, pp. 419-430 · Zbl 0605.65008
[64] Osborne, M.R.; Smyth, G.K., A modified prony algorithm for Fitting functions defined by difference equations, SIAM J. sci. statist. comput., 12, 362-382, (1991) · Zbl 0723.65006
[65] Osborne, M.R.; Smyth, G.K., A modified prony algorithm for exponential function Fitting, SIAM J. sci. comput., 16, 1, 119-138, (1995) · Zbl 0812.62070
[66] J. Petersson, Algorithms for fitting two classes of exponential sums to empirical data, Licentiate Thesis, ISSN 1400-5468, Opuscula ISRN HEV-BIB-OP-35-SE, Division of Optimization and Systems Theory, Royal Institute of Technology, Stockholm, Mälardalen University, Sweden, 4 December 1998
[67] J. Petersson, K. Holmström, Fitting of exponential sums to empirical data, Technical Report IMa-TOM-1997-05, Department of Mathematics and Physics, Mälardalen University, Sweden, 1997, Presented at the 16th International Symposium on Mathematical Programming, Lausanne, Switzerland, 24-29 August 1997
[68] J. Petersson, K. Holmström, Identifying parameters and model order for two classes of exponential sum fitting problems, Technical Report IMa-TOM-1998-05, Department of Mathematics and Physics, Mälardalen University, Sweden, 1998
[69] J. Petersson, K. Holmström, Initial values for a class of exponential sum least-squares fitting problems, Technical Report IMa-TOM-1998-04, Department of Mathematics and Physics, Mälardalen University, Sweden, 1998
[70] J. Petersson, K. Holmström, Initial values for the exponential sum least-squares fitting problem, Technical Report IMa-TOM-1998-01, Department of Mathematics and Physics, Mälardalen University, Sweden, 1998
[71] J. Petersson, K. Holmström, Initial values for two classes of exponential sum least-squares fitting problems, Technical Report IMa-TOM-1998-07, Department of Mathematics and Physics, Mälardalen University, Sweden, 1998
[72] J. Petersson and K. Holmström, Methods for parameter estimation in exponential sums, in: A. Løkketangen, (Ed.), Proceedings from the Fifth Meeting of the Nordic Section of the Mathematical Programming Society, ISBN 82-90347-76-6, Molde, Division of Operations Research, Molde University, 1998
[73] Price, P.F., A comparison of the least-squares and maximum likelihood estimators for counts of radiation quanta which follow a Poisson distribution, Acta cryst. A, 35, 57-60, (1979)
[74] Raschke, E.; Stucke, U., Beitr. physik atmos., 46, 203, (1973)
[75] Rissanen, J., Recursive identification of linear sequences, SIAM J. control, 9, 420-430, (1971) · Zbl 0204.46202
[76] Rissanen, J., Modelling by shortest data description, Automatica, 14, 465-471, (1978) · Zbl 0418.93079
[77] A. Ruhe, Least-squares fitting by positive sums of exponentials, Technical Report UMINF-70.78, Inst. of Information Processing, University of Umeå, Sweden, 1978, Revised 29 February 1980
[78] Ruhe, A., Fitting empirical data by positive sums of exponentials, SIAM J. sci. statist. comput., 1, 4, 481-498, (1980) · Zbl 0455.65009
[79] A. Ruhe, Fitting empirical data by positive sums of exponentials, Compstat (1980) 622-628 · Zbl 0438.65022
[80] Ruhe, A.; Wedin, P., Algorithms for separable nonlinear least-squares problems, SIAM rev., 22, 318-337, (1980) · Zbl 0466.65039
[81] Shah, B.K., Obtaining preliminary estimates to fit two-term exponential model to blood concentration data, J. pharm. sci., 62, 1208-1209, (1973)
[82] Shapiro, R., Information loss and compensation in linear interpolation, J. comput. phys., 10, 65-84, (1972)
[83] Shapiro, R.; Smoothing, Filtering and boundary effects, Ref. geophys. and space phys., 8, 359-387, (1972)
[84] Smith, M.R.; Cohn-Sfetcu, S.; Buckmaster, H.A., Decomposition of multicomponent exponential decays by spectral analytic techniques, Technometrics, 18, 4, 467-482, (1976) · Zbl 0342.62061
[85] G.K. Smyth, Coupled and separable iterations in nonlinear estimation, Ph.D. Thesis, Canberra, Australian National University, 1985
[86] H.S. Steyn, Fitting linear combinations of exponential decays by using Fourier analysis, in: Compstat, Physica-Verlag, Vienna, 1980, pp. 615-621 · Zbl 0438.65021
[87] H.S. Steyn and J.W.J. van Wyk, Some methods for fitting compartment models to data, Technical Report, Wetenskaplike bydraes van die pu vir cho, Potchefstroomse Universiteit vir CHO, 1977
[88] Van den Bos, A., A class of small sample nonlinear least-squares problems, Automatica, 16, 487-490, (1980) · Zbl 0441.93041
[89] Varah, J.M., On Fitting exponentials by nonlinear least squares, SIAM J. sci. statist. comput., 6, 30-44, (1985) · Zbl 0561.65007
[90] Wiscombe, W.J.; Evans, J.W., Exponential – sum Fitting of radiative transmission functions, Comput. phys., 24, 4, 416-444, (1977)
[91] Yabe, H.; Takahashi, T., Factored quasi-Newton methods for nonlinear least-squares problems, Math. programming, 51, 1, 75-100, (1991) · Zbl 0737.90064
[92] Beale, E.M.L., Confidence regions in nonlinear estimation, J. roy. statist. soc. ser. B, 22, 41-76, (1960) · Zbl 0096.13201
[93] Meyer, R.R., The validity of a family of optimization methods, SIAM J. of control, 8, 41-54, (1970) · Zbl 0194.20501
[94] Mckcown, J.J., Specialized versus general purpose algorithms for minimizing functions that are sums of squared terms, Mathematical programming, 9, 57-60, (1975)
[95] Gardner, D.g.; Gardner, J.C.; Laush, G.; Meinke, W.W., Method for the analysis of muticomponent experimental decay curves, J. chem. phys., 31, 978-986, (1959)
[96] J.R. Rice, Minimization and techniques in nonlinear approximation, in: J.M. Ortega, W.C. Rheinboldt (Eds.), Studies in Numerical analysis2, Society for Industrial and Applied Mathemetics, Philadelphia, PA, 1970, pp. 80-89
[97] Holmström, K., New optimization algorithms and software, Theory of stochastic processes, 5, 21, 55-63, (1999) · Zbl 0947.90131
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.