  We provide the first mathematically complete derivation of the Nystr\"om
method for low-rank approximation of indefinite kernels and propose an
efficient method for finding an approximate eigendecomposition of such kernel
matrices. Building on this result, we devise highly scalable methods for
learning in reproducing kernel Kre\u{\i}n spaces. The devised approaches
provide a principled and theoretically well-founded means to tackle large scale
learning problems with indefinite kernels. The main motivation for our work
comes from problems with structured representations (e.g., graphs, strings,
time-series), where it is relatively easy to devise a pairwise (dis)similarity
function based on intuition and/or knowledge of domain experts. Such functions
are typically not positive definite and it is often well beyond the expertise
of practitioners to verify this condition. The effectiveness of the devised
approaches is evaluated empirically using indefinite kernels defined on
structured and vectorial data representations.
