Padua points and fake nodes for polynomial approximation: old, new and open problems

Year 2022, , 14 - 36, 14.03.2022

Stefano De Marchı

https://doi.org/10.33205/cma.1070020

Abstract

Padua points, discovered in 2005 at the University of Padua, are the first set of points on the square $[-1,1{]}^2$ that are explicitly known, unisolvent for total degree polynomial interpolation and with Lebesgue constant increasing like ${\log }^2\left(n\right)$ of the degree.
One of the key features of the Padua points is that they lie on a particular Lissajous curve. Other important properties of Padua points are

1. in two dimensions, Padua points are a WAM for interpolation and for extracting approximate Fekete points and discrete Leja sequences.
2. in three dimensions, Padua points can be used for constructing tensor product WAMs on different compacts.

Unfortunately, their extension to higher dimensions is still the biggest open problem. 

The concept of mapped bases has been widely studied (cf. e.g. [35] and references therein), which turns out to be equivalent to map the interpolating nodes and then construct the approximant in the classical form without the need of resampling. The mapping technique is general, in the sense that works with any basis and can be applied to continuous, piecewise or discontinuous functions or even images.
All the proposed methods show convergence to the interpolant provided that the function is resampled at the mapped nodes. In applications, this is often physically unfeasible. An effective method for interpolating via mapped bases in the multivariate setting, referred as Fake Nodes Approach (FNA), has been presented in [37]. In this paper, some interesting connection of the FNA with Padua points and families of relatives nodes, that can be used as fake nodes for multivariate approximation, are presented and we conclude with some open problems.

Keywords

Padua points, Lissajous curves and points, mapped polynomial basis.

References

