Imagen de Portada

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Garg, Sachin, Dereziński, Michał
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Distributed Least Squares in Small Space via Sketching and Bias Reduction
por: Garg, Sachin, et al.
Publicado: (2024)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
por: Dereziński, Michał, et al.
Publicado: (2024)

Solving Dense Linear Systems Faster Than via Preconditioning
por: Dereziński, Michał, et al.
Publicado: (2023)

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
por: Dereziński, Michał, et al.
Publicado: (2025)

Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
por: Dereziński, Michał, et al.
Publicado: (2024)

Reweighted Solutions for Weighted Low Rank Approximation
por: Woodruff, David P., et al.
Publicado: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
por: Song, Zhao, et al.
Publicado: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
por: Gopalan, Parikshit, et al.
Publicado: (2024)

A Faster Generalized Two-Stage Approximate Top-K
por: Samaga, Yashas, et al.
Publicado: (2025)

Faster Algorithms for Schatten-p Low Rank Approximation
por: Kacham, Praneeth, et al.
Publicado: (2024)

Randomized Kaczmarz Methods with Beyond-Krylov Convergence
por: Dereziński, Michał, et al.
Publicado: (2025)

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
por: Chenakkod, Shabarish, et al.
Publicado: (2025)

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
por: Chenakkod, Shabarish, et al.
Publicado: (2024)

Optimal Embedding Dimension for Sparse Subspace Embeddings
por: Chenakkod, Shabarish, et al.
Publicado: (2023)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
por: Woodruff, David P., et al.
Publicado: (2024)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
por: Pham, Ninh, et al.
Publicado: (2025)

Faster Graph Embeddings via Coarsening
por: Fahrbach, Matthew, et al.
Publicado: (2020)

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

Towards Universal Convergence of Backward Error in Linear System Solvers
por: Dereziński, Michał, et al.
Publicado: (2026)

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
por: Wolfson, Daniel, et al.
Publicado: (2026)

Well-Conditioned Oblivious Perturbations in Linear Space
por: Chenakkod, Shabarish, et al.
Publicado: (2026)

Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
por: Zhou, Fengqin
Publicado: (2025)

A Faster $k$-means++ Algorithm
por: Liang, Jiehao, et al.
Publicado: (2022)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
por: Mangoubi, Oren, et al.
Publicado: (2024)

Faster Algorithms for Agnostically Learning Disjunctions and their Implications
por: Diakonikolas, Ilias, et al.
Publicado: (2025)

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

Constant-Factor Approximation for the Uniform Decision Tree
por: Szyfelbein, Michał
Publicado: (2026)

Faster and Space Efficient Indexing for Locality Sensitive Hashing
por: Verma, Bhisham Dev, et al.
Publicado: (2025)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
por: Jin, Yujia, et al.
Publicado: (2024)

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
por: Balmaseda, Vicente, et al.
Publicado: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
por: Hayderi, Alexandre, et al.
Publicado: (2024)

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
por: Wiesler, Eleanor, et al.
Publicado: (2026)

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

Consistent Low-Rank Approximation
por: Woodruff, David P., et al.
Publicado: (2026)

Provably Learning from Modern Language Models via Low Logit Rank
por: Golowich, Noah, et al.
Publicado: (2025)

A Characterization of List Regression
por: Pabbaraju, Chirag, et al.
Publicado: (2024)

On Unbiased Low-Rank Approximation with Minimum Distortion
por: Barnes, Leighton Pate, et al.
Publicado: (2025)

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

Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels
por: Aumon, Adrien, et al.
Publicado: (2026)