Skip to content

Well- and Ill-Posed Problems and Least Squares

CSIR NET geophysics inversion: forward vs inverse problems, Hadamard well-posedness, non-uniqueness, condition number, least squares, weighting and damping.

  • 17 min read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: Many Bodies, One Anomaly
  3. Forward and Inverse Problems
  4. Well-Posed and Ill-Posed Problems
  5. Least Squares
  6. Under-Determined Problems: Minimum Norm
  7. Damped Least Squares (Tikhonov Regularisation)
  8. Linearising a Non-Linear Problem
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

The Hook: Many Bodies, One Anomaly

Forward and Inverse Problems

Forward problemInverse problem
Givenmodel parameters \( \mathbf{m} \) (densities, velocities, depths)observed data \( \mathbf{d} \) (anomalies, travel times)
Findpredicted data \( \mathbf{d} = g(\mathbf{m}) \)the model \( \mathbf{m} \)
Characterusually unique and stableoften non-unique and unstable

For a linear (or linearised) problem with \( N \) data and \( M \) parameters:

$$\mathbf{d} = G\mathbf{m}, \qquad G \text{ is } N \times M.$$

\( G \) is the data kernel (sensitivity or Jacobian matrix). Example: in straight-ray travel-time tomography, \( G_{ij} \) is the length of ray \( i \) in cell \( j \), and \( m_j \) is the slowness of cell \( j \).

Well-Posed and Ill-Posed Problems

Geophysical examples

ProblemWhich condition failsWhy
Gravity / magnetic source from surface datauniquenessequivalent sources: the same external field from many internal distributions (Gauss’s theorem, equivalent stratum)
Inconsistent travel times (noise)existence (exact)no model fits every datum exactly when \( N > M \) and data contain errors
Downward continuation of potential fieldsstabilitywavenumber \( k \) is amplified by \( e^{k\Delta z} \); short-wavelength noise explodes
Deconvolutionstabilitydividing by a small spectral amplitude amplifies noise at those frequencies
Backward heat equation (initial temperature from present heat flow)stabilitydiffusion erases short-wavelength detail irreversibly
Under-sampled tomography (cells no ray crosses)uniquenessthose cells’ slownesses do not affect the data

Over-, under-, even- and mixed-determined

TypeConditionWhat happensStandard answer
Even-determined\( N = M \), \( G \) invertibleexact unique solution\( \mathbf{m} = G^{-1}\mathbf{d} \)
Over-determinedmore independent data than unknownsno exact solution with noisy dataleast squares
Under-determinedfewer independent data than unknownsinfinitely many exact solutionsminimum-norm solution
Mixed-determinedsome parameters over-, others under-determinedboth difficulties at once (typical tomography)damped least squares or truncated SVD

Counting \( N \) and \( M \) is not enough: what matters is the number of independent equations, the rank of \( G \). Twenty rays all crossing the same two cells in the same proportion still determine only one combination of their slownesses.

Conditioning

Even when \( G \) is square and invertible, the solution may be unstable. The condition number \( \kappa(G) = \frac{\sigma_{\max}}{\sigma_{\min}} \) (ratio of largest to smallest singular value) bounds the amplification of relative errors:

$$\frac{\lVert \delta\mathbf{m} \rVert}{\lVert \mathbf{m} \rVert} \le \kappa(G)\,\frac{\lVert \delta\mathbf{d} \rVert}{\lVert \mathbf{d} \rVert}.$$

A discrete problem with a huge \( \kappa \) is the finite-dimensional face of an ill-posed continuous problem. The singular values themselves are the subject of the next page.

Least Squares

The normal equations

For an over-determined problem, choose \( \mathbf{m} \) to minimise the squared misfit

$$E(\mathbf{m}) = \lVert \mathbf{d} - G\mathbf{m} \rVert^2 = (\mathbf{d} - G\mathbf{m})^{\mathsf T}(\mathbf{d} - G\mathbf{m}).$$

Setting \( \partial E/\partial \mathbf{m} = 0 \):

$$\boxed{G^{\mathsf T}G\,\mathbf{m} = G^{\mathsf T}\mathbf{d}} \qquad \boxed{\mathbf{m}_{\text{est}} = (G^{\mathsf T}G)^{-1}G^{\mathsf T}\mathbf{d}}$$

provided \( G^{\mathsf T}G \) is invertible (\( G \) has full column rank). Geometrically, \( G\mathbf{m}_{\text{est}} \) is the orthogonal projection of \( \mathbf{d} \) onto the column space of \( G \), so the residual vector is orthogonal to every column of \( G \).

