Research map / Learning theory and algorithms / Matrix and tensor methods
Sublinear Time Low-Rank Approximation of Distance Matrices
Ainesh Bakshi, David Woodruff
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 |
|---|---|---|---|
| Use recursive additive-error projection-cost preserving sampling | Low-rank approximation of arbitrary metric distance matrices · Arbitrary metric distance matrices | Frobenius squared-error guarantee: \| \mathbf{A} - \mathbf{M} \mathbf{N}^T \|^2_{F} \leq \| \mathbf{A} - \mathbf{A}_k\|^2_{F} + \epsilon \| \mathbf{A} \|^2 | Improved |
| Use coarse norm estimates and recursively sample rows and columns | Low-rank approximation of arbitrary metric distance matrices · Arbitrary metric distance matrices | Running time: \widetilde{O}((m^{1+\gamma} + n^{1+\gamma})\textrm{poly}(k \epsilon^{-1})) | Improved |
| Allow output rank k+4 relative to target rank k | Relative-error low-rank approximation of squared Euclidean distance matrices · Squared Euclidean distance matrices with \mathcal{P} = \mathcal{Q} | Frobenius squared-error guarantee: \|\mathbf{A}-\mathbf{B}\|_F^2 \leq (1+\epsilon)\|\mathbf{A}-\mathbf{A}_k\|_F^2 | Improved |
| Use squared Euclidean distances with equal point sets and allow output rank k+4 | Relative-error low-rank approximation · Squared Euclidean distance matrices with \mathcal{P} = \mathcal{Q} | Running time: n \cdot k \cdot \textrm{poly}(1/\epsilon) | Improved |
Closest papers by meaning
- Faster Linear Algebra for Distance Matrices (NeurIPS 2022 · similarity 0.88)
- Learning-Based Low-Rank Approximations (NeurIPS 2019 · similarity 0.87)
- Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? (NeurIPS 2017 · similarity 0.86)
- Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization (NeurIPS 2024 · similarity 0.84)
- A (1+?)-Approximation for Ultrametric Embedding in Subquadratic Time (AAAI 2025 · similarity 0.84)
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 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.
