11 papers · 1 filter
The matrix-vector complexity of
MichaÅ DereziÅski, Ethan N. Epperly, Raphael A. Meyer
Matrix--vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establ…
Well-Conditioned Oblivious Perturbations in Linear Space
Shabarish Chenakkod, MichaÅ DereziÅski, Xiaoyu Dong +1
Perturbing a deterministic -dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the co…
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…
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…
Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
MichaÅ DereziÅski, Daniel LeJeune, Deanna Needell +1
Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify due to problem-dependent quantities such…