research
∙
07/13/2023
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Recently Chen and Poor initiated the study of learning mixtures of linea...
share
research
∙
07/06/2023
A Near-Linear Time Algorithm for the Chamfer Distance
For any two point sets A,B ⊂ℝ^d of size up to n, the Chamfer distance fr...
research
∙
04/06/2023
Krylov Methods are (nearly) Optimal for Low-Rank Approximation
We consider the problem of rank-1 low-rank approximation (LRA) in the ma...
research
∙
03/02/2023
An Improved Classical Singular Value Transformation for Quantum Machine Learning
Quantum machine learning (QML) has shown great potential to produce larg...
research
∙
01/23/2023
A New Approach to Learning Linear Dynamical Systems
Linear dynamical systems are the foundational statistical model upon whi...
research
∙
12/01/2022
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Kernel matrices, as well as weighted graphs represented by them, are ubi...
research
∙
02/10/2022
Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products
We study iterative methods based on Krylov subspaces for low-rank approx...
research
∙
05/17/2021
Learning a Latent Simplex in Input-Sparsity Time
We consider the problem of learning a latent k-vertex simplex K⊂ℝ^d, giv...
research
∙
12/03/2020
Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimati...
research
∙
06/29/2020
Robust Linear Regression: Optimal Rates in Polynomial Time
We obtain a robust and computationally efficient estimator for Linear Re...
research
∙
05/13/2020
Testing Positive Semi-Definiteness via Random Submatrices
We study the problem of testing whether a matrix A ∈R^n × n with bounded...
research
∙
05/06/2020
Outlier-Robust Clustering of Non-Spherical Mixtures
We give the first outlier-robust efficient algorithm for clustering a mi...
research
∙
02/12/2020
List-Decodable Subspace Recovery via Sum-of-Squares
We give the first efficient algorithm for the problem of list-decodable ...
research
∙
12/09/2019
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n pos...
research
∙
02/27/2019
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
We study the Maximum Independent Set problem for geometric objects given...
research
∙
11/05/2018
Learning Two Layer Rectified Neural Networks in Polynomial Time
Consider the following fundamental learning problem: given input example...
research
∙
09/19/2018
Sublinear Time Low-Rank Approximation of Distance Matrices
Let P={ p_1, p_2, ... p_n } and Q = { q_1, q_2 ... q_m } be two point se...
research
∙
12/26/2014