# Gradient Descent Methods

This tour explores the use of gradient descent method for unconstrained and constrained optimization of a smooth function

## Contents

- Installing toolboxes and setting up the path.
- Gradient Descent for Unconstrained Problems
- Gradient Descent in 2-D
- Gradient Descent in Image Processing

## Installing toolboxes and setting up the path.

You need to download the following files: signal toolbox and general toolbox.

You need to unzip these toolboxes in your working directory, so that you have `toolbox_signal` and `toolbox_general` in your directory.

For Scilab user: you must replace the Matlab comment '%' by its Scilab counterpart '//'.

Recommandation: You should create a text file named for instance `numericaltour.sce` (in Scilab) or `numericaltour.m` (in Matlab) to write all the Scilab/Matlab command you want to execute. Then, simply run `exec('numericaltour.sce');` (in Scilab) or `numericaltour;` (in Matlab) to run the commands.

Execute this line only if you are using Matlab.

    getd = @(p)path(p,path); % scilab users must *not* execute this

Then you can add the toolboxes to the path.

    getd('toolbox_signal/');
    getd('toolbox_general/');

## Gradient Descent for Unconstrained Problems

We consider the problem of finding a minimum of a function f
, hence solving

min x∈R d f(x)
where f:R d→R
is a smooth function.

Note that the minimum is not necessarily unique. In the general case, f
might exhibit local minima, in which case the proposed algorithms is not expected to find a global minimizer of the problem. In this tour, we restrict our attention to convex function, so that the methods will converge to a global minimizer.

The simplest method is the gradient descent, that computes

x(k+1)=x(k)−τ k∇f(x(k)),
where τ k>0
is a step size, and ∇f(x)∈R d
is the gradient of f
at the point x
, and x(0)∈R d
is any initial point.

In the convex case, if f
is of class C 2
, in order to ensure convergence, the step size should satisfy

0<τ k<2 sup x∥H f(x)∥
where H f(x)∈R d×d
is the Hessian of f
at x
and ∥⋅∥
is the spectral operator norm (largest eigenvalue).

## Gradient Descent in 2-D

We consider a simple problem, corresponding to the minimization of a 2-D quadratic form

f(x)=1 2(x 2 1+η x 2 2,)
where η>0
controls the anisotropy, and hence the difficulty, of the problem.

Anisotropy parameter η
.

    eta = 10;

Function f
.

    f = @(x)( x(1)^2 + eta*x(2)^2 ) /2;

Background image of the function.

    t = linspace(-.7,.7,101);
    [u,v] = meshgrid(t,t);
    F = ( u.^2 + eta*v.^2 )/2 ;

Display the function as a 2-D image.

    clf; hold on;
    imagesc(t,t,F); colormap jet(256);
    contour(t,t,F, 20, 'k');
    axis off; axis equal;

Gradient.

    Gradf = @(x)[x(1); eta*x(2)];

The step size should satisfy τ k<2/η
. We use here a constrant step size.

    tau = 1.8/eta;

Exercice 1: (the solution is exo1.m) Perform the gradient descent using a fixed step size τ k=τ
. Display the decay of the energy f(x(k))
through the iteration. Save the iterates so that `X(:,k)` corresponds to x(k)
.

    exo1;

Display the iterations.

    clf; hold on;
    imagesc(t,t,F); colormap jet(256);
    contour(t,t,F, 20, 'k');
    h = plot(X(1,:), X(2,:), 'k.-');
    set(h, 'LineWidth', 2);
    set(h, 'MarkerSize', 15);
    axis off; axis equal;

Exercice 2: (the solution is exo2.m) Display the iteration for several different step sizes.

    exo2;

## Gradient Descent in Image Processing

We consider now the problem of denoising an image y∈R d
where d=n×n
is the number of pixels (n
being the number of rows/columns in the image).

Load a clean image.

    n = 256;
    name = 'lena';
    x0 = rescale( load_image(name, n) );

Display it.

    clf;
    imageplot(x0);

Add noise to it, to simulate a noisy image.

    sigma = .1;
    y = x0 + randn(n)*sigma;

Display the noisy image y
.

    clf;
    imageplot(clamp(y));

Denoising is obtained by minimizing the following functional

min x∈R d f(x)=1 2∥y−x∥2+λ J(x)
where J(x)
is a smoothed total variation of the image.
J(x)=∑i∥(G x)i∥ε
where (G x)i∈R 2
is an approximation of the gradient of x
at pixel i
and for u∈R 2
, we use the following smoothing of the L 2
norm in R 2
∥u∥ε=ε 2+∥u∥2−−−−−−−−√,
for a small value of ε>0
.

The gradient of the functional read

∇f(x)=x−y+λ∇J(x)
where the gradient of the smoothed TV norm is
∇J(x)i=G∗(u)where u i=(G x)i∥(G x)i∥ε
where G∗
is the adjoint operator of G
which corresponds to minus a discretized divergence.

Value for λ
.

    lambda = .3;

Value for ε
.

    epsilon = 1e-3;

TV norm.

    Amplitude = @(u)sqrt(epsilon^2 + sum(u.^2,3));
    J = @(x)sum(sum(Amplitude(Grad(x))));

Function to minimize.

    f = @(x)1/2*norm(x-y,'fro')^2 + lambda*J(x);

Gradient of TV norm. Note that `div` implement −G∗
.

    Normalize = @(u)u./repmat(Amplitude(u), [1 1 2]);
    GradJ = @(x)-div( Normalize(grad(x)) );

Gradient of the functional.

    Gradf = @(x)x-y+lambda*GradJ(x);

The step size should satisfy

0<τ k<2 1+4 λ/ε.
Here we use a slightly larger step size, which still work in practice.

    tau = 1.8/( 1 + lambda*8/epsilon );
    tau = tau*4;

Exercice 3: (the solution is exo3.m) Implement the gradient descent. Monitor the decay of f
through the iterations.

    exo3;

Display the resulting denoised image.

    clf;
    imageplot(x);