Sanity check. Measure one quantity \( N \) times: \( G \) is a column of ones, \( G^{\mathsf T}G = N \), \( G^{\mathsf T}\mathbf{d} = \sum d_i \), and \( m_{\text{est}} = \bar{d} \). The least-squares estimate is the mean.

Straight-line fit

For \( d_i = a + b x_i \), the normal equations are

$$\begin{pmatrix} N & \sum x_i \\ \sum x_i & \sum x_i^2 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \sum d_i \\ \sum x_i d_i \end{pmatrix}.$$

Uncertainty of the estimate

If the data errors are independent with variance \( \sigma_d^2 \), the model covariance is

$$\boxed{C_m = \sigma_d^2\,(G^{\mathsf T}G)^{-1}}.$$

In the example, \( (G^{\mathsf T}G)^{-1} = \frac{1}{20}\begin{pmatrix} 14 & -6 \\ -6 & 4 \end{pmatrix} \). With \( \sigma_d = 0.05 \) s: \( \sigma_b = 0.05\sqrt{4/20} \approx 0.022 \) s/km and \( \sigma_a = 0.05\sqrt{14/20} \approx 0.042 \) s. The negative off-diagonal says the intercept and slope errors are anticorrelated: tilt the line steeper and the intercept drops.

Weighted least squares

When data have different reliabilities, minimise \( (\mathbf{d} - G\mathbf{m})^{\mathsf T}W(\mathbf{d} - G\mathbf{m}) \), usually with \( W = C_d^{-1} \) (inverse data covariance; for independent data, weights \( w_i = 1/\sigma_i^2 \)):

$$\boxed{\mathbf{m}_{\text{est}} = (G^{\mathsf T}WG)^{-1}G^{\mathsf T}W\mathbf{d}}$$

Choosing a norm: L2 versus L1

Least squares minimises the L2 norm of the residual. It is optimal for Gaussian errors but sensitive to outliers, because a residual’s influence grows with its square. Minimising the L1 norm \( \sum \lvert d_i - (G\mathbf{m})_i \rvert \) is robust: for repeated measurements of one quantity, L2 gives the mean and L1 gives the median. Data 10, 11, 12, 13, 40 have mean 17.2 but median 12. L1 problems are solved by linear programming or iteratively reweighted least squares.

Is the fit good enough?

If the model is right and the errors have the stated \( \sigma_i \), the weighted misfit \( \chi^2 = \sum \frac{r_i^2}{\sigma_i^2} \) should be close to its number of degrees of freedom, \( N - M \). Much larger: the model is too simple or the errors are underestimated. Much smaller: you are fitting noise. The discrepancy principle uses exactly this test to stop an iterative inversion or to choose a damping parameter.

Under-Determined Problems: Minimum Norm

With fewer independent data than unknowns, \( G\mathbf{m} = \mathbf{d} \) has infinitely many solutions. Pick the one with the smallest length \( \lVert\mathbf{m}\rVert \) (minimise \( \mathbf{m}^{\mathsf T}\mathbf{m} \) subject to \( G\mathbf{m} = \mathbf{d} \), by Lagrange multipliers):

$$\boxed{\mathbf{m}_{\text{est}} = G^{\mathsf T}(GG^{\mathsf T})^{-1}\mathbf{d}}$$

Minimum length is a choice, not a discovery. Minimising the distance from a reference model \( \lVert \mathbf{m} - \langle\mathbf{m}\rangle \rVert \), or the model’s roughness \( \lVert D\mathbf{m} \rVert \) (with \( D \) a difference operator, giving the smoothest model), are equally valid choices with different answers. Prior information, not the data, decides among them.

Damped Least Squares (Tikhonov Regularisation)

For mixed-determined and ill-conditioned problems, minimise a weighted sum of misfit and model size:

$$\Phi(\mathbf{m}) = \lVert \mathbf{d} - G\mathbf{m} \rVert^2 + \varepsilon^2 \lVert \mathbf{m} \rVert^2 \quad\Rightarrow\quad \boxed{\mathbf{m}_{\text{est}} = (G^{\mathsf T}G + \varepsilon^2 I)^{-1}G^{\mathsf T}\mathbf{d}}$$

