research
∙
08/11/2023
Simple Analysis of Priority Sampling
We prove a tight upper bound on the variance of the priority sampling me...
share
research
∙
07/02/2023
Moments, Random Walks, and Limits for Spectrum Approximation
We study lower bounds for the problem of approximating a one dimensional...
research
∙
05/30/2023
Dimensionality Reduction for General KDE Mode Finding
Finding the mode of a high dimensional probability distribution D is a f...
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
∙
01/14/2023
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
We present a new approach for computing compact sketches that can be use...
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
∙
10/24/2022
Active Learning for Single Neuron Models with Lipschitz Non-Linearities
We consider the problem of active learning for single neuron models, als...
research
∙
08/05/2022
A Tight Analysis of Hutchinson's Diagonal Estimator
Let 𝐀∈ℝ^n× n be a matrix with diagonal diag(𝐀) and let 𝐀̅ be 𝐀 with its ...
research
∙
03/14/2022
Fast Regression for Structured Inputs
We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...
research
∙
02/23/2022
Low-memory Krylov subspace methods for optimal rational matrix function approximation
We describe a Lanczos-based algorithm for approximating the product of a...
research
∙
11/09/2021
Active Sampling for Linear Regression Beyond the ℓ_2 Norm
We study active sampling algorithms for linear regression, which aim to ...
research
∙
10/26/2021
Dynamic Trace Estimation
We study a dynamic version of the implicit trace estimation problem. Giv...
research
∙
06/17/2021
Error bounds for Lanczos-based matrix function approximation
We analyze the Lanczos method for matrix function approximation (Lanczos...
research
∙
04/08/2021
Linear and Sublinear Time Spectral Density Estimation
We analyze the popular kernel polynomial method (KPM) for approximating ...
research
∙
04/07/2021
Correlation Sketches for Approximate Join-Correlation Queries
The increasing availability of structured datasets, from Web tables and ...
research
∙
03/30/2021
Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand
In this paper, we make a first attempt to incorporate both commuting dem...
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/22/2020
Graph Learning for Inverse Landscape Genetics
The problem of inferring unknown graph edges from numerical data at a gr...
research
∙
06/14/2020
The Statistical Cost of Robust Kernel Hyperparameter Tuning
This paper studies the statistical complexity of kernel hyperparameter t...
research
∙
06/12/2020
Fourier Sparse Leverage Scores and Approximate Kernel Learning
We prove new explicit upper bounds on the leverage scores of Fourier spa...
research
∙
04/17/2020
Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
In this note we illustrate how common matrix approximation methods, such...
research
∙
12/16/2019
Finding the Mode of a Kernel Density Estimate
Given points p_1, ..., p_n in R^d, how do we find a point x which maximi...
research
∙
11/19/2019
Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers
We study how to estimate a nearly low-rank Toeplitz covariance matrix T ...
research
∙
05/14/2019
Sample Efficient Toeplitz Covariance Estimation
We study the query complexity of estimating the covariance matrix T of a...
research
∙
04/22/2019
Low-Rank Approximation from Communication Complexity
In low-rank approximation with missing entries, given A∈R^n× n and binar...
research
∙
03/28/2019
Faster Spectral Sparsification in Dynamic Streams
Graph sketching has emerged as a powerful technique for processing massi...
research
∙
12/20/2018
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Reconstructing continuous signals from a small number of discrete sample...
research
∙
04/26/2018
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
Random Fourier features is one of the most popular techniques for scalin...
research
∙
04/23/2018
Eigenvector Computation and Community Detection in Asynchronous Gossip Models
We give a simple distributed algorithm for computing adjacency matrix ei...
research
∙
01/23/2018
Learning Networks from Random Walk-Based Node Similarities
Digital presence in the world of online social media entails significant...
research
∙
12/28/2017
Minimizing Polarization and Disagreement in Social Networks
The rise of social media and online social networks has been a disruptiv...
research
∙
05/24/2016
Recursive Sampling for the Nyström Method
We give the first algorithm for kernel Nyström approximation that runs i...
research
∙
02/22/2016