CS 328: Numerical Methods for Visual Computing (Fall 2018)
Summary: Visual computing disciplines are characterized by their universal reliance on numerical algorithms to process and display large amounts of visual information such as geometry, images, and volume data; an understanding of numerical methods is thus an important prerequisite to working in this area. This course will familiarize students with a range of essential numerical tools to solve practical problems in a visual computing context.
Contents: This course provides a first introduction to the field of numerical analysis with a strong focus on visual computing applications. Using examples from computer graphics, geometry processing, computer vision, and computational photography, students will gain hands-on experience with a range of essential numerical algorithms.
The course will begin with a review of important considerations regarding floating point arithmetic and error propagation in numerical computations. Following this, students will study and experiment with several techniques that solve systems of linear and non-linear equations. Since many interesting problems cannot be solved exactly, numerical optimization techniques constitute the second major topic of this course. Students will solve a variety of problems using nonlinear optimization, principal component anlysis, and deep neural networks. The course concludes with a review of numerical methods that make judicious use of randomness to solve problems that would otherwise be intractable.
Students will have the opportunity to gain practical experience with the discussed methods using programming assignments based on Scientific Python.
Prerequisites: Course prerequisites are MATH-101 (Analysis I) and MATH-111 (Linear Algebra). The courses CS-211 (Introduction to visual computing) and MATH-106 (Analysis II) are recommended but not required.
Students are expected to have good familiarity with at least one programming language (e.g. C/C++, Java, Scala, Python, R, Ruby...). The course itself will rely on Python, but this is straightforward to learn while taking the course. During the first weeks of the semester, there will be tutorial sessions on using Python and Scientific Python.
Although it is not a strict prerequisite, this course is highly recommended for students who wish to pursue studies in the area of Visual Computing, in particular: CS-341 (Introduction to computer graphics), CS-440 (Advanced computer graphics), CS-442 (Computer vision), CS-413 (Computational Photography), CS-444 (Virtual Reality), and CS-445 (Digital 3D geometry processing)
Learning outcomes: At the end of the course, students should be able to:
Write computer programs that use numerical linear algebra and analysis techniques to transform and visualize data
Reason about ways of structuring numerical computations efficiently.
Analyze the numerical stability of programs built on floating point arithmetic
Recognize numerical problems in visual computing applications and cast them into a form that can be solved or optimized.
Teaching methods: Lectures, interactive demos, theory and programming exercises
Expected student activities: Students are expected to study the provided reading material and actively participate in class and in exercise sessions. They will be given both theoretical exercises and a set of hands-on programming assignments.
- Continuous assessment during the semester via project assignments (50%)
- Final exam (50%)
Resources: Slides and other resource will be provided at the end of each class. The course textbook is Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics by Justin Solomon (freely available here)
The following optional references are optional but highly recommended: Scientific Computing: An Introductory Survey (2nd edition) by Michael Heath and What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg.
Late policy: the score of late homework submissions is reduced by -25% per late day.
Academic Integrity: Assignments must be solved and submitted individually. Do not copy (or even look at) parts of any of the homeworks from anyone else including the web. Do not make any parts of your homework available to anyone, and ensure that your files are not accessible to others. The university policies on academic integrity will be applied rigorously.
Lecture: Administrative details, overview of course topics, introduction to Floating Point arithmetic & error analysis.
Exercise: Introduction to Python.
Lecture: Linear systems review, LU decomposition.
Reading: Solomon, Chapter 3.
Homework 1 released.
Exercise: Introduction to NumPy.
Lecture: Conditioning of linear systems, Intro to Least Squares
Reading: Solomon, Chapter 4.
Exercise: Part 1: Introduction to Matplotlib, Part 2: homework Q&A.
Lecture: Least Squares continued, QR Factorization, Regularization
Reading: Solomon, Chapter 5 (you can skip over the section on Gram-Schmidt QR).
Homework 1 due, homework 2 released.
Lecture: How to write efficient numerical code: high-performance computing, processor architecture trends, parallelism, vectorization.
Lecture: Singular Value Decomposition
Reading: Chapter 6 [up to 6.4.1]
Homework 2 due, homework 3 released.
Lecture: (Nonlinear) Root finding and optimization (1D)
Reading: Solomon, Chapter 8, Section 1: Nonlinear Systems (1D case)
Lecture: Nonlinear problems, Multiple variables and Optimization
Reading: Solomon, Chapter 9.
Homework 3 due, homework 4 released.
Lecture: Numerical integration.
Reading: Solomon, Chapter 14.1 & 14.2.[1,2,3,5,6]
Lecture: Neural networks.
Reading: Neural Networks and Deep Learning (online book), Chapter 1-2
Homework 4 due, homework 5 released.
Lecture: Monte Carlo methods.
Reading: PhD Thesis by Wojciech Jarosz: Appendix A: Monte Carlo Integration, pages 149-157
Lecture: Markov Chain Monte Carlo
Lecture: Wrap-up, homework 4 & exam review.