Research map / Learning theory and algorithms / Matrix and tensor methods
Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method
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 |
|---|---|---|---|
| Exploit polynomial spectral decay with k-DPP sampling | CSSP · Matrices with λ_i between c_1 i^{-p} and c_2 i^{-p} | approximation factor: c γ p | Helped |
| Exploit exponential spectral decay with k-DPP sampling | CSSP · Matrices with λ_i between c_1(1-δ)^i and c_2(1-δ)^i | approximation factor: cγ(1+ δ k) | Helped |
| Use the stable-rank-dependent Master Theorem bound | CSSP with k-DPP · s < k < t_s | approximation factor: (1+2ε)^2 Φ_s(k) | Helped |
| Vary the RBF parameter σ to flatten the spectrum | Nyström approximation on bodyfat · bodyfat | approximation factor | Helped |
| Vary the RBF parameter σ to flatten the spectrum | Nyström approximation on eunite2001 · eunite2001 | approximation factor | Helped |
| Introduce sharp spectral drops around subset sizes | CSSP and Nyström · Subset size k | approximation factor | Hurt |
| Use multiple spectral drops | CSSP and Nyström · Subset size k | approximation factor | Mixed |
| Use a flat spectrum | Nyström approximation on the toy dataset · Toy dataset | approximation factor | Helped |
Closest papers by meaning
- Sampling-based Nyström Approximation and Kernel Quadrature (ICML 2023 · similarity 0.89)
- Linear Time Approximation Algorithm for Column Subset Selection with Local Search (NeurIPS 2024 · similarity 0.88)
- On Socially Fair Low-Rank Approximation and Column Subset Selection (NeurIPS 2024 · similarity 0.88)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.86)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.86)
- Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · similarity 0.85)
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.