Interpolation and Approximation for Visual Computing
Lecturer: Vassillen Chizhov
Examiner:
Dr. Joachim Weickert
Winter Term 2022
Lectures (3h) with exercises (1h);
(6 ETCS points)
Lectures: Sessions with Q&A and Tutorial Sections
The lectures will be held online (Zoom link shared over email)
Monday, 14:1516:00
Thursday, 14:1516:00
Announcements –
Description –
Prerequisites –
Tutorials –
Registration –
Exam –
Contents –
Assignments –
Literature
Target group: Students in the Master Programme Visual Computing
Lecture aim: Give an introduction to the concepts of interpolation
and (function) approximation. This includes
 interpolation with polynomials,
 leastsquare fitting,
 polynomial splines,
 some Fourier theory,
 radial basis functions, and
 applications in image processing.
This course is suitable for students of visual computing, mathematics, and
computer science.
Students attending this course should be familiar with basic concepts of
(multidimensional) calculus and linear algebra as covered in introductory
maths course (such as Mathematik für Informatiker IIII). Mathematical
prerequisites which exceed the basic mathematics courses are provided within
the lecture notes. All material will be in English. Knowledge from image
processing may be helpful, but is not required.
In order to register for the lecture, write an email to
Vassillen Chizhov.
The subject line must begin with the tag [IAVC22].
Please use the following template for the email:
First name: myFirstName
Last name: myLastName
Date of birth: dd.mm.yyyy
Student ID number: ...
Course of study: Bachelor/Master/...
Subject: Computer Science/Visual Computing/Mathematics/...
Note that the email address from which you send this information will be used
to provide you with urgent information concerning the lecture.
Such information may include further regulations or urgent additional
remarks regarding assignment.
The registration is completely independent of
LSF/HISPOS.
They require a separate registration.
According to the regulations concerning storage and processing of
personal data (Art. 6 (1) Datenschutzgrundverordnung (DSGVO)) we
store and process your personal data for the purpose of lecture and
tutorial organisation only. I.e. we may use them to contact you, to
inform you about your grade, and to transmit your grades to the
examination office.
There will be two written exams: the first on 21.02, 1417 (E1 3, HS002), and the second on
21.03, 1417.
You are allowed to take part in both exams.
The better grade counts, but each exam will count as an attempt
individually.
Please remember that you have to register online for the exam
in the HISPOS system of the
Saarland University for each attempt separately.
Course material will be made available on this homepage.
Additional organizational information, examples and explanations
that may be relevant for your understanding and the exam are provided
in the online sessions and tutorials.
Introductory Slides
Here you can find: Dr. Augustin's notes.
We will follow the above notes for some topics (e.g. polynomials).
However, I will occasionally provide more details on specific topics, and
less on others. This will be made clear during the lectures.
For instance, I plan to cover some more applications for
interpolation and approximation for higher dimensions
(e.g. finite elements, PDE inpainting).
Date 
Please prepare 
Pages 
27.10.2022 
Polynomial Interpolation, Lagrange Basis

14 
31.10.2022 
Polynomial Interpolation, Newton Interpolation

512 
03.11.2022 
Interpolation Error, Polynomial Approximation

1322 
07.11.2022 
Splines I

2334 
10.11.2022 
Splines II: BSplines

3446 
14.11.2022 
Splines III: Approximation and Smoothing Splines

4653 
17.11.2022 
Solving Mock Exam I


21.11.2022 
Solving Mock Exam I


24.11.2022 
Higher Dimensions I: MairhuberCurtis Theorem and Multivariate Polynomials

5559 
28.11.2022 
Higher Dimensions II: Tensor Product Splines, Affine Transformations

5967 
01.12.2022 
Higher Dimensions III: Voronoi, Delaunay, and Multiharmonic Reconstruction

6774 
05.12.2022 
Fourier Theory I: Approximation in Orthonormal Bases, Fourier Series

7488 
08.12.2022 
Fourier Theory II: Fourier Transform, Convolution

8898 
12.12.2022 
Fourier Theory III: Discrete Fourier and Cosine Transforms

98101 
15.12.2022 
Fourier Theory IV: Degradation Phenomena in Reconstruction

101110 
19.12.2022 
Synthesis Functions I: Sampling Theorem

111115 
22.12.2022 
Synthesis Functions II: Inteprolation Using Synthesis Functions

115124 
02.01.2023 
Synthesis Functions III: Transfer to Higher Dimensions

124135 
05.01.2023 
Synthesis Functions IV: From Energy Minimizing Ideas

135143 
09.01.2023 
Interpolation and Approximation in Inner Product Spaces


12.01.2023 
Trigonometric Polynomial Approximation Exercises


16.01.2023 
Interpolation in Reproducing Kernel Hilbert Spaces


19.01.2023 
Fourier Transform, Convolution, Interpolation Exercises


23.01.2023 
Convolution, Bochner's Theorem Exercises


26.01.2023 
Mock Exam: Chebyshev Polynomials


30.01.2023 
Mock Exam: Monomial, Newton, Lagrange, Hermite Bases


02.02.2023 
Mock Exam: Hermite, De Casteljau, Approximation, Splines


06.02.2023 
Mock Exam: BSplines, Fourier, Theory


There is no specific text book for this class as it touches on many topics
for which specialized books exist.

Introduction to Numerical Analysis
J. Stoer, R. Bulirsch, Springer, 1993.
English translation of the originally german version.

Numerical Methods
W. Boehm, H. Prautzsch, CRC Press, 1993.

Interpolation and Approximation
P. Davis, Blaisdell, 1963.
Reprinted by Dover, 2014.

Approximation Theory
O. Christensen, K. Christensen, Springer, 2005.

Mathematics of Approximation
J. de Villiers, Springer, 2012.

Fourier Analysis and Applications
C. Gasquet, P. Witomski, Springer, 1999.

The Fourier Transform and its Applications
R. N. Bracwell, McGraw Hill, 1999.

A Practical Guide to Splines
C. de Boor, Springer, 2001.

Multivariate Splines
C. Chui, SIAM, 1991.

Scattered Data Approximation
H. Wendland, Cambridge University Press, 2005.
Most of these and further books can be found in the
mathematics and computer science library.
Further references will be provided during the lecture.
