CIS 610, Summer 1, 2009
Brief description:
The purpose of this course is to present geometric methods used in
computer vision, robotics and computer graphics.
The treatment will be rigorous but
I will try very hard to convey intuitions and to give many
examples illustrating all these concepts.
Syllabus:
This time, I intend to discuss two kinds of topics:

Affine and Euclidean geometry, spectral theorems, SVD, pseudoinverses and
PCA,

Convex sets, polytopes, polyhedra and basics of linear programming
The material in (2) provides firm foundations for
linear programming and convex programming.

Basics of Affine Geometry

Affine spaces, affine combinations (barycenters)

Affine subspaces, affine independence, affine frames,
convex combinations

Affine maps, affine groups

A glimpse at affine geometry
(Pappus, Desargues)

Hyperplanes
and affine forms, intersection of affine spaces.
(Chapter 12 of GMA)

Euclidean Geometry

Inner Products, Euclidean Spaces

Orthogonality, Orthogonal and Orthonormal bases, GramSchmidt

A glimpse at Fourier Series

Linear Isometries (also called orthogonal transformations),
the orthogonal group, orthogonal matrices,
the Groups O(n), SO(n)

Hyperplane reflections and the CartanDieudonne' Theorem

QRdecomposition

Householder matrices and QRdecomposition
(Chapters 6 and 7 of GMA)

Spectral theorems in Euclidean geometry and Hermitian spaces,

Normal linear maps, selfadjoint linear maps, skew selfadjoint linear maps
(Chapter 11 of GMA)

Singular value decomposition and polar forms

Polar form

Singular value decomposition (SVD)

Pseudoinverses

Least squares and PCA
(Chapters 12 and 13 of GMA)

Convex sets and Polytopes

Basic properties of convex sets,
Half spaces determined
by hyperplanes

Caratheodory's theorem on convex hulls

Radon's theorem

Helly's theorem.

Existence of center points

Separation theorems:
HahnBanach theorem and others.

Supporting hyperplanes, Minkowski's theorem.

The Farkas lemma

Vertices and Extremal points, Krein and Milman's theorem.

Polytopes and polyhedra: Hpolytopes and Vpolytopes. Cones.
Vertices, faces and facets.

Polarity and duality.
The main theorem.

FourierMotzkin elimination, the equivalence of Hpolyhedra and Vpolyhedra
revisited
We may also discuss applications to the Support Vector Machine Method
(Chapter 3 of GMA + Notes)

Foundations of Linear Programming

Linear programming

Primal and Dual Programs

Lagrangian functions and
Strong Duality

Application to fractional packing and covering problems

Introduction to primaldual combinatorial algorithms
Back to
Gallier Homepage
published by: