2018/09/06 by Dino Oglić, Oglic, Dino, Thomas Gärtner +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Tensor decomposition and applications
paper · doi:10.48550/arxiv.1809.02157
openalex publication_date 2018/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We provide the first mathematically complete derivation of the Nyström 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ı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.