A convex dual problem for the rational minimax approximation and Lawson’s iteration
HTML articles powered by AMS MathViewer
- by Lei-Hong Zhang, Linyi Yang, Wei Hong Yang and Ya-Nan Zhang;
- Math. Comp. 94 (2025), 2457-2494
- DOI: https://doi.org/10.1090/mcom/4021
- Published electronically: October 10, 2024
- HTML | PDF | Request permission
Abstract:
Computing the discrete rational minimax approximation in the complex plane is challenging. Apart from Ruttan’s sufficient condition, there are few other sufficient conditions for global optimality. The state-of-the-art rational approximation algorithms, such as the adaptive Antoulas-Anderson (AAA), AAA-Lawson, and the rational Krylov fitting method, perform highly efficiently, but the computed rational approximations may not be minimax solutions. In this paper, we propose a convex programming approach, the solution of which is guaranteed to be the rational minimax approximation under Ruttan’s sufficient condition. Furthermore, we present a new version of Lawson’s iteration for solving this convex programming problem. The computed solution can be easily verified as the rational minimax approximation. Our numerical experiments demonstrate that this updated version of Lawson’s iteration generally converges monotonically with respect to the objective function of the convex optimization. It is an effective competitive approach for computing the rational minimax approximation, compared to the highly efficient AAA, AAA-Lawson, and the stabilized Sanathanan-Koerner iteration.References
- N. I. Akhiezer, Elements of the theory of elliptic functions, Translations of Mathematical Monographs, vol. 79, American Mathematical Society, Providence, RI, 1990. Translated from the second Russian edition by H. H. McFaden. MR 1054205, DOI 10.1090/mmono/079
- I. Barrodale and J. C. Mason, Two simple algorithms for discrete rational approximation, Math. Comp. 24 (1970), 877–891. MR 301894, DOI 10.1090/S0025-5718-1970-0301894-X
- I. Barrodale, M. J. D. Powell, and F. D. K. Roberts, The differential correction algorithm for rational ${\cal l}_{\infty }$-approximation, SIAM J. Numer. Anal. 9 (1972), 493–504. MR 312685, DOI 10.1137/0709044
- Mario Berljafa and Stefan Güttel, Generalized rational Krylov decompositions with an application to rational approximation, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 894–916. MR 3361437, DOI 10.1137/140998081
- Mario Berljafa and Stefan Güttel, The RKFIT algorithm for nonlinear rational approximation, SIAM J. Sci. Comput. 39 (2017), no. 5, A2049–A2071. MR 3702872, DOI 10.1137/15M1025426
- Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575, DOI 10.1017/CBO9780511804441
- Pablo D. Brubeck, Yuji Nakatsukasa, and Lloyd N. Trefethen, Vandermonde with Arnoldi, SIAM Rev. 63 (2021), no. 2, 405–415. MR 4253796, DOI 10.1137/19M130100X
- E. W. Cheney and H. L. Loeb, Two new algorithms for rational approximation, Numer. Math. 3 (1961), 72–75. MR 121965, DOI 10.1007/BF01386002
- A. K. Cline, Rate of convergence of Lawson’s algorithm, Math. Comp. 26 (1972), 167–176. MR 298872, DOI 10.1090/S0025-5718-1972-0298872-8
- P. Cooper, Rational approximation of discrete data with asymptotic behaviour, PhD thesis, University of Huddersfield, 2007.
- Andrew G. Deczky, Equiripple and minimax (Chebyshev) approximations for recursive digital filters, IEEE Trans. Acoust. Speech Signal Process. ASSP- (1974), no. 2, 98–111. MR 419085, DOI 10.1109/TASSP.1974.1162556
- James Demmel, Ming Gu, Stanley Eisenstat, Ivan Slapničar, Krešimir Veselić, and Zlatko Drmač, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), no. 1-3, 21–80. MR 1723709, DOI 10.1016/S0024-3795(99)00134-2
- James Demmel and Krešimir Veselić, Jacobi’s method is more accurate than $QR$, SIAM J. Matrix Anal. Appl. 13 (1992), no. 4, 1204–1245. MR 1182723, DOI 10.1137/0613074
- T. A. Driscoll, N. Hale, and L. N. Trefethen, Chebfun User’s Guide, Pafnuty Publications, Oxford, 2014, www.chebfun.org.
- S. Ellacott and Jack Williams, Linear Chebyshev approximation in the complex plane using Lawson’s algorithm, Math. Comput. 30 (1976), no. 133, 35–44. MR 400652, DOI 10.1090/S0025-5718-1976-0400652-0
- G. H. Elliott, The construction of Chebyshev approximations in the complex plane, PhD thesis, Facultyof Science (Mathematics), University of London, 1978.
- Silviu-Ioan Filip, Yuji Nakatsukasa, Lloyd N. Trefethen, and Bernhard Beckermann, Rational minimax approximation via adaptive barycentric representations, SIAM J. Sci. Comput. 40 (2018), no. 4, A2427–A2455. MR 3840899, DOI 10.1137/17M1132409
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913, DOI 10.56021/9781421407944
- Ion Victor Gosea and Stefan Güttel, Algorithms for the rational approximation of matrix-valued functions, SIAM J. Sci. Comput. 43 (2021), no. 5, A3033–A3054. MR 4309865, DOI 10.1137/20M1324727
- B. Gustavsen and A. Semlyen, Rational approximation of frequency domain responses by vector fitting, IEEE Trans. Power Deliv., 14 (1999), 1052–1061.
- Martin H. Gutknecht, On complex rational approximation. I. The characterization problem, Computational aspects of complex analysis (Braunlage, 1982) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 102, Reidel, Dordrecht-Boston, Mass., 1983, pp. 79–101. MR 712892
- M. H. Gutknecht, J. O. Smith, and L. N. Trefethen, The Caratheodory-Féjer method for recursive, digital filter design, IEEE Trans. Acoust., Speech, Signal Processing, 31 (1983), 1417–1426.
- J. M. Hokanson, Multivariate rational approximation using a stabilized Sanathanan-Koerner iteration, arXiv:2009.10803v1, 2020.
- M.-P. Istace and J.-P. Thiran, On computing best Chebyshev complex rational approximants, Numer. Algorithms 5 (1993), no. 1-4, 299–308. Algorithms for approximation, III (Oxford, 1992). MR 1258602, DOI 10.1007/BF02108464
- Shinji Ito and Yuji Nakatsukasa, Stable polefinding and rational least-squares fitting via eigenvalues, Numer. Math. 139 (2018), no. 3, 633–682. MR 3814608, DOI 10.1007/s00211-018-0948-4
- Charles L. Lawson, CONTRIBUTIONS TO THE THEORY OF LINEAR LEAST MAXIMUM APPROXIMATION, ProQuest LLC, Ann Arbor, MI, 1961. Thesis (Ph.D.)–University of California, Los Angeles. MR 2939207
- Xin Liang, Ren-Cang Li, and Zhaojun Bai, Trace minimization principles for positive semi-definite pencils, Linear Algebra Appl. 438 (2013), no. 7, 3085–3106. MR 3018059, DOI 10.1016/j.laa.2012.12.003
- H. L. Loeb, On rational fraction approximations at discrete points, Technical report, Convair Astronautics, 1957, Math. Preprint #9.
- R. D. Millán, V. Peiris, N. Sukhorukova, and J. Ugon, Application and issues in abstract convexity, arXiv:2202.09959, 2022.
- R. Díaz Millán, V. Peiris, N. Sukhorukova, and J. Ugon, Multivariate approximation by polynomial and generalized rational functions, Optimization 71 (2022), no. 4, 1171–1187. MR 4420937, DOI 10.1080/02331934.2022.2044478
- Yuji Nakatsukasa, Olivier Sète, and Lloyd N. Trefethen, The AAA algorithm for rational approximation, SIAM J. Sci. Comput. 40 (2018), no. 3, A1494–A1522. MR 3805855, DOI 10.1137/16M1106122
- Yuji Nakatsukasa and Lloyd N. Trefethen, An algorithm for real and complex rational minimax approximation, SIAM J. Sci. Comput. 42 (2020), no. 5, A3157–A3179. MR 4161312, DOI 10.1137/19M1281897
- Yurii Nesterov, Lectures on convex optimization, Springer Optimization and Its Applications, vol. 137, Springer, Cham, 2018. Second edition of [ MR2142598]. MR 3839649, DOI 10.1007/978-3-319-91578-4
- Jorge Nocedal and Stephen J. Wright, Numerical optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940
- John R. Rice, The approximation of functions. Vol. 2: Nonlinear and multivariate theory, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 244675
- Arden Ruttan, A characterization of best complex rational approximants in a fundamental case, Constr. Approx. 1 (1985), no. 3, 287–296. MR 891533, DOI 10.1007/BF01890036
- E. B. Saff and R. S. Varga, Nonuniqueness of best approximating complex rational functions, Bull. Amer. Math. Soc. 83 (1977), no. 3, 375–377. MR 433108, DOI 10.1090/S0002-9904-1977-14276-6
- C. K. Sanathanan and J. Koerner, Transfer function synthesis as a ratio of two complex polynomials, IEEE T. Automat. Contr., 8 (1963), 56–58, https://doi.org/10.1109/TAC.1963.1105517.
- Herbert Stahl, Best uniform rational approximation of $x^\alpha$ on $[0,1]$, Bull. Amer. Math. Soc. (N.S.) 28 (1993), no. 1, 116–122. MR 1168517, DOI 10.1090/S0273-0979-1993-00351-3
- J.-P. Thiran and M.-P. Istace, Optimality and uniqueness conditions in complex rational Chebyshev approximation with examples, Constr. Approx. 9 (1993), no. 1, 83–103. MR 1198524, DOI 10.1007/BF01229337
- Lloyd N. Trefethen, Cubature, approximation, and isotropy in the hypercube, SIAM Rev. 59 (2017), no. 3, 469–491. MR 3683677, DOI 10.1137/16M1066312
- Jack Williams, Numerical Chebyshev approximation in the complex plane, SIAM J. Numer. Anal. 9 (1972), 638–649. MR 314232, DOI 10.1137/0709053
- Jack Williams, Characterization and computation of rational Chebyshev approximations in the complex plane, SIAM J. Numer. Anal. 16 (1979), no. 5, 819–827. MR 543971, DOI 10.1137/0716061
- Daniel E. Wulbert, On the characterization of complex rational approximations, Illinois J. Math. 24 (1980), no. 1, 140–155. MR 550656
- Yang Linyi, Lei-Hong Zhang, and Zhang Ya-Nan, The $L_q$-weighted dual programming of the linear Chebyshev approximation and an interior-point method, Adv. Comput. Math. 50 (2024), no. 4, Paper No. 80, 29. MR 4776430, DOI 10.1007/s10444-024-10177-w
- L.-H. Zhang, Y. Su, and R.-C. Li, Accurate polynomial fitting and evaluation via Arnoldi, Numer. Algebra Control Optim., 14:3(2024), 526–546, DOI 10.3934/naco.2023002.
Bibliographic Information
- Lei-Hong Zhang
- Affiliation: School of Mathematical Sciences, Soochow University, Suzhou 215006, Jiangsu, People’s Republic of China
- MR Author ID: 794517
- ORCID: 0000-0001-5349-8621
- Email: longzlh@suda.edu.cn
- Linyi Yang
- Affiliation: School of Mathematical Sciences, Soochow University, Suzhou 215006, Jiangsu, People’s Republic of China
- Email: lyyang161@stu.suda.edu.cn
- Wei Hong Yang
- Affiliation: School of Mathematical Sciences, Fudan University, Shanghai 200433, People’s Republic of China
- Email: whyang@fudan.edu.cn
- Ya-Nan Zhang
- Affiliation: School of Mathematical Sciences, Soochow University, Suzhou 215006, Jiangsu, People’s Republic of China
- Email: ynzhang@suda.edu.cn
- Received by editor(s): September 12, 2023
- Received by editor(s) in revised form: June 3, 2024, and August 24, 2024
- Published electronically: October 10, 2024
- Additional Notes: The first author’s research was partially supported by the National Natural Science Foundation of China NSFC-12471356, NSFC-12071332, NSFC-12371380, Jiangsu Shuangchuang Project (JSSCTD202209), Academic Degree and Postgraduate Education Reform Project of Jiangsu Province, and China Association of Higher Education under grant 23SX0403. The second author’s research was partially supported by Postgraduate Research & Practice Innovation Program of Jiangsu Province KYCX23_3226. The third author’s research was partially supported by the National Natural Science Foundation of China NSFC-72394365.
The first author is the corresponding author - © Copyright 2024 American Mathematical Society
- Journal: Math. Comp. 94 (2025), 2457-2494
- MSC (2020): Primary 41A50, 41A20, 65D15, 90C46
- DOI: https://doi.org/10.1090/mcom/4021