6 papers
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For an…
Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
Sachin Garg, Michał Dereziński
The Nyström method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed s…
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
Michał Dereziński, Aaron Sidford
We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for large singular values. For solving su…
Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
Pratik Rathore, Zachary Frangella, Sachin Garg +3
Gaussian processes (GPs) play an essential role in biostatistics, scientific machine learning, and Bayesian optimization for their ability to provide probabilistic predictions and…
Randomized Kaczmarz Methods with Beyond-Krylov Convergence
Michał Dereziński, Deanna Needell, Elizaveta Rebrova +1
Randomized Kaczmarz methods form a family of linear system solvers which converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some c…
Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
An oblivious subspace embedding is a random matrix such that, for any -dimensional subspace, with high probability preserves the norms of all vectors in that…