Test Problems for Regularization Methods

A Fredholm integral equation of the first kind (in one dimension) can be written as

\[\int_0^1 K(s,t) f(t)\, dt = g(s), \quad 0 \leq s \leq 1,\]

where $g$ and the kernel $K$ are known functions and $f$ is the unknown solution. This is a classical linear ill-posed problem: an arbitrarily small perturbation of the data can cause an arbitrarily large perturbation of the solution. In computerized tomography, for example, $K$ is an X-ray source, $f$ is the scanned object and $g$ is the measured damping of the X-rays.

Discretization (by quadrature or the Galerkin method) yields a linear system $Ax = b$. All problems of the group :regprob are derived this way. By default only the matrix is generated; with matrixonly = false as last argument, mdopen returns a descriptor with the matrix A, right-hand side b and solution x:

A = matrixdepot("deriv2", 4)

4×4 Matrix{Float64}:
 -0.0169271   -0.0195312  -0.0117188  -0.00390625
 -0.0195312   -0.0481771  -0.0351562  -0.0117188
 -0.0117188   -0.0351562  -0.0481771  -0.0195312
 -0.00390625  -0.0117188  -0.0195312  -0.0169271

md = mdopen("deriv2", 4, false)
md.x

4-element Vector{Float64}:
 0.0625
 0.1875
 0.3125
 0.4375

Problems

baart

MatrixDepot.baart — Function

Fredholm Integral Equation of the First Kind

Input options:

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

Groups: ["regprob"]

References:

M. L. Baart, The use of auto-correlation for pesudo-rank determination in noisy ill-conditioned linear-squares problems, IMA, J. Numer. Anal. 2 (1982), 241-247.

source

blur

MatrixDepot.blur — Function

Image Deblurring Test Problem

The generated matrix A is an n*n-by-n*n sparse, symmetric, doubly block Toeplitz matrix that models blurring of an n-by-n image by a Gaussian point spread function.

Input options:

[type,] dim, band, σ, [matrixonly]: the dimension of the matrix is dim^2. band is the half-bandwidth, only matrix elements within a distance band-1 from the diagonal are nonzero. σ controls the width of the Gaussin point spread function. The larger the σ, the wider the function and the more ill posed the problem. If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true by default).
[type,] dim, [matrixonly]: band = 3, σ = 0.7.

Groups: ["regprob", "sparse"]

source

deriv2

MatrixDepot.deriv2 — Function

Computation of the Second Derivative

A classical test problem for regularization algorithms: This is a mildly ill-posed problem. It is a discretization of a first kind Fredholm integral equation whose kernel K is the Green's function for the second derivative.

Input options:

[type,] dim, example, [matrixonly]: the dimension of the matrix is dim. One choose between between the following right-hand g and solution f:

    example = 1 gives g(s) = (s^3 - s)/6, f(t) = t.

    example = 2 gives g(s) = exp(s) + (1 -e)s - 1, f(t) = exp(t)

    example = 3 gives  g(s) = | (4s^3 - 3s)/24,  s < 0.5
                              | (-4s^3 + 12s^2 - 9s + 1)/24, s>= 0.5
                       f(t) = | t, t < 0.5
                       f(t) = | 1- t, t >= 0.5.

    If `matrixonly = false`, the matrix A and vectors b and x in the linear system Ax = b will be
    generated (`matrixonly = true` by default).

[type,] dim, [matrixonly]: example = 1.

Groups: ["regprob"]

References:

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

source

foxgood

MatrixDepot.foxgood — Function

Severely Ill-posed Problem Suggested by Fox & Goodwin

This is a model problem discretized by simple quadrature, which does not satifiy the discrete Picard condition for the small singular values.

Input options:

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

Groups: ["regprob"]

References:

C. T. H. Baker, The Numerical Treatment of Integral Equations, Clarendon Press, Oxford, 1977, p. 665.

source

gravity

MatrixDepot.gravity — Function

One-dimensional Gravity Surverying 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.

Input options:

[type,] dim, example, a, b, d, [matrixonly]: dim is the dimension of the matrix. Three examples are implemented.

   (a) example = 1 gives f(t) = sin(π*t) + 0.5*sin(2*π*t).

   (b) example = 2 gives f(t) = piecewise linear function.

   (c) example = 3 gives f(t) = piecewise constant function.

   The t integration interval is fixed to [0, 1], while the s
   integration interval [a, b] can be specified by the user.
   The parameter d is the depth at which the magnetic deposit is
   located. The larger the d, the faster the decay of the singular values.

   If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated
   (matrixonly = true by default).

