PaperlayerView exact revision on arXiv

Source-linked AI summary

Methods of Solving Ill-Posed Problems

Suresh B. Srinivasamurthy

arXiv:1205.5323v1math.NA

TL;DR

Ill-posed operator equations with noisy data require stable numerical approximations. The paper reviews regularization approaches and focuses on the dynamical systems method, which constructs convergent approximations for linear ill-posed problems.

  • Problem

    Ill-posed operator equations with noisy data require numerical algorithms that produce stable approximations as the noise level decreases.

  • Method

    The paper reviews regularization methods and studies the dynamical systems method, which constructs a globally solvable Cauchy problem whose long-time limit is stable.

  • Results

    For linear ill-posed problems with noisy data, the dynamical systems method yields approximations satisfying lim δ→0 ∥uδ(tδ) −y∥= 0 and lim δ→0tδ = ∞.

  • Takeaways & Limitations

    The dynamical systems method provides a stable solution approach for linear ill-posed problems with noisy data.

  • Takeaways & Limitations

    Without additional a priori assumptions on f, convergence of the dynamical systems method can be arbitrarily slow.

Abstract

from arXiv · show

Many physical problems can be formulated as operator equations of the form Au = f. If these operator equations are ill-posed, we then resort to finding the approximate solutions numerically. Ill-posed problems can be found in the fields of mathematical analysis, mathematical physics, geophysics, medicine, tomography, technology and ecology. The theory of ill-posed problems was developed in the 1960's by several mathematicians, mostly Soviet and American. In this report we review the methods of solving ill-posed problems and recent developments in this field. We review the variational regularization method, the method of quasi-solution, iterative regularization method and the dynamical systems method. We focus mainly on the dynamical systems method as it is found that the dynamical systems method is more efficient than the regularization procedure.

A REPORT Submitted in partial fulfillment of the requirements for the degree

The report concerns ill-posed problems and reviews terminology associated with regularization, quasi-solutions, iterative regularization, and dynamical systems methods.

  • The report addresses ill-posed problems as its central topic.
  • It highlights variational regularization, quasi-solutions, iterative regularization, and the dynamical systems method.
  • Key technical terms include regularization parameter, discrepancy principle, and operator equations.

1. Introduction

The introduction defines ill-posed operator equations, explains their sensitivity to data errors, and reviews analytical tools used to study them.

  • A problem is well-posed when existence, uniqueness, and continuous dependence on the data all hold; failure of any condition makes it ill-posed.
  • Small measurement, perturbation, or round-off errors can produce large solution deviations when continuous dependence fails.
  • For injective operators, the inverse is well-defined on the range, while the normal solution is the unique least-norm solution when a null-space is present.
  • An injective compact operator on an infinite-dimensional space has an unbounded inverse, a characteristic source of ill-posedness.
  • Singular Value Decomposition: Singular values quantify ill-posedness: the faster they approach zero, the more ill-posed the problem is.
  • The introduction also presents adjoints, convex functionals, derivatives, spectral theory, and the equivalent normal equation Bu = q.
  • The pseudo-inverse A+ is bounded exactly when the operator is normally solvable and its range is closed.

2. Examples of ill-posed problems

The examples show how noisy data can destabilize differentiation, Laplace Cauchy problems, and first-kind Fredholm integral equations.

  • Numerical differentiation is ill-posed because small perturbations in a function can produce large errors in its derivative.
  • Stable differentiation seeks an operator Rδ whose approximation error tends to zero as the noise level δ tends to zero.
  • For the Laplace Cauchy problem, boundary data can approach zero while the corresponding solution becomes very large for y > 0.
  • The Laplace Cauchy problem is unique but lacks continuous dependence on the data, so it is ill-posed.
  • A first-kind Fredholm equation with a compact operator is ill-posed because compact operators on infinite-dimensional spaces cannot have bounded inverses.

3. Regularizing family

