  The runtime for Kernel Partial Least Squares (KPLS) to compute the fit is
quadratic in the number of examples. However, the necessity of obtaining
sensitivity measures as degrees of freedom for model selection or confidence
intervals for more detailed analysis requires cubic runtime, and thus
constitutes a computational bottleneck in real-world data analysis. We propose
a novel algorithm for KPLS which not only computes (a) the fit, but also (b)
its approximate degrees of freedom and (c) error bars in quadratic runtime. The
algorithm exploits a close connection between Kernel PLS and the Lanczos
algorithm for approximating the eigenvalues of symmetric matrices, and uses
this approximation to compute the trace of powers of the kernel matrix in
quadratic runtime.