[type,] dim, example, [matrixonly]: a = 0, b = 1, d = 0.25;
[type,] dim, [matrixonly]: example = 1, a = 0, b = 1, d = 0.25.

Groups: ["regprob"]

References:

G. M. Wing and J. D. Zahrt, A Primer on Integral Equations of the First Kind, Society for Industrial and Applied Mathematics, Philadelphia, 1991, p. 17.

source

heat

MatrixDepot.heat — Function

Inverse Heat Equation

Input options:

[type,] dim, κ, [matrixonly]: dim is the dimension of the matrix and dim must be even. κ controls the ill-conditioning of the matrix. (κ = 5 gives a well-conditioned problem and κ = 1 gives an ill conditoned problem). If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true by default).
[type,] n, [matrixonly]: κ = 1.

Groups: ["regprob"]

References:

A. S. Carasso, Determining surface temperatures from interior observations, SIAM J. Appl. Math. 42 (1982), 558-574.

source

parallax

MatrixDepot.parallax — Function

Stellar Parallax Problem with 26 Fixed, Real Observations

The underlying problem is a Fredholm integral equation of the first kind with kernel

K(s,t) = (1/(σ√(2π)))*exp(-0.5*((s-t)/σ)^2),

with σ = 0.014234, and it is dscretized by means of a Galerkin method with n orthonormal basis functions. The right-hand side b consists of a measured distribution function of stellar parallaxes, and its length is fixed at 26, i.e, the matrix A is 26×n. The exact solution, which represents the true distribution of stellar parallaxes, is unknown.

Input options:

[type,] dim, [matrixonly]: the generated matrix is 26×dim. If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true by default).

Groups: ["regprob"]

References:

W. M. Smart, Stellar Dynamics, Cambridge University Press, Cambridge, (1938), p. 30.

source

phillips

MatrixDepot.phillips — Function

Phillips's "Famous" Problem

Input options:

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

Groups: ["regprob"]

References:

D. L. Phillips, A technique for the numerical solution of certain integral equations of the first kind, J. ACM 9 (1962), 84-97.

source

shaw

MatrixDepot.shaw — Function

One-Dimensional Image Restoration Model

This test problem uses a first-kind Fredholm integral equation to model a one-dimensional image restoration situation.

Input options:

[type,] dim, [matrixonly]: the dimesion of the matrix dim must be even. If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true by default).

Groups: ["regprob"]

References:

C. B. Shaw, Jr., Improvements of the resolution of an instrument by numerical solution of an integral equation. J. Math. Ana. Appl. 37 (1972), 83-112.

source

spikes

MatrixDepot.spikes — Function

Test Problem with "Spike" Solution

Artificially generated discrete ill-posed problem.

Input options:

[type,] dim, tmax, [matrixonly]: dim is the dimension of the matrix. `tmaxcontrols the length of the pulse train. Ifmatrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true` by default). The solution x consists a unit step at t = .5 and a pulse train of spike of decreasing magnitude at t = .5, 1.5, 2.5, ....
[type,] dim, [matrixonly]: t_max = 5.

Groups: ["regprob"]

source

ursell

MatrixDepot.ursell — Function

Integral Equation with No square Integrable Solution

Discretization of a first kind Fredholm integral equation with kernel K and right-hand side g given by K(s,t) = 1/(s+t+1), g(s) = 1, where both integration intervals are [0, 1]. The matrix A is a Hankel matrix.

Input options:

[type,] dim, [matrixonly]: dim is the dimension of the matrix. If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will also be generated (matrixonly = true by default).

Groups: ["regprob"]

References:

F. Ursell, Introduction to the theory of linear integral equations., Chapter 1 in L. M. Delves & J. Walsh, Numerical Solution of Integral Equations, Clarendon Press, 1974.

source

wing

MatrixDepot.wing — Function

A Problem with a Discontinuous Solution

Input options:

[type,] dim, t1, t2, [matrixonly]: the dimension of matrix is dim. t1 and t2 are two real scalars such that 0 < t1 < t2 < 1. If matrixonly = false, the matrix A and vectors b and x in the linear system Ax = b will be generated (matrixonly = true by default).
[type,] n, [matrixonly]: t1 = 1/3 and t2 = 2/3.

Groups: ["regprob"]

References:

G. M. Wing, A Primer on Integral Equations of the First Kind, Society for Industrial and Applied Mathematics, 1991, p. 109.

source