Null space and gradient methods

In applications where we fit $\bold d \approx\bold F \bold x$,there might exist a vector (or a family of vectors) defined by the condition $\bold 0 =\bold F \bold x_{\rm null}$.This family is called a null space. For example, if the operator $\bold F$ is a time derivative, then the null space is the constant function; if the operator is a second derivative, then the null space has two components, a constant function and a linear function, or combinations of them. The null space is a family of model components that have no effect on the data.

When we use the steepest-descent method, we iteratively find solutions by this updating:

$$\begin{eqnarray} \bold x_{i+1} &=& \bold x_i + \alpha \Delta \bold x \\ \bold x_... ...d x_{i+1} &=& \bold x_i + \alpha \bold F'(\bold F\bold x -\bold d)\end{eqnarray}$$ (50) (51) (52)

After we have iterated to convergence, the gradient $\Delta \bold x$ vanishes as does $\bold F'(\bold F\bold x -\bold d)$.Thus, an iterative solver gets the same solution as the theory leading to equation (27).

Suppose that by adding a huge amount of $\bold x_{\rm null}$,we now change $\bold x$and continue iterating. Notice that $\Delta \bold x$ remains zero because $\bold F \bold x_{\rm null}$ vanishes. Thus we conclude that any null space in the initial guess $\bold x_0$will remain there unaffected by the gradient-descent process.

Although finding a basis for the null space would take us too far afield into linear algebra, a more practical goal is to see some members of the null space, if any. To try to see a member of the null space, we take two starting guesses and run our iterative solver for each of them. If the solutions are the same, there is no null space. If the two different solutions differ, say $\bold x_1$ and $\bold x_2$, there will be a null space. Since the residual squared is a convex quadratic function, the two solutions must have the same residual $\bold r$.Subtracting $\bold r = \bold F\bold x_1 - \bold d$ from $\bold r = \bold F\bold x_2 - \bold d$ we find $\bold F(\bold x_1-\bold x_2)=0$,so $\bold x_1-\bold x_2$ is a model in the null space. Adding $\bold x_1-\bold x_2$ to any to any model $\bold x$will not change the theoretical data.

A practical way to learn about the existence of null spaces and their general appearance is simply to try gradient-descent methods beginning from various different starting guesses.