A regularizing family replaces unstable inversion with stable approximations from noisy data, while parameter selection balances perturbation amplification and approximation error.

  • Regularizing family: A regularizing algorithm maps noisy data and a chosen parameter α(δ) to an approximate solution satisfying an error estimate as δ tends to zero.
  • Regularizing family: Under monotonicity assumptions, a suitable α(δ) exists and tends to zero as δ tends to zero.
  • Regularizing family: The regularization parameter can be chosen by minimizing the sum δa(α) + η(α), which balances noisy-data amplification against approximation error.
  • Regularizing family: The resulting regularizer converges to the exact inverse on R(A), yielding a stable approximation.
  • Regularizing family: Regularization applies when the exact inverse is unavailable or unstable, with the parameter α controlling the approximation.
  • Example: A numerical differentiation example constructs a regularizer for an integral formulation using noisy observations.
  • An alternative regularizer definition evaluates uniform approximation over all solutions in a compactum consistent with the noisy data.
  • The chapter reviews variational, quasi-solution, iterative, and dynamical-systems methods for constructing regularizing families.

1. Variational regularization method

Variational regularization solves a penalized minimization problem to obtain stable approximations for ill-posed operator equations. Under the stated assumptions, minimizers exist uniquely and converge to the minimal-norm solution as noise decreases.

  • 1. Variational regularization method: The method minimizes a functional balancing data-fit error and a regularization penalty controlled by α and δ.Solutions of the variational problem are called minimizers.
  • 1. Variational regularization method: For every α>0 and δ>0, the variational problem has a minimizer.
  • 1. Variational regularization method: The minimizer is unique, because the associated normal equation admits no nonzero solution to A∗Aw+αw=0.
  • 1. Variational regularization method: The minimizer satisfies the optimality condition A∗Au−A∗fδ+αu=0.
  • 1. Variational regularization method: If α=α(δ) is chosen under the theorem’s condition, the regularized solutions converge to the minimal-norm solution y as δ→0.
  • 1. Variational regularization method: The regularizer is Rαfδ=(B+α)^−1A∗fδ, with B=A∗A, and is bounded for every α>0.

2. Discrepancy principle for variational regularization method

The discrepancy principle selects the regularization parameter from the observed residual rather than fixing it in advance. Under the stated assumptions, this choice is unique and yields convergence to the minimal-norm solution as noise vanishes.

  • 2. Discrepancy principle for variational regularization method: The discrepancy principle chooses α=α(δ) as the root of ∥Auα,δ−fδ∥=Cδ, with C>1.
  • 2. Discrepancy principle for variational regularization method: Under assumptions (A), the discrepancy equation has a unique α(δ)>0 and α(δ)→0 as δ→0.
  • 2. Discrepancy principle for variational regularization method: The corresponding solutions uδ=uα(δ),δ converge to y, with ∥uδ−y∥→0 as δ→0.
  • 2. Discrepancy principle for variational regularization method: The residual equation can be rewritten using Q=AA∗ as C^2δ^2=∥[Q(Q+α)^−1−I]fδ∥^2.
  • 2. Discrepancy principle for variational regularization method: A minimizer is orthogonal to the null-space of A, so projecting onto N(A)⊥ does not increase the functional.
  • 2. Discrepancy principle for variational regularization method: The discrepancy principle generally does not yield convergence uniform with respect to the data.

3. The method of quasi-solution

Quasi-solution restricts minimization to a compact set K, producing stable approximations for ill-posed equations. With convexity, compactness, injectivity, and strict convexity, existence, uniqueness, continuous dependence, and convergence follow.

  • 3. The method of quasi-solution: The quasi-solution method minimizes ∥Au−fδ∥ over a compact set K.A quasi-solution is defined as a solution to this constrained minimization problem.
  • 3. The method of quasi-solution: If y∈K is a solution, the minimization problem has a stable solution uδ∈K with ∥uδ−y∥→0 as δ→0.
  • 3. The method of quasi-solution: The minimum residual satisfies m(δ)≤δ and therefore tends to zero as the noise level decreases.
  • 3. The method of quasi-solution: Under the theorem’s assumptions, the quasi-solution exists, is unique, and depends continuously on f.
  • 3. The method of quasi-solution: Strict convexity and convexity make the metric projection onto AK unique and continuous, while injectivity transfers this continuity to the quasi-solution.
  • 3. The method of quasi-solution: The approach requires a convex compactum K containing the solution and can use a closed operator instead of a bounded one.

