UNDERDETERMINED LEAST-SQUARES

Construct theoretical data with   Assume there are fewer data points than model points and that the matrix is invertible. From the theoretical data we estimate a model $\bold m_0$ with   To verify the validity of the estimate, insert the estimate (31) into the data modeling equation (30) and notice that the estimate $\bold m_0$ predicts the correct data.

Now we will show that of all possible models $\bold m$ that predict the correct data, $\bold m_0$ 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 $\bold m_0$ is orthogonal to because   Therefore,

(37)

so adding null space to $\bold m_0$ 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 $\bold m_0$with no null-space component. In (36) we see that the orthogonality does not arise because has any particular value. It arises because $\bold m_0$ is of the form .Gradient methods contribute which is of the required form.