16 citations · 62 across the 29 of their papers we have counts for
7 papers · 1 filter
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2
Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…
Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi, Allen Liu, Ankur Moitra +1
We study the problem of learning a local quantum Hamiltonian given copies of its Gibbs state at a known inverse temperature . Anshu, Arun…
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra +1
Recently Chen and Poor initiated the study of learning mixtures of linear dynamical systems. While linear dynamical systems already have wide-ranging applications in modeling time-…
A Near-Linear Time Algorithm for the Chamfer Distance
Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram +2
For any two point sets of size up to , the Chamfer distance from to is defined as , whe…
Krylov Methods are (nearly) Optimal for Low-Rank Approximation
Ainesh Bakshi, Shyam Narayanan
We consider the problem of rank- low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: $$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal…
An Improved Classical Singular Value Transformation for Quantum Machine Learning
Ainesh Bakshi, Ewin Tang
We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. QSVT, introduced by [GSLW, STOC'19, arXiv:1806.…
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra +1
Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require kno…