regu.rst

Test Problems for Regularization Methods

A Fredholm integral equation of the first kind (in 1-dimensional) can be written as

∫₀¹K(s, t)f(t)dt = g(s), 0 ≤ s ≤ 1,

where g and K (called kernel) are known functions and f is the unknown solution. This is a classical example of a linear ill-posed problem, i.e., an arbitrary small perturbation of the data can cause an arbitrarily large perturbation of the solution. For example, in computerized tomography, K is an X-ray source, f is the object being scanned, and g is the measured damping of the X-rays. The goal here is to reconstruct the scanned object from information about the locations of the X-ray sources and measurements of their damping.

After discretizations (by the quadrature method or the Galerkin method), we obtain a linear system of equations Ax = b. All the regularization test problems are derived from discretizations of a Fredholm integral equation of the first kind. Each generated test problem has type RegProb, which is defined as:

immutable RegProb{T}
  A::AbstractMatrix{T}  # matrix of interest
  b::AbstractVector{T}  # right-hand side
  x::AbstractVector{T}  # the solution to Ax = b
end

Here is an example:

julia> matrixdepot("deriv2")
Computation of the Second Derivative:

A classical test problem for regularization algorithms.

Input options:

1. [type,] n, [matrixonly]: the dimension of the matrix is n. 
           If matrixonly = false, the linear system A, b, x will be generated. 
           (matrixonly = true by default.)

Reference: P.C. Hansen, Regularization tools: A MATLAB pacakge for 
           analysis and solution of discrete ill-posed problems. 
           Numerical Algorithms, 6(1994), pp.1-35

julia> A = matrixdepot("deriv2", 4) # generate the test matrix
4x4 Array{Float64,2}:
-0.0169271   -0.0195313  -0.0117188  -0.00390625
-0.0195313   -0.0481771  -0.0351563  -0.0117188 
-0.0117188   -0.0351563  -0.0481771  -0.0195313 
-0.00390625  -0.0117188  -0.0195313  -0.0169271 

julia> A = matrixdepot("deriv2", Float32, 4)
4x4 Array{Float32,2}:
-0.0169271   -0.0195313  -0.0117188  -0.00390625
-0.0195313   -0.0481771  -0.0351563  -0.0117188 
-0.0117188   -0.0351563  -0.0481771  -0.0195313 
-0.00390625  -0.0117188  -0.0195313  -0.0169271 


julia> r = matrixdepot("deriv2", 3, false) # generate the test problem
Test problems for Regularization Method
A:
3x3 Array{Float64,2}:
-0.0277778   -0.0277778  -0.00925926
-0.0277778   -0.0648148  -0.0277778 
-0.00925926  -0.0277778  -0.0277778 
b:
[-0.01514653483985129,-0.03474793286789414,-0.022274315940957783]
x:
[0.09622504486493762,0.28867513459481287,0.48112522432468807]

julia> r.A  # generate the matrix A
3x3 Array{Float64,2}:
-0.0277778   -0.0277778  -0.00925926
-0.0277778   -0.0648148  -0.0277778 
-0.00925926  -0.0277778  -0.0277778 

Here is a list of test problems in the collection:

• baart
• blur
• deriv2
• foxgood
• gravity
• heat
• phillips
• shaw
• spikes
• ursell
• wing

ursell

Discretization of a Fredholm integral equation of the first kind with kernel K and right-hand side g given by

$$K(s,t) = \frac{1}{s+t+1}, \quad g(s) = 1,$$

where both integration intervals are [0, 1] [ursell].

spikes

Artificially generated discrete ill-posed problem.

gravity

One-dimensional gravity surveying model problem. Discretization of a 1-D model problem in gravity surveying, in which a mass distribution f(t) is located at depth d, while the vertical component of the gravity field g(s) is measured at the surface. The resulting problem is a first-kind Fredholm integral equation with kernel

K(s, t) = d(d² + (s − t)²)^− 3/2.

blur

Image deblurring test problem. It arises in connection with the degradation of digital images by atmospheric turbulence blur, modelled by a Gaussian point-spread function

h(x,y) = frac{1}{2pisigma^2}exp(-frac{x^2+y^2}{2sigma^2}).

The matrix A is a symmetric n² × n² doubly block Toeplitz matrix, stored in sparse format.

heat

Inverse heat equation [carasso82]. It is a Volterra integral equation of the first kind with integration interval [0, 1]. The kernel K is given by

K(s, t) = k(s − t),

where

k(t) = frac{t^{-3/2}}{2kappa sqrt{pi}}expbig(-frac{1}{4kappa^2t}big).

κ controls the ill-conditioning of the matrix A. κ = 1 (default) gives an ill-conditioned matrix and κ = 5 gives a well-conditioned matrix.

baart

Discretization of an artificial Fredholm integral equation of the first kind [baart82]. The kernel K is given by

K(s, t) = exp (scos (t)).

The right-hand side g and the solution f are given by

$$g(s)=2\frac{\sin (s)}{s}, \quad f(t) = \sin(t).$$

phillips

Phillips's "famous" problem. Discretization of the "famous" Fredholm integral equation of the first kind deviced by D.L. Phillips [phillips62]. The kernel K and solution f are given by

K(s,t) = theta(s-t), quad f(t) = theta(t),

where

theta(x) = begin{cases}

1+cos(frac{pi x}{3}), & < 3, \ 0, & geq 3. \

end{cases}

The right-hand side g is given by

$$g(s) = (6 - |s|)\Big( 1 + \frac{1}{2}\cos\big(\frac{\pi s}{3}\big)\Big) + \frac{9}{2 \pi}\sin\Big(\frac{\pi |s|}{3}\Big).$$

Both integration intervals are [ − 6, 6].

foxgood

A severely ill-posed problem suggested by Fox & Goodwin. This is a model problem which does not satisfy the discrete Picard condition for the small singular values [baker77].

wing

A problem with a discontinuous solution. The kernel K is given by

K(s,t) = t exp(-st^2),

with both integration intervals are [0, 1]. The functions f and g are given as

f(t) = begin{cases}

1, quad t_1 < t < t_2, \

0, quad mbox{otherwise},\

end{cases}

quad g(s) = frac{exp(-st_1^2) - exp(-st_2^2)}{2s}.

Here 0 < t₁ < t₂ < 1. The matrix A and two vectors x and b are obtained by Galerkin discretization with orthonormal basis functions defined on a uniform mesh.

shaw

One-dimensional image restoration model. This test problem uses a first-kind Fredholm integral equation to model a one-dimensional image restoration situation. The kernel K is given by

$$K(s,t) = (\cos(s)+\cos(t))^2\big(\frac{\sin(u)}{u}\big)^2,$$

where

u = π(sin (s) + sin (t)).

Both integration intervals are [ − π/2, π/2]. The solution f is given by

f(t) = a₁exp ( − c₁(t − t₁)²) + a₂exp ( − c₂(t − t₂)²).

K and f are discretized by simple quadrature to produce the matrix A and the solution vector x. The right-hand b is computed by b = Ax.

deriv2

Computation of the second derivative. The kernel K is Green's function for the second derivative

$$\begin{aligned} K(s,t) = \begin{cases} s(t - 1), \quad s < t, \\\ t(s - 1), \quad s \geq t, \\\ \end{cases} \end{aligned}$$

and both integration intervals are [0, 1]. The function g and f are given by

g(s) = (s³ − s)/6, f(t) = t.

The symmetric matrix A and vectors x and b are computed from K, f and g using the Galerkin method.