This is also called ridge regression or the Levenberg–Marquardt form (on the next page).

  • Adding \( \varepsilon^2 \) to the diagonal makes \( G^{\mathsf T}G + \varepsilon^2 I \) invertible and lifts its small eigenvalues away from zero.
  • \( \varepsilon \to 0 \): ordinary least squares (unstable if \( G^{\mathsf T}G \) is near-singular). \( \varepsilon \to \infty \): \( \mathbf{m} \to 0 \) (stable but ignores the data).
  • Trade-off: larger \( \varepsilon \) means smaller variance but more bias and less resolution. Plotting \( \lVert \mathbf{m} \rVert \) against misfit for many \( \varepsilon \) gives the L-curve; its corner is a common choice. The discrepancy principle (\( \chi^2 \approx N \)) is another.
  • Replacing \( \lVert\mathbf{m}\rVert \) by \( \lVert D\mathbf{m}\rVert \) gives smoothness-constrained (“Occam-type”) inversion, widely used for resistivity and MT.

Linearising a Non-Linear Problem

Most geophysical forward problems are non-linear: travel time depends on the ray path, which depends on the velocities. Expand about a starting model \( \mathbf{m}_0 \):

$$\mathbf{d} \approx g(\mathbf{m}_0) + J\,\Delta\mathbf{m}, \qquad J_{ij} = \frac{\partial g_i}{\partial m_j}.$$

The residual \( \Delta\mathbf{d} = \mathbf{d} - g(\mathbf{m}_0) \) and the Jacobian \( J \) give a linear problem \( \Delta\mathbf{d} = J\Delta\mathbf{m} \), solved by least squares; update the model and repeat. This is the Gauss–Newton method, developed with its relatives on the next page.

graph TD
    A["Starting model m0"] --> B["Forward model: predicted data g(m)"]
    B --> C["Residual d - g(m)"]
    C --> D{"Misfit acceptable? (chi-square near N)"}
    D -->|Yes| E["Stop; assess resolution and uncertainty"]
    D -->|No| F["Jacobian J; solve damped least squares for the update"]
    F --> G["m = m + update"]
    G --> B

Memory Tricks

Don’t Confuse

ThisvsThat
Forward problem: model to data, usually uniqueInverse problem: data to model, often non-unique
Non-uniqueness (many models fit)Instability (small data change, large model change)
Over-determined: least squares minimises misfitUnder-determined: minimum norm minimises model length
Ordinary least squares (\( W = I \))Weighted least squares (\( W = C_d^{-1} \))
Damping parameter \( \varepsilon^2 \): stabilises, adds biasData weights: express measurement quality
L2 norm: optimal for Gaussian errorsL1 norm: robust to outliers
Upward continuation: stableDownward continuation: ill-posed

Common Mistakes

Practice

All questions below are original practice questions written for this page. They are not from any CSIR NET paper.

Level 1: Foundation

  1. State Hadamard’s three conditions for a well-posed problem.
  2. Write the normal equations for the least-squares solution of \( G\mathbf{m} = \mathbf{d} \).
  3. Which is stable: upward or downward continuation of a potential field?
Answers
  1. Existence, uniqueness, continuous dependence on the data (stability).
  2. \( G^{\mathsf T}G\,\mathbf{m} = G^{\mathsf T}\mathbf{d} \).
  3. Upward continuation. It multiplies each wavenumber by \( e^{-k\Delta z} \le 1 \).

Level 2: Part B Style

Practice Q1. Least-squares fitting of \( t = a + bx \) to first arrivals at \( x = 0, 1, 2, 3 \) km with \( t = 1.0, 1.6, 1.9, 2.5 \) s gives a refractor velocity of about:

(a) 1.67 km/s (b) 2.08 km/s (c) 2.50 km/s (d) 3.00 km/s

Answer: (b) 2.08 km/s

Normal equations: \( 4a + 6b = 7.0 \), \( 6a + 14b = 12.9 \). Determinant 20; \( b = \frac{4(12.9) - 6(7.0)}{20} = 0.48 \) s/km. Velocity \( = 1/0.48 \approx 2.08 \) km/s.

Option (a) uses only the first two points (slope 0.6 s/km). The two end points alone would give \( \frac{2.5 - 1.0}{3} = 0.5 \) s/km, or 2.00 km/s. Least squares uses all four points and weights them equally.

Practice Q2. A magnetic anomaly is continued downward by 0.5 km. The amplitude of its 1 km wavelength component is multiplied by about:

(a) 1.4 (b) 4.8 (c) 23 (d) 540

Answer: (c) about 23

\( e^{k\Delta z} = e^{(2\pi/1)(0.5)} = e^{\pi} \approx 23.1 \). Option (a) is the factor for a 10 km wavelength.

Practice Q3. One gravity station is read twice: 10 ± 1 mGal and 13 ± 2 mGal. The weighted least-squares estimate is:

(a) 10.6 mGal (b) 11.0 mGal (c) 11.5 mGal (d) 12.0 mGal

Answer: (a) 10.6 mGal

Weights \( 1/\sigma^2 \): 1 and 0.25. \( \frac{10 + 13(0.25)}{1.25} = 10.6 \) mGal. (b) weights by \( 1/\sigma \) instead of \( 1/\sigma^2 \): \( \frac{10 + 6.5}{1.5} = 11.0 \). (c) is the unweighted mean.

Practice Q4. Five repeat measurements are 10, 11, 12, 13 and 40 (the last a blunder). The L2 (least-squares) and L1 estimates of the quantity are:

(a) 12 and 12 (b) 17.2 and 12 (c) 12 and 17.2 (d) 17.2 and 17.2

Answer: (b) 17.2 and 12

L2 gives the mean, \( \frac{86}{5} = 17.2 \); L1 gives the median, 12. The outlier drags the mean but not the median.

Level 3: Part C Style

Practice Q5. Consider these statements about geophysical inverse problems:

  1. Two different density distributions can produce exactly the same gravity field everywhere outside a closed surface enclosing both.
  2. If \( N > M \), the least-squares solution is always unique.
  3. Downward continuation fails Hadamard’s stability condition.
  4. Deconvolution of a band-limited seismic trace is unstable at frequencies where the wavelet spectrum is near zero.

Which are correct?

(a) 1 and 3 only (b) 1, 3 and 4 only (c) 2 and 4 only (d) 1, 2, 3 and 4

Answer: (b) 1, 3 and 4 only
  1. True: equivalent sources (for example concentric spheres of equal excess mass).
  2. False: uniqueness needs \( G \) to have full column rank (rank \( M \)). Dependent rows can leave \( G^{\mathsf T}G \) singular however large \( N \) is.
  3. True: amplification \( e^{k\Delta z} \) is unbounded as \( k \to \infty \).
  4. True: inverse filtering divides by the wavelet spectrum.

Practice Q6. For \( G = \begin{pmatrix} 1 & 0 \\ 0 & 0.1 \end{pmatrix} \) and \( \mathbf{d} = (1,\ 0.15) \), the damped least-squares solution with \( \varepsilon^2 = 0.01 \) is closest to:

(a) (1.00, 1.50) (b) (0.99, 0.75) (c) (0.99, 1.50) (d) (1.00, 0.15)

Answer: (b) (0.99, 0.75)

\( G^{\mathsf T}G + \varepsilon^2 I = \mathrm{diag}(1.01,\ 0.02) \); \( G^{\mathsf T}\mathbf{d} = (1,\ 0.015) \).

\( m_1 = \frac{1}{1.01} = 0.990 \); \( m_2 = \frac{0.015}{0.02} = 0.75 \).

(a) is the undamped solution; (d) mistakes data for model.

Practice Q7. A linear system has singular values 10 and 0.01. The relative error in the data is 0.1%. The worst-case relative error in the recovered model is about:

(a) 0.1% (b) 1% (c) 10% (d) 100%

Answer: (d) about 100%

\( \kappa = \frac{10}{0.01} = 1000 \). Relative model error \( \le 1000 \times 0.001 = 1 \), that is 100%. The estimate can be entirely noise: the problem needs damping or truncation of the small singular value.

Quick Revision Table

IdeaFormula or fact
Linear inverse problem\( \mathbf{d} = G\mathbf{m} \), \( G \) is \( N \times M \)
Hadamardexistence, uniqueness, stability
Classic ill-posed examplespotential-field sources, downward continuation, deconvolution, backward heat flow
Downward continuation factor\( e^{k\Delta z} \), \( k = 2\pi/\lambda \)
Condition number\( \kappa = \sigma_{\max}/\sigma_{\min} \); relative error amplification
Least squares\( (G^{\mathsf T}G)^{-1}G^{\mathsf T}\mathbf{d} \)
Model covariance\( \sigma_d^2(G^{\mathsf T}G)^{-1} \)
Weighted LS\( (G^{\mathsf T}WG)^{-1}G^{\mathsf T}W\mathbf{d} \), \( W = C_d^{-1} \)
Minimum norm\( G^{\mathsf T}(GG^{\mathsf T})^{-1}\mathbf{d} \)
Damped LS\( (G^{\mathsf T}G + \varepsilon^2 I)^{-1}G^{\mathsf T}\mathbf{d} \)
Good fit\( \chi^2 \approx N - M \) (about \( N \))
L2 / L1mean / median; L1 robust

Key Takeaways

What’s Next