• B. Adcock, R. B. Platte: A mapped polynomial method for high-accuracy approximations on arbitrary grids, SIAM J. Numer. Anal., 54 (2016), 2256–2281.
• R. Archibald, A. Gelb and J. Yoon: Polynomial Fitting for Edge Detection in Irregularly Sampled Signals and Images, SIAM J. Numer. Analysis, 43 (1) (2005), 259–279.
• J. Baglama, D. Calvetti and L. Reichel: Fast Leja points, Electron. Trans. Numer. Anal., 7 (1998), 124–140.
• J.-P. Berrut, S. De Marchi, G. Elefante and F. Marchetti: Treating the Gibbs phenomenon in barycentric rational interpolation and approximationvia the S-Gibbs algorithm, Appl. Math. Letters, 103 (2020), 106196.
• L. Bos: On certain configurations of points in R^n which are unisolvent for polynomial interpolation, J. Approx. Theory, 64 (3) (1991), 271–280.
• L. Bos: Multivariate interpolation and polynomial inequalities, Ph.D. course held at the University of Padua (2001), unpublished.
• L. Bos, M. Caliari, S. De Marchi and M. Vianello: A numerical study of the Xu interpolation formula, Computing, 76 (3-4) (2006), 311–324.
• L. Bos, M. Caliari, S. De Marchi, M. Vianello and Y. Xu: Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J. Approx. Theory, 143 (1) (2006), 15–25.
• L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva and M. Vianello: Geometric Weakly Admissible Meshes, Discrete Least Squares Approximations and Approximate Fekete Points, Math. Comp., 80 (2011), 1601–1621.
• L. Bos, S. De Marchi, M. Vianello and Y. Xu: Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer. Math., 108 (1) (2007), 43–57.
• L. Bos, S. De Marchi and S. Waldron: On the Vandermonde Determinant of Padua-like Points (on Open Problems section), Dolomites Res. Notes on Approx., 2 (2009), 1–15.
• L. Bos, S. De Marchi, A. Sommariva and M. Vianello: Weakly Admissible Meshes and Discrete Extremal Sets, Numer. Math. Theory Methods Appl., 4 (2011), 1–12.
• L. Bos, S. De Marchi, A. Sommariva and M. Vianello: Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Num. Anal., 48 (5) (2010), 1984–1999.
• L. Bos, N. Levenberg: On the Approximate Calculation of Fekete Points: the Univariate Case, Elec. Trans. Numer. Anal., 30 (2008), 377–397.
• L. Bos, A. Sommariva and M. Vianello: Least-squares polynomial approximation on weakly admissible meshes: disk and triangle, J. Comput. Appl. Math., 235 (2010), 660–668.
• L. Bos, M. A. Taylor and B. A. Wingate: Tensor product Gauss-Lobatto points are Fekete points for the cube, Math. Comp., 70 (2001), 1543–1547.
• L. Brutman: Lebesgue functions for polynomial interpolation: a survey, Ann. Numer. Math., 4 (1997), 111–127.
• M. D. Buhmann: Radial Basis Functions: Theory and Implementation, Cambridge Monogr. Appl. Comput. Math., Vol. 12, Cambridge Univ. Press, Cambridge, (2003).
• CAA: Padova-Verona Research Group on Constructive Approximation webpage: https://sites.google.com/view/caa-padova-verona/home
• M. Caliari, S. De Marchi and M. Vianello: Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput., 165 (2) (2005), 261–274.
• M. Caliari, S. De Marchi, M. Vianello: Algorithm 886: Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software, 35 (3) (2008), 1–11.
• M. Caliari, S. De Marchi and M. Vianello: Bivariate Lagrange interpolation at the Padua points: computational aspects, J. Comput. Appl. Math., 221 (2008), 284–292.
• M. Caliari, S. De Marchi, A. Sommariva and M. Vianello: Padua2DM: fast interpolation and cubature at Padua points in Matlab/Octave, Numer. Algorithms, 56 (1) (2011), 45–60.
• J. Canny: A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8 (6) (1986), 679–698.
• J. P. Calvi, N. Levenberg: Uniform approximation by discrete least squares polynomials, J. Approx. Theory, 152 (2008), 82–100.
• W. Cheney, W. Light: A Course on Approximation Theory, AMS, Vol. 101, (2009).
• K. C. Chung, T. H. Yao: On lattices adimmitting unique Lagrange interpolations, SIAM J. Numer. Anal., 14 (1977), 735–743.
• P. Davis: Interpolation and Approximation, Blaisdell Pub Company, New York, (1963).
• A. Cuyt, I. Yaman, B. A. Ibrahimoglu and B. Benouahmane: Radial orthogonality and Lebesgue constants on the disk, Numer. Algorithms, 61 (2) (2012), 291–313.
• C. de Boor: A Practical Guide to Splines, revised edition, Springer, New York, (2001).
• A. P. de Camargo, S. De Marchi: A few remarks on "On certain Vandermonde determinants whose variables separate", Dolomites Res. Notes Approx., 8 (2015), 1–11.
• S. De Marchi: On Leja sequences: some results and applications, Appl. Math. Comput., 152 (3) (2004), 621–647.
• S. De Marchi, G. Elefante and F. Marchetti: Stable discontinuous mapped bases: the Gibbs-Runge-Avoiding Stable Polynomial Approximation (GRASPA) method, Comput. Appl. Math., 40:299 (2021).
• S. De Marchi, G. Elefante, E. Perracchione and D. Poggiali: Quadrature at fake nodes, Dolomites Res. Notes Approx., 14 Special Issue MATA2020 (2021), 39–45.
• S. De Marchi, F. Marchetti, E. Perracchione and D. Poggiali: Polynomial interpolation via mapped bases without resampling, J. Comput. Appl. Math., 364 (2020), 112347.
• S. De Marchi, W. Erb and F. Marchetti: Lissajous sampling and spectral filtering in MPI applications: the reconstruction algorithm for reducing the Gibbs phenomenon, 2017 International Conference on Sampling Theory and Applications SampTA (2017), 580–584.
• S. De Marchi, F. Marchetti, E. Perracchione and D. Poggiali: Multivariate approximation at fake nodes, Appl. Math. Comput., 391 (2021), 125628.
• S. De Marchi,W. Erb, F. Marchetti, E. Perracchione and M. Rossini: Shape-Driven Interpolation with Discontinuous Kernels: Error Analysis, Edge Extraction and Applications in Magnetic Particle Imaging, SIAM J. Sci. Comput., 42 (2) (2020), B472-B491.
• S. De Marchi, A. Sommariva and M. Vianello: Multivariate Christoffel functions and hyperinterpolation, Dolomites Res. Notes Approx., 7 (2014), 36–33.
• S. De Marchi, R. Schaback and H. Wendland: Near-Optimal Data-Independent Point Locations for Radial Basis Function Interpolation, Adv. Comput. Math., 23 (3) (2005), 317–330.
• S. De Marchi, F. Piazzon, A. Sommariva and M. Vianello: Polynomial Meshes: Computation and Approximation, Proceedings of the 15th International Conference on Computational and Mathematical Methods in Science and Engineering CMMSE (2015), 414–425.
• S. De Marchi, K. Usevich: On certain multivariate Vandermonde determinants whose variables separate, Linear Alg. Appl., 449 (2014), 17–27.
• S. De Marchi, M. Vianello: Polynomial approximation on pyramids, cones and solids of rotation, Dolomites Res. Notes Approx., Proceedings DWCAA12, 6 (2013), 20–26.
• F. Dell’Accio, F. Di Tommaso and F. Nudo: Generalizations of the constrained mock-Chebyshev least squares in two variables: Tensor product vs total degree polynomial interpolation, Appl. Math. Letters, 125 (2022), 107732.
• M. Dubiner: The theory of multi-dimensional polynomial approximation, J. Anal. Math., 67 (1995), 39–116.
• W. Erb, C. Kathner, P. Denker and M. Alhborg: A survey on bivariate Lagrange interpolation on Lissajous nodes, Dolomites Res. Notes Approx., 8 (2015), 23-36.
• G. E. Fasshauer: Meshfree Approximation Methods with Matlab,World Scientific Publishing, Interdisciplinary Mathematical Sciences, Vol. 6, Singapore, (2007).
• G. E. Fasshauer, M. J. McCourt: Kernel-based Approximation Methods Using Matlab, World Scientific Publishing, Interdisciplinary Mathematical Sciences, Vol. 17, Singapore, (2015).
• L. Fernández, T. E. Pérez and M. A. Piãr: On Koornwinder classical orthogonal polynomials in two variables, J. Comput. Appl. Math., 236 (2012), 3817–3826.
• G. J. Gassner, F. Lörcher, C.-D. Munz and J. S. Hesthaven: Polymorphic nodal elements and their application in discontinuous Galerkin methods, J. Comput. Phys., 228 (2009), 1573–1590.
• J. W. Gibbs: Fourier’s Series, Nature, 59 (1898), 200.
• R. L. Hardy: Multiquadric equations of topography and other irregular surfaces, J. Geophys. Res., 76 (1971), 1905–1915.
• N. J. Higham: The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal., 24 (2004), 547–556.
• K. Hormann, G. Klein and S. De Marchi: Barycentric rational interpolation at quasi-equidistant nodes, Dolomites Res. Notes Approx., 5 (2012), 1–6.
• E. J. Kansa: Application of Hardy’s multiquadric interpolation to hydrodynamics, Proceeding Multiconference on Computer Simulation: Aerospace, San Diego (1986), 111–117.
• M. Krebsbach, B. Trauzette and A. Calzona: Optimization of Richardson extrapolation for quantum error mitigation, preprint on ResearchGate (21 January 2022).
• D. Kosloff, H. Tal-Ezer: A modified Chebyshev pseudospectral method with an O(N^{-1}) time step restriction, J. Comput. Phys., 104 (1993), 457–469.
• M. Koushki, E. Jabbari and M. Ahmadinia: Evaluating RBF methods for solving PDEs using Padua points distribution, Alexandria Eng. J., 59 (5) (2020), 2999–3018.
• O. Landon-Cardinal, L. C. G. Govia and A. A. Clerk: Quantitative Tomography for Continuous Variable Quantum Systems, Phys. Rev. Lett., 120 (9) (2018), 090501.
• N. T. Lloyd: Approximation Theory and Approximation Practice, SIAM, (2013).
• G. Mastroianni, D. Occorsio: Optimal systems of nodes for Lagrange interpolation on bounded intervals. A survey., J. Comput. Appl. Math., 134 (1-2) (2001), 325–341.
• J. C. Merino: Lissajous Figures and Chebyshev Polynomials, College Math. J., 32 (2) (2003), 122–127.
• C. R. Morrow, T. N. L. Patterson: Construction of Algebraic Cubature Rules Using Polynomial Ideal Theory, SIAM J. Numer. Anal., 15 (5) (1978), 953–976.
• Numerical computing with functions: Chebfun. www.chebfun.org
• R. Pachón, L. N. Trefethen: Barycentric-Remez algorithms for best polynomial approximation in the chebfun system, BIT Numer. Math., 49 (2009), 721–741.
• D. Poggiali, D. Cecchin, C. Campi and S. De Marchi: Oversampling errors in multimodal medical imaging are due to the Gibbs effect, Mathematics, 9 (12) (2021), 1348.
• L. Qu: Copula density estimation by Lagrange interpolation at the Padua points, Conference on Data Science, Statistics & Visualization 2017, Book of abstacts p. 67.
• T. Rivlin: An Introduction to the Approximation of Functions, Dover Pub. Inc, (1969).
• G. Rodeghiero, Y. Zhong et al.: An efficient interpolation for calculation of the response of composite layered material and its implementation in MUSIC imaging, Proceedings 19th Conference on the Computation of Electromagnetic Fields COMPUMAG, Budapest (Hungary) (2013).
• L. Romani, M. Rossini and D. Schenone: Edge detection methods based on RBF interpolation, J. Comput. Applied Math., 349 (2019), 532–547.
• C. Runge: Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten, Zeit. Math. Phys., 46 (1901), 224–243.
• B. Schölkopf, A. J. Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, USA, (2002).
• I. J. Schoenberg: Metric spaces and completely monotone functions, Ann. of Math., 39 (1938), 811–841.
• L. L. Schumaker: Spline Functions - Basic Theory, Wiley-Interscience, New York, (1981).
• A. Sommariva, M. Vianello: Computing approximate Fekete points by QR factorizations of Vandermonde matrices, Comp. Math. App., 57 (2009), 1324–1336.
• A. Sommariva, M. Vianello and R. Zanovello: Nontensorial Clenshaw–Curtis cubature, Numer. Algorithms, 49 (2008), 409–427.
• I. H. Sloan, R. S. Womersley: Extremal systems of points and numerical integration on the sphere. Adv. Comput. Math., 21 (2004), 107–125.
• M. A. Taylor, B. A. Wingate and R. E. Vincent: An algorithm for computing Fekete points in the triangle, SIAM J. Numer. Anal., 38 (5) (2000), 1707–1720.
• P. Vértesi: On the Lebesgue function and Lebesgue constant: a tribute to Paul Erdös, Bolyai Society of Mathematical Studies, Vol. 11, Budapest, Janos Bolyai Math. Soc., (2002), 705–728.
• H. Wendland: Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, Cambridge Univ. Press, (2005).
• Wikipedia: Padua points https://en.wikipedia.org/wiki/Padua_points
• Y. Xu: Christoffel functions and Fourier series for multivariate orthogonal polynomials, J. Approx. Theory, 82 (1995), 205–239.
• P. Zitnan: The collocation solution of Poisson problems based on approximate Fekete points, Eng. Anal. Bound. Elem., 35 (2011) 594–599.