The eigenvalue spread can be computed by an eigendecomposition of R, but this is a time-consuming operation and is hardly ever performed. An
estimate of the eigenvalue spread for the multidimensional-data case is the ratio
between the maximum and the minimum of the magnitude of the Fourier transform of
the input data.
Alternatively, simple inspection of the correlation matrix of the input can
provide an estimation of the time to find a solution. The best possible case is
when R is diagonal, with equal values in the diagonal, because in this case the
eigenvalue spread is 1 and the gradient descent travels in a straight line to the
minimum. We cannot have a faster convergence than this, even when second-order
methods (such as Newton's method, studied later) are used. When R is diagonal but with different values, the ratio of the largest number over
the smallest is a good approximation to the eigenvalue spread. When R is fully populated, the analysis becomes much more difficult.
Use your browser's back button to
return to text.