research
∙
09/10/2023
Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation
We study the problem of estimating the trace of a matrix 𝐀 that can only...
share
research
∙
05/04/2023
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation
Krylov subspace methods are a ubiquitous tool for computing near-optimal...
research
∙
11/13/2022
Near-Linear Sample Complexity for L_p Polynomial Regression
We study L_p polynomial regression. Given query access to a function f:[...
research
∙
03/14/2022
Fast Regression for Structured Inputs
We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...
research
∙
10/19/2020
Hutch++: Optimal Stochastic Trace Estimation
We study the problem of estimating the trace of a matrix A that can only...
research
∙
06/14/2020