Convex Analysis for Image Processing
Dr. Matthias Augustin
Office hour: Wednesday, 14:00 - 15:00.
Winter Term 2016 / 2017
Lectures (3h) with exercises (1h);
(6 ETCS points)
Lectures:
Monday, 12-14 c.t., Building E1.3, Lecture Hall 003
Thursday, 16-18 c.t., Building E1.3, Lecture Hall 001
First lecture: Thursday, October 27, 2016
First Tutorial: Thursday, November 17, 2016; see also below.
Announcements –
Description –
Prerequisites –
Tutorials –
Registration –
Oral Exam –
Contents –
Assignments –
Literature
- 2017-03-03: ORAL EXAMS:
Sent information about the first exam to all registered students.
If you are registered but have not received an email with date and time of
your exam and further information, please let me know so I can provide
this information to you.
All exams will take place at my office (Building E1 7, Room 4.12).
- 2017-02-23: Slides for lecture 23 are online.
All chapters updated, corrected typos and changed some formulations.
The lecture notes are now also available in one file.
- 2017-01-06: Exam dates fixed. For more information, see
Oral Exam.
- 2016-12-08: As decided by vote of attendees of the lecture today,
proofs will further on be presented on the blackboard. This means that
slides will no longer contain abbreviated versions of proofs.
- 2016-11-14: Registration is closed.
Many problems in image processing or computer vision can be modeled as convex
minimization problems. The restored image is thus the minimizer of a suitable
convex energy functional and a numerical solution strategy can rely on fast
optimization algorithms. Many such algorithms rely on knowledge of convex
analysis. Therefore, this course wants to introduce students to some basic
concepts in this rich field including 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
(multi-dimensional) calculus and linear algebra as covered in introductory
maths course (such as Mathematik für Informatiker I-III). Mathematical
prerequisites which exceed the basic mathematics courses are provided within
the lecture. Lectures and tutorials will be in English. Knowledge from image
processing may be helpful, but is not required.
There will be a total of 7 tutorials which will take place instead of
regular lectures on
- 2016-11-17,
- 2016-12-01,
- 2016-12-15,
- 2017-01-05,
- 2017-01-19,
- 2017-02-02, and
- 2017-02-16.
The tutorials include homework assignments which
have to be submitted in the lecture break, or earlier and which will be graded.
Working together in groups of up to 3 students is permitted and encouraged.
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total. Exams will be oral. Time and date
will be announced on the homepage after the winter break.
Registration is closed since the submitting date of the first assignment passed
(2016-11-14).
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total.
First exam: March 09 and 10, 2017
Second exam: April 12 and 13, 2017
- You can attend both exams.
- Each exam counts as one try.
- Second exam can be taken to improve the grade.
- Exams can be taken in English (default) or German.
Registration:
You have to register in
- HISPOS.
- Furthermore, for internal uses, register per eMail to
Matthias Augustin.
(Deadline first exam: February 23, 2017)
(Deadline second exam: March 29, 2017)
Subject: [CAIP16] exams
Content:
First name: [myFirstName]
Last name: [myLastName]
Date of birth: [dd.mm.yyyy]
Student ID number: [...]
Registration for: [first/second] exam
Prefered language: [English/German]
- I will arrange the time slots and let you know.
Course material is available on this homepage in order to
support the classroom teaching and the tutorials, not to replace
them. Additional organizational information, examples and explanations
that may be relevant for your understanding and the exam are provided
in the lectures and tutorials.
Lecture notes in one file
Lecture notes in separate chapters
No. |
Title |
Date |
|
Chapter 1 |
Introduction, Brief Background on Images, Motivation |
02/13 |
[download] |
Chapter 2 |
Convex Sets and Convex Functions |
02/13 |
[download] |
Chapter 3 |
Convexity, Continuity, and Differentiability |
02/13 |
[download] |
Chapter 4 |
Aspects of Smooth Unconstrained Convex Optimization |
02/13 |
[download] |
Chapter 5 |
Separation Theorems and Supporting Hyperlanes |
02/13 |
[download] |
Chapter 6 |
Subgradients and the Subdifferential |
03/27 |
[download] |
Chapter 7 |
Set-Operation Inspired Operations on Functions |
02/13 |
[download] |
Chapter 8 |
Non-Smooth Convex Optimization |
02/13 |
[download] |
Chapter 9 |
Conjugacy |
02/13 |
[download] |
Chapter 10 |
Duality in Convex Optimization |
02/13 |
[download] |
Chapter 11 |
Numercial Methods Involving Dual Problems |
02/13 |
[download] |
Appendix 1 |
Basic Mathematical Concepts, Notation |
02/13 |
[download] |
Index |
Index of Some Specific Terms and Concepts |
02/13 |
[download] |
Literature |
References |
02/13 |
[download] |
Slides
No. |
Title |
Date |
|
Lecture 0 |
Organisatorial Issues |
10/27 |
[download] |
Lecture 1 |
Introduction, Brief Background on Images, Motivation |
10/27 |
[download] |
Lecture 2 |
Convex Sets, Convex Functions, Extended Reals, Semi-Continuity |
10/28 |
[download] |
Lecture 3 |
Operations preserving Convexity / Lower Semi-Continuity, Attainment
and Uniqueness of Minima
|
10/31 |
[download] |
Lecture 4 |
Convexity of Differentiable Functions, Continuity of Convex Functions
|
11/03 |
[download] |
Lecture 5 |
Introduction to Smooth Optimization
|
11/07 |
[download] |
Lecture 6 |
Theory for Smooth Convex Optimization
|
11/10 |
[download] |
Lecture 7 |
(Optimal) Gradient Descent for Smooth Convex Optimization
|
11/14 |
[download] |
Lecture 8 |
Separation Theorems and Supporting Hyperplanes
|
11/21 |
[download] |
Lecture 9 |
Subgradients and Subdifferential: Definition and First Properties
|
11/24 |
[download] |
Lecture 10 |
Subgradients and Subdifferential: Relations to Directional Derivatives
and Calculus Rules
|
11/28 |
[download] |
Lecture 11 |
Set-Operation Inspired Operations on Functions: Proximal Mapping,
Moreau Envelope, Closure, Convex Hull, Closed Convex Hull
|
12/05 |
[download] |
Lecture 12 |
Non-Smooth Convex Optimization I: Lower Complexity Bound, Subgradient
Method for unconstrained, geometrically constrained and inequality
constrained problems
|
12/08 |
[download] |
Lecture 13 |
Non-Smooth Convex Optimization II: Proximal point algorithm, composite
optimization, proximal gradient scheme, acceleration, LASSO, ISTA, FISTA
|
12/08 |
[download] |
Lecture 14 |
Convex Conjugate I: Definition, Interpretation, Geometric Construction,
First Properties
|
01/02 |
[download] |
Lecture 15 |
Convex Conjugate II: Further Properties, Fenchel-Moreau Theorem, Conjugacy
and Infimal Convolution, Conjugacy and the Subdifferential, Moreau's
Decomposition, Dual Norms
|
01/09 |
[download] |
Lecture 16 |
Duality I: Kuhn-Tucker Vectors, Lagrange Multipliers, KKT Conditions
|
01/12 |
[download] |
Lecture 17 |
Duality II: Geometric Interpretation, Lagrangian
Duality, and Slater’s Constraint Qualification
|
01/16 |
[download] |
Lecture 18 |
Duality III: Conjugate Duality
|
01/23 |
[download] |
Lecture 19 |
Duality IV: Fenchel Duality
Dual Algorithms I: Dual Proximal Point and Augmented Lagrangian
|
01/26 |
[download] |
Lecture 20 |
Dual Algorithms II: Primal-dual Subgradient Method, Monotone Operators,
Non-expansive Operators
|
01/30 |
[download] |
Lecture 21 |
Dual Algorithms III: Resolvents, Monotonicity and Convexity, Strong
Monotonicity, Fixpoints
|
02/06 |
[download] |
Lecture 22 |
Dual Algorithms IV: Operator Splitting, (Primal-)Dual Methods for
Composite Optimization, ADMM
|
02/09 |
[download] |
Lecture 23 |
Dual Algorithms V: Primal-Dual Hybrid Gradient Method and Applications in
Image Analysis
|
02/13 |
[download] |
No. |
Title |
Date |
|
Submit until |
Assignment 01 |
Convex Sets and Convex Functions |
11/07 |
[download] |
11/14 |
Assignment 02 |
Strong Convexity, Smooth Convex Optimization |
11/21 |
[download] |
11/28 |
Assignment 03 |
Projections, Subgradients, Subdifferentials |
12/05 |
[download] |
12/12 |
Assignment 04 |
Subdifferentials, Proximal Mappings |
12/12 |
[download] |
01/02 |
Assignment 05 |
Heavy-Ball Method, Conjugates |
01/09 |
[download] |
01/16 |
Assignment 06 |
Conjugates, Legendre-Fenchel Transform |
01/23 |
[download] |
01/30 |
Assignment 07 |
Duality, Monotone Operators |
02/06 |
[download] |
02/13 |
There is no specific text book for this class, but here is a selection of some
books covering many of the topics in this course, giving background material
and providing further reading:
-
Convex Analysis
R. T. Rockafellar, Princeton University Press, 1997.
- Convex Analysis and Minimization Algorithms I+II
J.-B. Hiriart-Urruty and C. Lemaréchal, Springer, 1993.
- Fundamentals of Convex Analysis
J.-B. Hiriart-Urruty and C. Lemaréchal, Springer, 2001.
(Abridged version of the previous two-volume entry.)
- Convex Optimization
S. Boyd and L. Vandenberghe, Cambridge University Press, 2004.
(Also available to
download at
the authors' homepages.)
- Introductory Lectures on Convex Optimization - A Basic Course.
Y. Nesterov, Kluwer Academic Publishers, 2004.
- Convex Analysis and Optimization.
D. P. Bertsekas, Athena Scientific, 2003.
- Convex Analysis and Monotone Operator Theory in Hilbert Spaces.
H. H. Bauschke and P. L. Combettes, Springer, 2011.
-
Variational Analysis
R. T. Rockafellar and R. J.-B. Wets, Springer, 1998.
- Perturbation Analysis of Optimization Problems
J. F. Bonnans and A. Shapiro, Springer, 2000.
Most of these and further books can be found in the mathematics and computer
science library.
Further references will be provided during the lecture.
|