Batenkov, Dmitry Accurate solution of near-colliding Prony systems via decimation and homotopy continuation. (English) Zbl 1375.65071 Theor. Comput. Sci. 681, 27-40 (2017). Summary: We consider polynomial systems of Prony type, appearing in many areas of mathematics. Their robust numerical solution is considered to be difficult, especially in “near-colliding” situations. We consider a case when the structure of the system is a-priori fixed. We transform the nonlinear part of the Prony system into a Hankel-type polynomial system. Combining this representation with a recently discovered “decimation” technique, we present an algorithm which applies homotopy continuation to an appropriately chosen Hankel-type system as above. In this way, we are able to solve for the nonlinear variables of the original system with high accuracy when the data is perturbed. Cited in 7 Documents MSC: 65H10 Numerical computation of solutions to systems of equations 65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations Keywords:Prony system; homotopy continuation; decimation; polynomial systems; ESPRIT; Hankel-type polynomial system; algorithm Software:PHClab; PHCpack PDFBibTeX XMLCite \textit{D. Batenkov}, Theor. Comput. Sci. 681, 27--40 (2017; Zbl 1375.65071) Full Text: DOI arXiv References: [1] Akinshin, A.; Batenkov, D.; Yomdin, Y., Accuracy of spike-train Fourier reconstruction for colliding nodes, (2015 International Conference on Sampling Theory and Applications (SampTA) (May 2015)), 617-621 [2] Badeau, R.; David, B.; Richard, G., High-resolution spectral analysis of mixtures of complex exponentials modulated by polynomials, IEEE Trans. Signal Process., 54, 4, 1341-1350 (2006) · Zbl 1373.94537 [3] Badeau, R.; David, B.; Richard, G., Performance of ESPRIT for estimating mixtures of complex exponentials modulated by polynomials, IEEE Trans. Signal Process., 56, 2, 492-504 (2008) · Zbl 1390.94085 [4] Batenkov, D., Prony systems via decimation and homotopy continuation, (Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. SNC ’14 (2014), ACM: ACM New York, NY, USA), 59-60 · Zbl 1345.65028 [5] Batenkov, D., Complete algebraic reconstruction of piecewise-smooth functions from Fourier data, Math. Comp., 84, 295, 2329-2350 (2015) · Zbl 1329.65327 [6] Batenkov, D., Stability and super-resolution of generalized spike recovery, Appl. Comput. Harmon. Anal. (2016), in press [7] Batenkov, D.; Yomdin, Y., Algebraic Fourier reconstruction of piecewise smooth functions, Math. Comp., 81, 277-318 (2012) · Zbl 1237.42003 [8] Batenkov, D.; Yomdin, Y., On the accuracy of solving confluent Prony systems, SIAM J. Appl. Math., 73, 1, 134-154 (2013) · Zbl 1269.65047 [9] Batenkov, D.; Yomdin, Y., Geometry and Singularities of the Prony mapping, J. Singul., 10, 1-25 (2014) · Zbl 1353.94014 [10] Beckermann, B.; Golub, G. H.; Labahn, G., On the numerical condition of a generalized Hankel eigenvalue problem, Numer. Math., 106, 1, 41-68 (Mar. 2007) [11] Ben-Or, M.; Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, (Proceedings of the twentieth annual ACM symposium on Theory of computing (1988), ACM), 301-309 [12] Cadzow, J. A., Total least squares, matrix enhancement, and signal processing, Digit. Signal Process., 4, 1, 21-39 (Jan. 1994) [13] Candes, E.; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math., 67, 6, 906-956 (Jun. 2014) [14] Comer, M. T.; Kaltofen, E. L.; Pernet, C., Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values, (Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (2012), ACM), 138-145 · Zbl 1323.65008 [15] Dayton, B.; Li, T.-Y.; Zeng, Z., Multiple zeros of nonlinear systems, Math. Comp., 80, 276, 2143-2168 (2011) · Zbl 1242.65102 [16] Eckhoff, K., Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions, Math. Comp., 64, 210, 671-690 (1995) · Zbl 0830.65144 [17] Elaydi, S., An Introduction to Difference Equations (2005), Springer · Zbl 1071.39001 [18] Gautschi, W., On inverses of Vandermonde and confluent Vandermonde matrices, Numer. Math., 4, 1, 117-123 (1962) · Zbl 0108.12501 [19] Giesbrecht, M.; Labahn, G.; Lee, W.-s., Symbolic-numeric sparse interpolation of multivariate polynomials, J. Symbolic Comput., 44, 8, 943-959 (Aug. 2009) [20] Guan, Y.; Verschelde, J., PHClab: a MATLAB/Octave interface to PHCpack, (Software for Algebraic Geometry (2008), Springer), 15-32 · Zbl 1148.68578 [21] Kaltofen, E.; Lee, W.-s., Early termination in sparse interpolation algorithms, J. Symbolic Comput., 36, 3-4, 365-400 (Sep. 2003) [22] Kaltofen, E.; Pernet, C., Sparse polynomial interpolation codes and their decoding beyond half the minimal distance, (ISSAC 2014 Proc. 39th Internat. Symp. Symbolic Algebraic Comput (2014)), 280-287 [23] Kaltofen, E. L.; Lee, W.-s.; Yang, Z., Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation, (Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation (2012), ACM), 130-136 · Zbl 1347.65037 [24] Kia, S.; Henao, H.; Capolino, G.-A., A high-resolution frequency estimation method for three-phase induction machine fault detection, IEEE Trans. Ind. Electron., 54, 4, 2305-2314 (Aug. 2007) [25] Kim, Y.-H.; Youn, Y.-W.; Hwang, D.-H.; Sun, J.-H.; Kang, D.-S., High-resolution parameter estimation method to identify broken rotor bar faults in induction motors, IEEE Trans. Ind. Electron., 60, 9, 4103-4117 (Sep. 2013) [26] Lee, W.-s., From quotient-difference to generalized eigenvalues and sparse polynomial interpolation, (Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation. SNC ’07 (2007), ACM: ACM New York, NY, USA), 11-116 [27] Maravic, I.; Vetterli, M., Sampling and reconstruction of signals with finite rate of innovation in the presence of noise, IEEE Trans. Signal Process., 53, 8 Part 1, 2788-2805 (2005) · Zbl 1370.94398 [28] 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 [29] Pereyra, V.; Scherer, G., Exponential Data Fitting and Its Applications (Jan. 2010), Bentham Science Publishers [30] Pope, S. R.; Szanto, A., Nearest multivariate system with given root multiplicities, J. Symbolic Comput., 44, 6, 606-625 (2009) · Zbl 1168.65347 [31] Potts, D.; Tasche, M., Parameter estimation for exponential sums by approximate Prony method, Signal Process., 90, 5, 1631-1642 (2010) · Zbl 1194.94128 [32] Prony, R., Essai experimental et analytique, J. Éc. Polytech. (Paris), 2, 24-76 (1795) [33] Sidi, A., Practical Extrapolation Methods: Theory and Applications (2003), Cambridge University Press · Zbl 1041.65001 [34] Stetter, H. J., Numerical polynomial algebra, SIAM (2004) · Zbl 1058.65054 [35] Stoica, P.; Moses, R., Spectral Analysis of Signals (2005), Pearson/Prentice Hall [36] Verschelde, J., Polynomial homotopy continuation with PHCpack, ACM Commun. Comput. Algebra, 44, 3/4, 217-220 (2011) · Zbl 1308.68198 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.