ATA 2016-17
Approximation theory and applications:
"Introduction to RBF and Kernel methods
and multivariate polynomial approximation "

These are the lectures for the course "Approximation Theory and Applications", A.Y. 2016-17 given by prof. Stefano De Marchi and prof. Andras Króo (Hungarian Academy of Science)

  • Class: Wednesday 11:30-13:15, Room 2AB45
  • Class: Thursday 11:30-13:15, Room 2AB45
  • Lab: Tuesday 10:00-12:00, NumLab

  • October 2016
    5, 6, 12, 13, 19, 20, 26, 27: class
    18, 25: lab

  • November 2016
    2, 3, 9, 10, 23, 24, 30 : class
    8, 22, 29: lab

  • December 2016
    1, 14, 15, 21 : class
    13, 20: lab

  • January 2017
    These lectures (16 hours) will be done by Prof. Andras Króo in the two weeks before the exams' session.
    10,11,12,13, 17, 18,19,20: class
    Notice : the lectures of Tuesday 10 and 17 are in room 2BC30, 10:30-12:00; the lectures of Friday 13 and 20 are in room 2BC30, 9:30-11:00. The other lectures as usual room 2AB45, 11:30-13:00.


    First part

    October 5. Introduction to the course. Recalls of polynomial interpolation, Lebesgue constant, divided differences. Polynomial splines space.
    October 6. B-splines: definition, recurrence relation, evaluation. Spline space and dimension. Natural splines. From splines to radial basis functions.
    October 12. Haar-Maierhuber-Curtis theorem for scattered data interpolation. Haar spaces: examples. Low-discrepancy points: Halton sequences. Radial basis function interpolation problem with distances. Distance matrix fit.
    October 13. Fill-distance and separation distance. Positive definite matrices and functions. Properties of positive definite function. Bochner characterization theorem.
    October 19. Strictly Positive Definite and radial functions. Characterization theorems. Examples: Gaussian, Laguerre-gaussian, Poisson, truncated powers, potentials and integration against a kernel.
    October 20. Seminar of Hanli Qiao - University of Torino. The slides are here.
    Iterested students to the FAIR software, the website where download it after signing in the copyright form is this one.
    October 26. Completely Monotone Functions and Multiply Monotone Functions: definitions, characterizations and examples. Scattered data interpolation with polynomial reproduction. Conditionally Positive Definite matrices of order 1 and their invertibility.
    October 27. (Strictly) Conditionally Positive Definite (SCPD) functions: characterization in terms of Fourier transform and its order of singularity. Examples: multiquadrics, powers and thin plate splines. The invertibility of the system with SCPD functions of order 1, in terms of its eigenvalues.
    November 2. Construction of compactly supported radial functions of Wendland, Wu, Gneiting, Eulidean hat and Buhmann. Introduction to error estimation.
    November 3. Reproducing kernel Hilbert spaces: definition and properties. Native spaces for RBF kernels. The interpolant in cardinal form. The power function. Pointwise error estimation by using the power function.
    November 9. Error in terms of the fill distance. Stability analysis: upper and lower bound for max and min eigenvalues. Trade-off principle and its analysis: trial and error, max of the power function as error indicators.
    November 10. Leave One Out Cross Validation, Contour Padé. Optimality principles for RBF interpolants. Least-squares with RBF.
    November 23. Least squares, weighted least squares and moving least squares (MLS). Backus-Gilbert (BG)approach .
    November 24. Matrix form of the BG approach. Proof of equivalence between BG and MLS. Examples: Shepard's methods and its generalizations. Error bounds in MLS.
    November 30. More on the error bounds for MLS. How to get better conditioned bases? Interpolation of isosurfaces. Intro to generalized Hermite interpolation.
    December 1. Generalized Hermite interpolation in details. Solution of elleptic PDES by Kansa's method (non-symmetric) and Fasshauer's one (symmetric). Galerkin method with RBF.
    December 14. Pseudo Spectral (PS) methods combined with RBF approximation. Symmetric and non symmetric methods are "equivalent" to the PS method.
    December 15. New results in kernel-based approximation: fast computation of stable basis functions , image reconstruction from Radon data.
    December 21. First part test

    Second part

    January 10. Recalls on Weierstrass theorem and their claims (first and second), with proofs. Stone-Weierstrass theorem and the necessary conditions. Examples: lacunary and incomplete polynomials. Tietze extension theorem.
    January 11. Existence, uniqueness, characterization of best approximation of a given function. Size of the best approximation error. Tau functional at f in a certain direction. Examples of tau functionals in some Hilbert spaces: continuos functions, L_p spaces p>1 and p< \infinity, L_1.
    January 12. Caratheodory lemma (no proof). General characterization theorem for best approximation. Examples: C[0,1] and M=P_2; more general linear functionals. Best approximation for linear functionals
    January 13. Haar spaces: various way to define and examples (algebraic poly., trigonometric poly., span of exponentials). Uniqueness of b.a. assuming M be a Haar space. Inqualities for polynomials and their derivatives: Bernstein, Schur and Markov.
    January 17. Modulus of continuity. Jackson's theorem (with proof) for trig polynomials for estimating the best approximation error. Some corollaries: Bernstein Letargy theorem, Dini-Lipschitz theorem, Stechkin inequality.
    January 18. Projection and positive linear operators. Lebesgue inequality. Lozinskii-Harsiladze theorem. Korovkin theorem. Bernstein, Fejér operator. Comparison of operators: Fourier, Fejér. De la Valleé Poussin operator
    January 19. Multivariate Markov inequality for polynomials on convex and central symmetric bodies. Multivariate Bernstein inequality.
    January 20. Optimal meshes: definition and meaning. Construction: from one dimensional case to the multivariate. Examples.

    Lab exercises

    October 18. The text of today's lab is here .
    October 25. The text of today's lab is here .
    November 8. The text of today's lab is here .
    November 22. The text of today's lab is here .
    November 29. The text of today's lab is here .
    December 13. The text of today's lab is here .
    December 20. Today's lab was dedicated to finalize implementations

    Final test
    The final test consists of two parts: written test and oral discussion. The final mark will be the weighted sum of the mark of the first part (De Marchi) and the second part (Króo)

    Dates (and rooms)
    27 Jan. 2017: only for the second part, room 331, 10 a.m. (prof. Kroo)
    13 Feb. 2017: 14-16, room 2AB45
    20 Jun. 2017: 10-12, room 2AB45
    11 Jul. 2017: 10-12, room 2AB45
    The last in September: To be agreed.

    Stefano De Marchi: Lectures on multivariate polynomial interpolation
    Stefano De Marchi: Four lectures on radial basis functions
    Gregory E. Fasshauer: Meshfree Approximation Methods with MATLAB
    Gregory E. Fasshauer and Michael Mc Court: Kernel-based Approximation Methods using Matlab
    Wen Shen, C.S.Shen and Zhuo-Jia Fu Recent Advances in Radial Basis Function Collocation Methods

    (last update: 20 January 2017).