Research map / Learning theory and algorithms / Matrix and tensor methods
Block Subsampled Randomized Hadamard Transform for Nyström Approximation on Distributed Architectures
Oleg Balabanov, Matthias Beaupère, Laura Grigori, Victor Lederer
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 Gaussian sketch with block SRHT in distributed Nyström / tall-skinny sketching | block SRHT sketch · Distributed Nyström approximation (n=65536, 8x8 grid) | runtime of Y=AΩ^T and ΩY: Gaussian up to 2.5x slower | Improved |
| Use block SRHT instead of Gaussian sketch for applying Ω to tall-skinny V | block SRHT sketch · n=10^7, d=200, l=2000, up to p=1536 cores | overall runtime speedup: more than 2.5x speedup | Improved |
| Use block SRHT instead of Gaussian sketch in weak scaling test | block SRHT sketch · n=10^5 x p, l=2000, up to p=1536 | runtime: about 2.5x reduction | Improved |
| Use block SRHT instead of Gaussian sketch for Nyström approximation accuracy | block SRHT sketch · Nyström approximation, MNIST/YearPredictionMSD, trace-norm error | low-rank approximation error | No clear effect |
| Use block SRHT (memory) instead of Gaussian for n=10^8 sketch | block SRHT sketch · n=10^8, l=2000, distributed | feasibility / memory | Improved |
Closest papers by meaning
- Optimal Randomized First-Order Methods for Least-Squares Problems (ICML 2020 · similarity 0.88)
- Improved Subsampled Randomized Hadamard Transform for Linear SVM (AAAI 2020 · similarity 0.88)
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.85)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.85)
- Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization (ICLR 2025 · similarity 0.83)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · 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.
