Welcome to the homepage of the lecture

Convex Analysis for Image Processing

Winter Term 2016 / 2017

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.



AnnouncementsDescriptionPrerequisitesTutorialsRegistrationOral ExamContents 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.


MIA Group
©2001-2023
The author is not
responsible for
the content of
external pages.

Imprint - Data protection