93 citations · 388 across the 44 of their papers we have counts for
4 papers · 1 filter
Toeplitz Low-Rank Approximation with Sublinear Query Complexity
Michael Kapralov, Hannah Lawrence, Mikhail Makarov +2
We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix . In particu…
Near-Linear Sample Complexity for Polynomial Regression
Raphael A. Meyer, Cameron Musco, Christopher Musco +2
We study polynomial regression. Given query access to a function , the goal is to find a degree polynomial such that, for a giv…
Fast Regression for Structured Inputs
Raphael A. Meyer, Cameron Musco, Christopher Musco +2
We study the regression problem, which requires finding that minimizes for a matrix $\mathbf{A}\in\mat…
Low-memory Krylov subspace methods for optimal rational matrix function approximation
Tyler Chen, Anne Greenbaum, Cameron Musco +1
We describe a Lanczos-based algorithm for approximating the product of a rational matrix function with a vector. This algorithm, which we call the Lanczos method for optimal ration…