Scaling as a source of ill-conditioning in spline systems
by
Garry Newsam
Defence Science and Technology Organisation

When using thin-plate spline interpolation to register images, Skea et al. [A control point mathcing algorithm, Pattern Recognition, 26(2), pp. 269-276, 1993] encountered very ill-conditioned matrices. They also found, however, that simple rescaling from pixel coordinates to the unit interval dramatically improved the conditioning. We explain this by showing that the condition number of the thin plate spline matrix scales as O(s⁴) with a length scaling of s. This is due to an interaction between the special block structure

æ ç ç ç è A B BT 0 ö ÷ ÷ ÷ ø

of spline systems and the fact that the different blocks scale differently with changes in scale. Systems of this general form occur quite frequently; the practical implication is that good practice requires that the aasociated problems be rescaled to the unit interval as a matter of course. Finally, however, we present a more positive result first noted by M.J.D. Powell: the approved way of solving such systems by making use of the QR decomposition of B to construct a reduced system results in a system whose condition number is invariant to rescaling.

Date received: July 17, 1999