×

On the least-squares fitting of data by sinusoids. (English) Zbl 1357.62247

Pardalos, Panos M. (ed.) et al., Advances in stochastic and deterministic global optimization. Cham: Springer (ISBN 978-3-319-29973-0/hbk; 978-3-319-29975-4/ebook). Springer Optimization and Its Applications 107, 209-226 (2016).
Summary: The sinusoidal parameter estimation problem is considered to fit a sum of damped sinusoids to a series of noisy observations. It is formulated as a nonlinear least-squares global optimization problem. A one-parametric case study is examined to determine an unknown frequency of a signal. Univariate Lipschitz-based deterministic methods are used for solving such problems within a limited computational budget. It is shown that the usage of local information in these methods (such as local tuning on the objective function behavior and/or evaluating the function first derivatives) can significantly accelerate the search for the problem solution with a required guarantee. Results of a numerical comparison with metaheuristic techniques frequently used in engineering design are also reported and commented on.
For the entire collection see [Zbl 1359.90005].

MSC:

62J05 Linear regression; mixed models
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barkalov, K., Polovinkin, A., Meyerov, I., Sidorov, S., Zolotykh, N.: SVM regression parameters optimization using parallel global search algorithm. In: Parallel Computing Technologies. LNCS, vol. 7979, pp. 154–166. Springer, Heidelberg (2013) · Zbl 06274677 · doi:10.1007/978-3-642-39958-9_14
[2] Bloomfield, P.: Fourier Analysis of Time Series: An Introduction. Wiley, New York (2000) · Zbl 0994.62093 · doi:10.1002/0471722235
[3] Broomhead, D.S., King, G.P.: Extracting qualitative dynamics from experimental data. Phys. D Nonlinear Phenom. 20 (2–3), 217–236 (1986) · Zbl 0603.58040 · doi:10.1016/0167-2789(86)90031-X
[4] Calvin, J.M., Žilinskas, A.: One-dimensional global optimization for observations with noise. Comput. Math. Appl. 50 (1–2), 157–169 (2005) · Zbl 1127.90050 · doi:10.1016/j.camwa.2004.12.014
[5] Carnì, D.L., Fedele, G.: Multi-sine fitting algorithm enhancement for sinusoidal signal characterization. Comput. Stand. Interfaces 34 (6), 535–540 (2012) · doi:10.1016/j.csi.2011.03.003
[6] Costanzo, S.: Synthesis of multi-step coplanar waveguide-to-microstrip transition. Prog. Electromagn. Res. 113, 111–126 (2011) · doi:10.2528/PIER10112908
[7] Elsner, J.B., Tsonis, A.A.: Singular Spectrum Analysis: A New Tool in Time Series Analysis. Springer, New York (1996) · Zbl 0900.86003 · doi:10.1007/978-1-4757-2514-8
[8] Evtushenko, Y.G.: Numerical Optimization Techniques. Translations Series in Mathematics and Engineering. Springer, Berlin (1985) · doi:10.1007/978-1-4612-5022-7
[9] Fedele, G., Ferrise, A.: A frequency-locked-loop filter for biased multi-sinusoidal estimation. IEEE Trans. Signal Process. 62 (5), 1125–1134 (2014) · Zbl 1394.94181 · doi:10.1109/TSP.2014.2300057
[10] Garnier, H., Wang, L. (eds.): Identification of Continuous-Time Models from Sampled Data. Springer, London (2008)
[11] Gergel, V.P., Sergeyev, Y.D.: Sequential and parallel algorithms for global minimizing functions with Lipschitzian derivatives. Comput. Math. Appl. 37 (4–5), 163–179 (1999) · Zbl 0931.90049 · doi:10.1016/S0898-1221(99)00067-X
[12] Gergel, V.P., Grishagin, V.A., Gergel, A.V.: Adaptive nested optimization scheme for multidimensional global search. J. Glob. Optim. (2015, to appear). doi 10.1007/s10898-015-0355-7 · Zbl 1355.90072 · doi:10.1007/s10898-015-0355-7
[13] Gergel, V.P., Grishagin, V.A., Israfilov, R.A.: Local tuning in nested scheme of global optimization. Proc. Comput. Sci. 51, 865–874 (2015). (International Conference on Computational Science ICCS 2015 – Computational Science at the Gates of Nature) · doi:10.1016/j.procs.2015.05.216
[14] Gillard, J.W.: Cadzow’s basic algorithm, alternating projections and singular spectrum analysis. Stat. Interface 3 (3), 335–343 (2010) · Zbl 1245.62107 · doi:10.4310/SII.2010.v3.n3.a7
[15] Gillard, J.W., Kvasov, D.E.: Lipschitz optimization methods for fitting a sum of damped sinusoids to a series of observations. Stat. Interface (2016, to appear) · Zbl 1387.90196
[16] Gillard, J.W., Zhigljavsky, A.: Analysis of structured low rank approximation as an optimisation problem. Informatica 22 (4), 489–505 (2011) · Zbl 1274.90379
[17] Gillard, J.W., Zhigljavsky, A.: Optimization challenges in the structured low rank approximation problem. J. Glob. Optim. 57 (3), 733–751 (2013) · Zbl 1285.90040 · doi:10.1007/s10898-012-9962-8
[18] Gillard, J.W., Zhigljavsky, A.: Stochastic algorithms for solving structured low-rank matrix approximation problems. Commun. Nonlinear Sci. Numer. Simul. 21, 70–88 (2015) · Zbl 1336.65070 · doi:10.1016/j.cnsns.2014.08.023
[19] Golyandina, N., Nekrutkin, V., Zhigljavsky, A.: Analysis of Time Series Structure: SSA and Related Techniques. Chapman & Hall/CRC, Boca Raton (2001) · Zbl 0978.62073 · doi:10.1201/9781420035841
[20] Grishagin, V.A., Strongin, R.G.: Optimization of multi-extremal functions subject to monotonically unimodal constraints. Eng. Cybern. 22 (5), 117–122 (1984) · Zbl 0577.90071
[21] Grishagin, V.A., Sergeyev, Y.D., Strongin, R.G.: Parallel characteristic algorithms for solving problems of global optimization. J. Glob. Optim. 10 (2), 185–206 (1997) · Zbl 0880.90123 · doi:10.1023/A:1008242328176
[22] Holmström, K., Petersson, J.: A review of the parameter estimation problem of fitting positive exponential sums to empirical data. Appl. Math. Comput. 126 (1), 31–61 (2002) · Zbl 1023.65009
[23] Kvasov, D.E.: Diagonal numerical methods for solving Lipschitz global optimization problems. Boll. Unione Mat. Ital. I (Serie IX) (3), 857–871 (2008) · Zbl 1190.65097
[24] Kvasov, D.E., Mukhametzhanov, M.S.: One-dimensional global search: nature-inspired vs. Lipschitz methods. In: Proceedings of the ICNAAM2015 Conference, AIP Conference Proceedings. AIP Publishing LLC, New York (2015).
[25] Kvasov, D.E., Sergeyev, Y.D.: Univariate geometric Lipschitz global optimization algorithms. Numer. Algebra Control Optim. 2 (1), 69–90 (2012) · Zbl 1246.90124 · doi:10.3934/naco.2012.2.69
[26] Kvasov, D.E., Sergeyev, Y.D.: Lipschitz global optimization methods in control problems. Autom. Remote Control 74 (9), 1435–1448 (2013) · Zbl 1282.90138 · doi:10.1134/S0005117913090014
[27] Kvasov, D.E., Sergeyev, Y.D.: Deterministic approaches for solving practical black-box global optimization problems. Adv. Eng. Softw. 80, 58–66 (2015)
[28] Kvasov, D.E., Mukhametzhanov, M.S., Sergeyev, Y.D.: Solving univariate global optimization problems by nature-inspired and deterministic algorithms. Adv. Eng. Softw. (2015, submitted) · doi:10.1016/j.advengsoft.2014.09.014
[29] Lemmerling, P., Van Huffel, S.: Analysis of the structured total least squares problem for HankelToeplitz matrices. Numer. Algorithms 27 (1), 89–114 (2001) · Zbl 0986.65040 · doi:10.1023/A:1016775707686
[30] Lera, D., Sergeyev, Y.D.: Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives. SIAM J. Optim. 23 (1), 508–529 (2013) · Zbl 1270.90049 · doi:10.1137/110859129
[31] Li, Y., Liu, K., Razavilar, J.: A parameter estimation scheme for damped sinusoidal signals based on low-rank Hankel approximation. IEEE Trans. Signal Process. 45 (2), 481–486 (1997) · doi:10.1109/78.554314
[32] Liuzzi, G., Lucidi, S., Piccialli, V.: A partition-based global optimization algorithm. J. Glob. Optim. 48 (1), 113–128 (2010) · Zbl 1230.90153 · doi:10.1007/s10898-009-9515-y
[33] Markovsky, I.: Bibliography on total least squares and related methods. Stat. Interface 3 (3), 329–334 (2010) · Zbl 1245.65001 · doi:10.4310/SII.2010.v3.n3.a6
[34] Mockus, J.: Bayesian Approach to Global Optimization. Kluwer Academic, Dordrecht (1989) · Zbl 0693.49001 · doi:10.1007/978-94-009-0909-0
[35] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. SpringerBriefs in Optimization. Springer, New York (2014) · Zbl 1401.90017 · doi:10.1007/978-1-4614-9093-7
[36] Paulavičius, R., Žilinskas, J.: Simplicial Lipschitz optimization without the Lipschitz constant. J. Glob. Optim. 59 (1), 23–40 (2014) · Zbl 1300.90031 · doi:10.1007/s10898-013-0089-3
[37] Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.: Globally-biased Disimpl algorithm for expensive global optimization. J. Glob. Optim. 59 (2–3), 545–567 (2014) · Zbl 1297.90130 · doi:10.1007/s10898-014-0180-4
[38] Pintér, J.D.: Global Optimization in Action. Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Kluwer Academic, Dordrecht (1996) · Zbl 0842.90110 · doi:10.1007/978-1-4757-2502-5
[39] Pollock, D.: A Handbook of Time Series Analysis, Signal Processing, and Dynamics. Academic, London (1999) · Zbl 0953.62090
[40] Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5 (4), 858–870 (1995) · Zbl 0847.90128 · doi:10.1137/0805041
[41] Sergeyev, Y.D.: A one-dimensional deterministic global minimization algorithm. Comput. Math. Math. Phys. 35 (5), 705–717 (1995)
[42] Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Program. 81 (1), 127–146 (1998) · Zbl 0920.90133 · doi:10.1007/BF01584848
[43] Sergeyev, Y.D.: On convergence of ”Divide the Best” global optimization algorithms. Optimization 44 (3), 303–325 (1998) · Zbl 0986.90058 · doi:10.1080/02331939808844414
[44] Sergeyev, Y.D.: Multidimensional global optimization using the first derivatives. Comput. Math. Math. Phys. 39 (5), 711–720 (1999) · Zbl 0964.90036
[45] Sergeyev, Y.D., Grishagin, V.A.: A parallel method for finding the global minimum of univariate functions. J. Optim. Theory Appl. 80 (3), 513–536 (1994) · Zbl 0797.90098 · doi:10.1007/BF02207778
[46] Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods. FizMatLit, Moscow (2008) [in Russian]
[47] Sergeyev, Y.D., Kvasov, D.E.: Lipschitz global optimization. In: Cochran, J.J. (ed.) Wiley Encyclopedia of Operations Research and Management Science, vol. 4, pp. 2812–2828. Wiley, New York (2011)
[48] Sergeyev, Y.D., Khalaf, F.M.H., Kvasov, D.E.: Univariate algorithms for solving global optimization problems with multiextremal non-differentiable constraints. In: A. Törn, J. Žilinskas (eds.) Models and Algorithms for Global Optimization, pp. 123–140. Springer, Heidelberg (2007) · Zbl 1267.90113 · doi:10.1007/978-0-387-36721-7_8
[49] Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. SpringerBriefs in Optimization. Springer, New York (2013) · Zbl 1278.90005 · doi:10.1007/978-1-4614-8042-6
[50] Sergeyev, Y.D., Mukhametzhanov, M.S., Kvasov, D.E., Lera, D.: Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization. J. Optim. Theory Appl. (2016, to appear) · Zbl 1351.90134 · doi:10.1007/s10957-016-0947-5
[51] Strekalovsky, A.S.: Elements of Nonconvex Optimization. Nauka, Novosibirsk (2003) [in Russian]
[52] Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic, Dordrecht (2000). 3rd edn. by Springer, Berlin (2014) · Zbl 0987.90068
[53] Törn, A., Žilinskas, A.: Global Optimization. Lecture Notes in Computer Science, vol. 350. Springer, Berlin (1989) · doi:10.1007/3-540-50871-6
[54] Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. SIAM, Philadelphia (1991) · Zbl 0789.62054 · doi:10.1137/1.9781611971002
[55] Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008) · Zbl 1136.90003
[56] Žilinskas, A.: Global Optimization. Axiomatics of Statistical Models, Algorithms, and Applications. Mokslas, Vilnius (1986) [in Russian]
[57] Žilinskas, A.: On similarities between two models of global optimization: statistical models and radial basis functions. J. Glob. Optim. 48 (1), 173–182 (2010) · Zbl 1202.90210 · doi:10.1007/s10898-009-9517-9
[58] Žilinskas, A., Žilinskas, J.: Global optimization based on a statistical model and simplicial partitioning. Comput. Math. Appl. 44 (7), 957–967 (2002) · Zbl 1047.90036 · doi:10.1016/S0898-1221(02)00206-7
[59] Žilinskas, A., Žilinskas, J.: Interval arithmetic based optimization in nonlinear regression. Informatica 21 (1), 149–158 (2010) · Zbl 06260291
[60] Žilinskas, A., Žilinskas, J.: A hybrid global optimization algorithm for non-linear least squares regression. J. Glob. Optim. 56 (2), 265–277 (2013) · Zbl 1275.90061 · doi:10.1007/s10898-011-9840-9
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.