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
On this page · 15 sections
- Prerequisites
- The Hook: Many Bodies, One Anomaly
- Forward and Inverse Problems
- Well-Posed and Ill-Posed Problems
- Least Squares
- Under-Determined Problems: Minimum Norm
- Damped Least Squares (Tikhonov Regularisation)
- Linearising a Non-Linear Problem
- Memory Tricks
- Don’t Confuse
- Common Mistakes
- Practice
- Quick Revision Table
- Key Takeaways
- What’s Next
Prerequisites
- Matrices, transposes, inverses, rank and eigenvalues: see Linear Algebra, and especially Inner Product Spaces and Orthonormal Bases for projections and least squares.
- Regression as statisticians see it (Gauss–Markov, BLUE): Linear Models, Regression and Multivariate Analysis.
- Deconvolution as an inverse problem: Filters, Deconvolution and Fractal Analysis.
- Chapter map: Numerical Analysis and Inversion.
The Hook: Many Bodies, One Anomaly
Forward and Inverse Problems
| Forward problem | Inverse problem | |
|---|---|---|
| Given | model parameters \( \mathbf{m} \) (densities, velocities, depths) | observed data \( \mathbf{d} \) (anomalies, travel times) |
| Find | predicted data \( \mathbf{d} = g(\mathbf{m}) \) | the model \( \mathbf{m} \) |
| Character | usually unique and stable | often 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
| Problem | Which condition fails | Why |
|---|---|---|
| Gravity / magnetic source from surface data | uniqueness | equivalent 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 fields | stability | wavenumber \( k \) is amplified by \( e^{k\Delta z} \); short-wavelength noise explodes |
| Deconvolution | stability | dividing by a small spectral amplitude amplifies noise at those frequencies |
| Backward heat equation (initial temperature from present heat flow) | stability | diffusion erases short-wavelength detail irreversibly |
| Under-sampled tomography (cells no ray crosses) | uniqueness | those cells’ slownesses do not affect the data |
Over-, under-, even- and mixed-determined
| Type | Condition | What happens | Standard answer |
|---|---|---|---|
| Even-determined | \( N = M \), \( G \) invertible | exact unique solution | \( \mathbf{m} = G^{-1}\mathbf{d} \) |
| Over-determined | more independent data than unknowns | no exact solution with noisy data | least squares |
| Under-determined | fewer independent data than unknowns | infinitely many exact solutions | minimum-norm solution |
| Mixed-determined | some parameters over-, others under-determined | both 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 --> BMemory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| Forward problem: model to data, usually unique | Inverse problem: data to model, often non-unique | |
| Non-uniqueness (many models fit) | Instability (small data change, large model change) | |
| Over-determined: least squares minimises misfit | Under-determined: minimum norm minimises model length | |
| Ordinary least squares (\( W = I \)) | Weighted least squares (\( W = C_d^{-1} \)) | |
| Damping parameter \( \varepsilon^2 \): stabilises, adds bias | Data weights: express measurement quality | |
| L2 norm: optimal for Gaussian errors | L1 norm: robust to outliers | |
| Upward continuation: stable | Downward 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
- State Hadamard’s three conditions for a well-posed problem.
- Write the normal equations for the least-squares solution of \( G\mathbf{m} = \mathbf{d} \).
- Which is stable: upward or downward continuation of a potential field?
Answers
- Existence, uniqueness, continuous dependence on the data (stability).
- \( G^{\mathsf T}G\,\mathbf{m} = G^{\mathsf T}\mathbf{d} \).
- 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:
- Two different density distributions can produce exactly the same gravity field everywhere outside a closed surface enclosing both.
- If \( N > M \), the least-squares solution is always unique.
- Downward continuation fails Hadamard’s stability condition.
- 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
- True: equivalent sources (for example concentric spheres of equal excess mass).
- False: uniqueness needs \( G \) to have full column rank (rank \( M \)). Dependent rows can leave \( G^{\mathsf T}G \) singular however large \( N \) is.
- True: amplification \( e^{k\Delta z} \) is unbounded as \( k \to \infty \).
- 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
| Idea | Formula or fact |
|---|---|
| Linear inverse problem | \( \mathbf{d} = G\mathbf{m} \), \( G \) is \( N \times M \) |
| Hadamard | existence, uniqueness, stability |
| Classic ill-posed examples | potential-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 / L1 | mean / median; L1 robust |
Key Takeaways
What’s Next
- Gradient and Direct Search, Generalized Inversion, SVD and Global Optimization: how to minimise misfit for non-linear problems, and the SVD view of resolution and null spaces.
- Numerical Analysis and Inversion: Quick Revision.
- Back to the Earth Sciences overview.