4. Iterative regularization method

Iterative regularization replaces explicit penalization with repeated updates for the transformed equation Bu=q. Noisy-data iterations provide stable approximations, while the iteration count serves as the regularization parameter.

  • 4. Iterative regularization method: The method transforms Au=f into Bu=q=A∗f, where B=A∗A≥0.
  • 4. Iterative regularization method: With noisy data satisfying ∥qδ−q∥≤δ, the iteration constructs a stable approximation to the minimal-norm solution y.
  • 4. Iterative regularization method: The iterative process updates u_n by u_{n+1,δ}=u_{n,δ}−μ(Bu_{n,δ}−qδ).The initial value may be chosen as u0=0.
  • 4. Iterative regularization method: The error obeys ∥γn,δ∥≤∥γn∥+nμδ, and tends to zero as δ→0 under the theorem’s iteration conditions.
  • 4. Iterative regularization method: The regularization parameter is the stopping rule n(δ), the number of iterations, with n(δ)→∞ as δ→0.

5. Dynamical systems method

The dynamical systems method reformulates an operator equation as a Cauchy problem whose trajectory converges to a stable solution. For noisy data, a suitably chosen stopping time provides a convergent approximation.

  • 5. Dynamical systems method: The DSM constructs a Cauchy problem with a unique global solution whose limit is a stable solution of the operator equation.The method is formulated for linear and nonlinear ill-posed problems in a real Hilbert space.
  • 5. Dynamical systems method: The framework assumes an operator equation in a real Hilbert space and permits a solution within an arbitrary ball around a fixed initial element.The solution need not be globally unique.
  • 5. Dynamical systems method: Ill-posedness arises when the derivative operator is not bounded and invertible, whereas well-posedness requires a bounded inverse.The paper also notes that the DSM can be applied to well-posed problems.
  • 5. Dynamical systems method: For noisy data satisfying ∥fδ − f∥≤δ, the DSM solves a perturbed Cauchy problem and evaluates its trajectory at a suitably chosen time tδ.The stopping time acts as the regularization parameter, and typically tδ tends to infinity as δ tends to zero.
  • 5. Dynamical systems method: For linear solvable ill-posed problems with bounded operator norm ∥A∥<1, DSM constructs a stable approximation to the minimal-norm solution from noisy data.The construction uses B=A∗A and q=A∗f in the associated normal equation Bu=q.
  • 5. Dynamical systems method: The linear DSM evolution is ˙u = −u + [B + ǫ(t)]−1q with initial value u0, where ǫ(t) is a decaying scaling parameter.The noisy-data version replaces q with qδ.

3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS

For linear ill-posed equations, DSM yields the minimal-norm solution through a globally solvable dynamical system. With noisy data, an appropriate stopping rule produces approximations converging to that solution, although the noiseless convergence rate can be arbitrarily slow.

  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: DSM stably solves every linear ill-posed problem covered by the stated assumptions using noisy data.The section presents this as its main theorem.
  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: The scaling parameter ǫ(t) is positive, continuous, monotonically decaying to zero, and can be selected within the stated integral condition.One displayed choice links ǫ(t) to the noise level through 2√ǫ(t)=δb, with b∈(0,1).
  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: For any initial approximation u0, the DSM Cauchy problem has a unique global solution and converges to the unique minimal-norm solution y.The initial approximation need not be close to the solution.
  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: With noisy data satisfying ∥f − fδ∥≤δ, a stopping time tδ can be selected so that ∥uδ(tδ) − y∥ tends to zero as δ tends to zero.The theorem also states that tδ tends to infinity.
  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: The stopping time is the DSM regularization parameter and may be chosen by a discrepancy principle or as a root of a prescribed equation.A discrepancy principle sets ∥Auδ(t) − fδ∥=Cδ with C>1 under the stated condition on fδ.
  • 3. DYNAMICAL SYSTEMS METHOD FOR LINEAR PROBLEMS: The noiseless error η(t)=∥u(t)−y∥ tends to zero, but its convergence rate can be arbitrarily slow for suitably chosen f.An a priori assumption on f, such as a source condition, is needed to estimate the rate.
Loading 1205.5323v1…