Preconditioning

Next: About this document ... Up: GIANT PROBLEMS Previous: The starting solution matters!

## Null space versus starting solution

The simplest null-space problem has one data point emerging from two model points.

 (47)

The null space is any solution that produces no data. You can add an arbitrary amount of the null space getting another solution as good as the first. Here is the full solution.

 (48)

Iterative methods can neither subtract nor add any null space to your initial solution. It is obvious in this simple case, because the gradient (here the matrix adjoint) dotted into the null-space vector vanishes. Suppose and are matrices, while , , and are vectors. Although more complicated, something similar happens. You can test if an application involves a null space by comparing the results of various starting solutions.

Other traps arise in the world of images. Rarely are we able to iterate to full completion, so we might say, practically speaking, this application has null spaces.'' For example, if we know that zero frequency is theoretically a null space, we would say, The null space contains low frequencies.'' We cannot avoid such issues.

The textbook way of dealing with null spaces is to require the researcher to set up model styling goals (regularizations). Finding such goals demands assumptions from the researcher, assumptions that are often hard to specify. Luckily, there is another path to consider. Thinking more like a physicist, we could choose the initial solution more carefully.

In regression (47) extended to images, we might hope not to have a null-space problem when we begin iterating from , but this is not true. It is a pitfall, which in an application context, took me some years to recognize. Notice what happens the first step you move away from . Your solution becomes a constant times the gradient. The image extension of (47) being:

 (49)

If the operators and resemble filters, it is pretty clear that and are correlated, which physically could be nonsense. We might be trying to discover if and how and are correlated. Or we might wish to demand they be uncorrelated.

I have no general method for you, but offer a suggestion that works for one family of applications and may be suggestive for others. Traditionally, it might happen that is ignored, effectively taking which happens when the data is better explained by alone than by alone. Solve first for without . Call it . Now define a new variable such that . Introducing your innovative concept (estimating ) your regression becomes:

 (50) (51)

Start off from . Like Equation (49), the first step leads to:

 (52)

which is very different from Equation (49), because is very different from . Although we may still have an annoying or inappropriate correlation between and , it is a lot less annoying than a correlation between and .

 Preconditioning

Next: About this document ... Up: GIANT PROBLEMS Previous: The starting solution matters!

2015-05-07