Research map / Learning theory and algorithms / Matrix and tensor methods
The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
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 iid Gaussian projections with an S-Rademacher product and sample rows without replacement | JLT dot-product estimation · JLT | MSE | Helped |
| Use a Gaussian matrix with orthogonal rows instead of iid Gaussian rows | JLT dot-product estimation · JLT | MSE | Helped |
| Use a final complex random diagonal in the S-product projection | S-Rademacher OJLT · JLT | MSE: MSE = 1/2 MSE | Helped |
| Replace unit-circle random phases with values uniform over {1, -1, i, -i} (ablation) | S-Hybrid OJLT · JLT | MSE | No clear effect |
| Use complex random variables in every S-product block (ablation) | S-Hybrid OJLT · JLT | MSE | No clear effect |
| Sample rows with replacement instead of without replacement (ablation) | S-Rademacher OJLT and S-Hybrid OJLT · JLT | MSE: n-1 | Hurt |
| Use an orthogonal Gaussian matrix instead of an iid Gaussian matrix | Angular-kernel random features · Angular kernel | MSE | Helped |
| Use an S-Rademacher matrix instead of an iid Gaussian matrix | Angular-kernel random features · Angular kernel | MSE | Helped |
| Use three S-product blocks rather than fewer blocks (ablation) | S-Rademacher and S-Hybrid embeddings · JLT pointwise and Gram matrix approximation | MSE | Helped |
| Increase the number of S-product blocks beyond three (ablation) | S-Rademacher and S-Hybrid embeddings · JLT pointwise and Gram matrix approximation | MSE | No clear effect |
| Use an odd rather than an even number of S-product blocks (ablation) | S-Rademacher OJLT · JLT | MSE | Helped |
| Use deterministic first-m rows rather than uniform sampling without replacement (ablation) | S-product OJLT · JLT | MSE | No clear effect |
Closest papers by meaning
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.87)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.86)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.85)
- Fourier Sliced-Wasserstein Embedding for Multisets and Measures (ICLR 2025 · similarity 0.84)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.84)
- Node Similarities under Random Projections: Limits and Pathological Cases (ICLR 2025 · 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.