Next: SCALING THE ADJOINT Up: Preconditioning Previous: Three codes for inverse

# THEORY OF UNDERDETERMINED LEAST-SQUARES

Construct theoretical data with
 (30)
Assume there are fewer data points than model points and that the matrix is invertible. From the theoretical data we estimate a model with
 (31)
To verify the validity of the estimate, insert the estimate (31) into the data modeling equation (30) and notice that the estimate predicts the correct data. Notice that equation (31) is not the same as equation () which we derived much earlier. What's the difference? The central issue is which matrix of and actually has an inverse. If is a rectangular matrix, then it is certain that one of the two is not invertible. (There are plenty of real cases where neither matrix is invertible. That's one reason we use iterative solvers.) Here we are dealing with the case with more model points than data points.

Now we will show that of all possible models that predict the correct data, has the least energy. (I'd like to thank Sergey Fomel for this clear and simple proof that does not use Lagrange multipliers.) First split (31) into an intermediate result and final result:
 (32) (33)
Consider another model ( not equal to zero)
 (34)
which fits the theoretical data .Since ,we see that is a null space vector.
 (35)
First we see that is orthogonal to because
 (36)
Therefore,
 (37)
so adding null space to can only increase its energy. In summary, the solution has less energy than any other model that satisfies the data.

Not only does the theoretical solution have minimum energy, but the result of iterative descent will too, provided that we begin iterations from or any with no null-space component. In (36) we see that the orthogonality does not arise because has any particular value. It arises because is of the form .Gradient methods contribute which is of the required form.

Next: SCALING THE ADJOINT Up: Preconditioning Previous: Three codes for inverse
Stanford Exploration Project
4/27/2004