Cover Image

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pham, Ninh, Pagh, Rasmus
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Private Minimum Spanning Trees
by: Pagh, Rasmus, et al.
Published: (2024)

Profile Reconstruction from Private Sketches
by: Wu, Hao, et al.
Published: (2024)

A Smooth Binary Mechanism for Efficient Private Continual Observation
by: Andersson, Joel Daniel, et al.
Published: (2023)

Streaming Private Continual Counting via Binning
by: Andersson, Joel Daniel, et al.
Published: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Daisy Bloom Filters
by: Bercea, Ioana O., et al.
Published: (2022)

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
by: Pagh, Rasmus, et al.
Published: (2024)

PLAN: Variance-Aware Private Mean Estimation
by: Aumüller, Martin, et al.
Published: (2023)

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
by: Chenakkod, Shabarish, et al.
Published: (2026)

Optimal Kernel Orchestration for Tensor Programs with Korch
by: Hu, Muyan, et al.
Published: (2024)

Fast Tensor Completion via Approximate Richardson Iteration
by: Ghadiri, Mehrdad, et al.
Published: (2025)

Approximating Tensor Network Contraction with Sketches
by: Heddes, Mike, et al.
Published: (2026)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
by: Alman, Josh, et al.
Published: (2025)

Fast Sampling Based Sketches for Tensors
by: Swartworth, William, et al.
Published: (2024)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

Approximately Optimal Core Shapes for Tensor Decompositions
by: Ghadiri, Mehrdad, et al.
Published: (2023)

Learning the Positions in CountSketch
by: Li, Yi, et al.
Published: (2023)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Aleph Filter: To Infinity in Constant Time
by: Dayan, Niv, et al.
Published: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

Polynomial-Time Approximability of Constrained Reinforcement Learning
by: McMahan, Jeremy
Published: (2025)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Sampling and Identity-Testing Without Approximate Tensorization of Entropy
by: Gay, William, et al.
Published: (2025)

A Note on Non-Negative $L_1$-Approximating Polynomials
by: Lee, Jane H., et al.
Published: (2026)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Matrix Product Sketching via Coordinated Sampling
by: Daliri, Majid, et al.
Published: (2025)

Optimal Matrix Sketching over Sliding Windows
by: Yin, Hanyan, et al.
Published: (2024)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Improving LSH via Tensorized Random Projection
by: Verma, Bhisham Dev, et al.
Published: (2024)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
by: Larsen, Kasper Green, et al.
Published: (2023)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)