22 citations · 36 across the 5 of their papers we have counts for
5 papers
Oblivious Sketching of High-Degree Polynomial Kernels
Thomas D. Ahle, Michael Kapralov, Jakob B. T. Knudsen +4
Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimens…
Conditional Sparse -norm Regression With Optimal Probability
John Hainline, Brendan Juba, Hai S. Le +1
We consider the following conditional linear regression problem: the task is to identify both (i) a -DNF condition and (ii) a linear rule such that the probability of $c…
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer +3
A central problem in data streams is to characterize which functions of an underlying frequency vector can be approximated efficiently. Recently there has been considerable effort…
Frequent Directions : Simple and Deterministic Matrix Sketching
Mina Ghashami, Edo Liberty, Jeff M. Phillips +1
We describe a new algorithm called Frequent Directions for deterministic matrix sketching in the row-updates model. The algorithm is presented an arbitrary input matrix $A \in R^{n…
Subspace Embeddings and -Regression Using Exponential Random Variables
David P. Woodruff, Qin Zhang
Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real , given a matrix $M \in…