Modeling Using Priors – A guide on the conception of an image denoising model

A model that works perfectly fine in every single case. Unfortunately, models that get closer to this tend to be very complex and, as a consequence, unpractical. Sometimes the best thing is to focus on a particular case and use all the assumptions that come with it in your favor and then devise a model to solve this particular class. In the following, we are going to work through image restoration models. The concepts introduced here will be motivated using the problem of Image Denoising.

An example from politics

Try to answer the question: Who is going to be the next president of Brazil?

It could be very hard to answer, even if you are a Brazilian. Nonetheless, you can be more confident on your answer if additional pieces of information are given. For example, your guess will be different in each of the scenarios below.

Continue reading


Understanding Taylor’s Theorem

Classical methods as gradient descent and Newton can be justified from Taylor’s theorem. It is a powerful tool to have at handy when doing convergence analysis of optimization methods. We try to develop here the necessary background in order to master this important tool.

Fundamental Results

Rolle’s Theorem: Let a,b \in \mathbb{R} and f:[a,b]\rightarrow \mathbb{R} a continuous function differentiable at the interval (a,b). Let c,d \in [a,b] such that f(c)=f(d). Then there exists \alpha \in (a,b) such that f^\prime(\alpha) = 0.

Proof: Assume, without loss of generality (w.l.o.g.), that d is the first value greater than c such that f(c) = f(d). Furter, w.l.o.g., assume that f(x) \geq 0 \quad \forall x \in [c,d]. Since [c,d] is a compact set, it attains a maximum at some point \alpha \in [c,d]. Therefore, f^\prime(\alpha) = 0. \hfill \square

Continue reading

Principles of Fixed Point Algorithms – Theory and Practice

A fixed-point algorithm is easy to explain: Given a fixed-point function f suited to your problem,  choose any point x_0 from dom(f) and compute f(x_0) to obtain the next point x_1. Proceed until find point x_k = f(x_k).

In the following, we expose the conditions in which this strategy works and the reason why. The famous gradient-method can be seen as a fixed-point algorithm.

A simple example

Let’s say you have n pairs of socks that are initially stored in n different drawers. The drawer in which the pair s is stored is given by d(s). Let’s assume that we start with d(s)=s \quad \forall s. Now we wish to change the drawers of each pair s such that d(s) \neq s \quad \forall s.. Is it possible? Sure it is!

Red dots represents d(x)=x

d(s) = \left\{ \begin{array}{ll} s+1 & s < n\\[0.15in] 1 & s=n \end{array}\right.

The function d is a permutation and it does not have any fixed-point, i.e., there exists no s such that d(s) = s. Functions with no fixed-points can be generated similarly for any countable set (See Hilbert’s Hotel). Let’s see what we can do with uncountable sets.

Continue reading

Necessary and Sufficient Conditions for Unrestricted Optimization Problems

In a previous post we have seen the conditions in which extremum values are guaranteed to exist. Nonetheless, there are cases in which the extremum values are there but the Weierstrass-Extremum value theorem didn’t tell us that much. The function x^2 has a global minimum on the interval (-1,1), for example. Further, the function

g(x) = \displaystyle \frac{1}{\sqrt{2 \pi}} e^{-(\frac{x^2}{2})} - \frac{1}{\sqrt{2\pi}}  e^{-(\frac{(x-2)^2}{2})}.

has a global maximum and a global minimum on the open interval (-5,5).


Continue reading

Existence of Extremum Values

At the end of the day we are all about extremes. We want to know the best we can do as much as the worst it can happen. How to be sure a function attains a maximum or a minimum value? Do they always exist?

Some intuition

Consider the function f:(0,1)\rightarrow \mathbb{R} defined as:

\displaystyle f(x) = x^3.

This function has neither a maximum nor a minimum value. In order to see that, suppose it has a maximum at z < 1. Then there exists \delta > 0 such that 1-z = \delta. If we set z^\star = 1  - \delta/ 2 we have f(z^\star) > f(z), which is a contradiction. A similar argument holds for the non-existence of a minimum.

If instead of domain (0,1) we define the function f at [0,1], then f attains a maximum and a minimum in its domain. The difference between the two domains is that the second it is a closed set, i.e., it contains all its accumulation (cluster) points.

Continue reading