Research map / Learning theory and algorithms / Kernels and regression theory
Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nyström method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a coupled covariance eigenproblem (CCE) that yields asymmetric kernel SVD (KSVD) with infinite-dimensional feature maps, plus an asymmetric Nyström method for speeding it up, evaluated on directed graphs, biclustering, and UCI tasks.
Problem
Existing asymmetric kernel SVD (KSVD) formulations only handle finite-dimensional feature maps, have unbounded variational objectives, and lack empirical evaluation; the Nyström method is also not formalized for asymmetric kernels.
Approach
Define a coupled covariance eigenproblem over two covariance operators in a shared feature space; its solution reduces to the SVD of an asymmetric kernel matrix, enabling infinite-dimensional maps. Derive an asymmetric Nyström approximation from the integral equations of adjoint singular functions.
Key results
- On directed-graph node classification, KSVD (asymmetric SNE kernel) reaches Micro-F1 0.792 on Cora vs 0.776 for SVD and 0.771 for KPCA.
- Asymmetric Nyström solver is fastest among compared SVD solvers, with a 32.51x speedup over RSVD on PubMed at tolerance 1e-1 (0.141 s).
- On biclustering, KSVD achieves NMI 0.68 on ACM and 0.48 on Wiki, outperforming KPCA, SVD, BCOT and EBC on most settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KSVD instead of the strongest listed baseline | Directed-graph node classification · Cora, Citeseer, TwitchPT, and BlogCatalog | Micro-F1: 0.787 -> 0.792; 0.675 -> 0.678; 0.694 -> 0.712; 0.687 -> 0.710 | Helped |
| Use KSVD instead of DiGAE | Directed-graph node classification · Pubmed | Micro-F1: 0.781 -> 0.773 | Hurt |
| Use KSVD instead of the strongest listed baseline | Document clustering · ACM, DBLP, Pubmed, and Wiki | NMI: 0.59 -> 0.68; 0.27 -> 0.28; 0.29 -> 0.33; 0.46 -> 0.48 | Helped |
| Use asymmetric Nyström instead of RSVD | KSVD solver · Cora, Citeseer, and PubMed | runtime (s): 0.274 -> 0.160; 0.290 -> 0.136; 4.577 -> 0.141 | Helped |
| Use KSVD instead of KPCA | Large-scale real-world classification · AmazonCat-13K, Avazu, and Criteo | AUROC: 0.51 -> 0.55; 0.52 -> 0.67; 0.54 -> 0.63 | Helped |
| Use KSVD instead of SVD on degree-2 polynomial features (ablation) | UCI downstream tasks · Diabetes, Ionosphere, and Liver | AUROC: 0.6296 -> 0.7607; 0.7292 -> 0.8374; 0.7032 -> 0.7100 | Helped |
| Use KSVD instead of SVD on degree-2 polynomial features (ablation) | UCI downstream tasks · Cholesterol, Yacht, and Physicochemical-protein | RMSE: 49.0867 -> 49.1592; 15.0002 -> 14.6489; 5.9517 -> 5.4583 | Mixed |
Surprising findings
- Nonlinear preprocessing followed by SVD is competitive with KSVD on some UCI regression targets (e.g., Cholesterol RMSE 49.09 vs 49.16).
Limitations
- Dimensionality compatibility matrix C requires choices (pseudo-inverse, PCA, random, learnable), with no single dominant option.
- Asymmetric Nyström derivation is formal/heuristic with scaling issues; authors note singular values are not needed for feature learning.
- Asymmetry gains are problem-dependent; authors do not claim asymmetric kernels are always superior.
Experimental setup
Datasets: Cora Citeseer Pubmed TwitchPT BlogCatalog ACM DBLP Wiki UCI datasets (Diabetes, Ionosphere, Liver, Cholesterol, Yacht, Physicochemical-protein) AmazonCat-13K Avazu Criteo
Benchmarks: Cora Citeseer Pubmed TwitchPT BlogCatalog ACM DBLP Wiki UCI regression/classification AmazonCat-13K Avazu Criteo
Metrics: Micro-F1 Macro-F1 graph reconstruction l1/l2 norms NMI Coherence ACC RMSE AUROC runtime and speedup
Baselines: PCA SVD KPCA DeepWalk HOPE DiGAE NERD EBC BCOT TSVD RSVD symmetric Nyström
Builds on: KPCA asymmetric kernel SVD (LSSVM-based) symmetric Nyström method SNE kernel
Closest papers by meaning
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.85)
- Self-Attention through Kernel-Eigen Pair Sparse Variational Gaussian Processes (ICML 2024 · similarity 0.84)
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.84)
- High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization (ICML 2024 · similarity 0.84)
- Learning with Exact Invariances in Polynomial Time (ICML 2025 · similarity 0.84)
- Spectrally Transformed Kernel Regression (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.