Research map / Learning theory and algorithms / Matrix and tensor methods
Computationally Efficient Nyström Approximation using Fast Transforms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace uniform/kmeans landmarks with Haar fast-transform structured landmarks (Fast-Nys) | Nystrom kernel approximation · MNIST, Gaussian kernel, and other datasets (Figure 3) | relative kernel approximation error at equal time | Helped |
| Add divide-and-conquer framework to Fast-Nys (DC-Fast-Nys) | kernel SVM prediction · webspam | prediction time relative to linear SVM: 11.21x vs 20.5x for DC-Pred++ at 98.0% vs 98.4% accuracy | Helped |
| Use Haar landmarks with 4x more landmarks at same time budget (ablation) | Fast-Nys (Haar) vs standard Nystrom · MNIST 60k | approximation error: 0.0020 at m=160 vs 0.0063 for Nys at m=40, similar total time | Helped |
| Learn seeds with alternating minimization (structural constraint) vs random seeds (ablation) | Haar Fast-Nys · ijcnn, webspam, magic (Gaussian kernel) | relative kernel approximation error | Helped |
| Haar landmarks instead of Hadamard landmarks (ablation) | Fast-Nys · ijcnn, webspam, magic (Gaussian kernel) | relative kernel approximation error at equal time | Helped |
| Use Hadamard instead of Haar landmarks (lower per-row cost O(m log d) vs O(m) but worse approximation) (ablation) | Fast-Nys · kernel approximation | approximation error at equal time | Hurt |
| Fast-Nys vs standard Nystrom on kernel SVM prediction | kernel SVM prediction (Fast-Nys) · MNIST, Gaussian kernel | prediction time to reach 95% accuracy (relative to linear SVM): about 40x vs more than 80x for second-best method | Helped |
Closest papers by meaning
- Recursive Sampling for the Nystrom Method (NeurIPS 2017 · similarity 0.90)
- Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.86)
- Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method (AAAI 2025 · similarity 0.84)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.84)
- Proxyformer: Nyström-Based Linear Transformer with Trainable Proxy Tokens (AAAI 2024 · similarity 0.83)
- Nyström-Accelerated Primal LS-SVMs: Breaking the $O(an^3)$ Complexity Bottleneck for Scalable ODEs Learning (NeurIPS 2025 · similarity 0.83)
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.