Ainesh Bakshi

STOC Conference 2025 Conference Paper

Learning the Closest Product State

• Ainesh Bakshi
• John Bostanci
• William Kretschmer
• Zeph Landau
• Jerry Li 0001
• Allen Liu
• Ryan O'Donnell
• Ewin Tang

STOC Conference 2025 Conference Paper

Sample-Optimal Private Regression in Polynomial Time

• Prashanti Anderson
• Ainesh Bakshi
• Mahbod Majid
• Stefan Tiegel

We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure). We provide the first sample-optimal polynomial time algorithm for this task under both pure and approximate differential privacy. We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds. Additionally, our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers. In contrast, all prior efficient algorithms either incurred sample complexities with sub-optimal dimension dependence, scaling with the condition number of the covariates, or obtained a polynomially worse dependence on the privacy parameters. Our technical contributions are two-fold: first, we leverage resilience guarantees of Gaussians within the sum-of-squares framework. As a consequence, we obtain efficient sum-of-squares algorithms for regression with optimal robustness rates and sample complexity. Second, we generalize the recent robustness-to-privacy framework of Hopkins, Kamath, Majid, and Narayanan to account for the geometry induced by the covariance of the input samples. This framework crucially relies on the robust estimators to be sum-of-squares algorithms, and combining the two steps yields a sample-optimal private regression algorithm. We believe our techniques are of independent interest, and we demonstrate this by obtaining an efficient algorithm for covariance-aware mean estimation, with an optimal dependence on the privacy parameters.

SODA Conference 2024 Conference Paper

An Improved Classical Singular Value Transformation for Quantum Machine Learning

• Ainesh Bakshi
• Ewin Tang

FOCS Conference 2024 Conference Paper

Efficient Certificates of Anti-Concentration Beyond Gaussians

• Ainesh Bakshi
• Pravesh K. Kothari
• Goutham Rajendran
• Madhur Tulsiani
• Aravindan Vijayaraghavan

A set of high dimensional points X $= \{x_{1}, x_{2}, \ldots, x_{n}\}\subseteq \mathbb{R}^{d}$ in isotropic position is said to be $\delta$ -anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $\left|\left\langle x_i, v\right\rangle\right| \leqslant \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, three recent works [7], [44], [71] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distri-butions [52], the aforementioned approach has been limited only to rotationally invariant distributions (and their affine transformations) with the only prominent example being Gaussian distributions. This work presents a new (and arguably the most natural) formulation for anti- concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over $L_{p}$ balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e. g. , list-decodable learning and clustering, to such distributions. As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy. However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial. Our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program. From a technical standpoint, unlike existing works that explicitly construct sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.

FOCS Conference 2024 Conference Paper

High-Temperature Gibbs States are Unentangled and Efficiently Preparable

• Ainesh Bakshi
• Allen Liu
• Ankur Moitra
• Ewin Tang

We show that thermal states of local Hamiltonians are separable above a constant temperature. Specifically, for a local Hamiltonian $H$ on a graph with degree $\mathfrak{g}$, its Gibbs state at inverse temperature $\beta$, denoted by $\rho=e^{-\beta H}/\text{tr}(e^{-\beta H})$, is a classical distribution over product states for all $\beta < 1/ (c \mathfrak{{g}})$, where $c$ is a constant. This sudden death of thermal entanglement upends conventional wisdom about the presence of short-range quantum correlations in Gibbs states. Moreover, we show that we can efficiently sample from the distribution over product states. In particular, for any $\beta < 1/(c\mathfrak{g}^{3})$, we can prepare a state $\varepsilon$ -close to $\rho$ in trace distance with a depth-one quantum circuit and $\text{poly}(n)\log(1/\varepsilon)$ classical overhead. 1 1 In independent and concurrent work, Rouzé, França, and Alhambra [37] obtain an efficient quantum algorithm for preparing high-temperature Gibbs states via a dissipative evolution.

STOC Conference 2024 Conference Paper

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time

• Ainesh Bakshi
• Allen Liu
• Ankur Moitra
• Ewin Tang

FOCS Conference 2024 Conference Paper

Structure Learning of Hamiltonians from Real-Time Evolution

• Ainesh Bakshi
• Allen Liu
• Ankur Moitra
• Ewin Tang

We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply $e^{-\mathrm{i}Ht}$ for an unknown local Hamiltonian $H=\Sigma_{a=1}^{m}\lambda_{a}E_{a}$ on $n$ qubits, the goal is to recover $H$. This problem is already well-understood under the assumption that the interaction terms, $E_{a}$, are given, and only the interaction strengths, $\lambda_{a}$, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to $\varepsilon$ error with total evolution time $\mathcal{O}(\log(n)/\varepsilon)$, and has the following appealing properties: 1)It does not need to know the Hamiltonian terms; 2)It works beyond the short-range setting, extending to any Hamiltonian $H$ where the sum of terms interacting with a qubit has bounded norm; 3)It evolves according to $H$ in constant time $t$ increments, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy $\varepsilon$ with total evolution time beating the standard limit of $1/\varepsilon^{2}$.

STOC Conference 2023 Conference Paper

A New Approach to Learning Linear Dynamical Systems

• Ainesh Bakshi
• Allen Liu
• Ankur Moitra
• Morris Yau

FOCS Conference 2023 Conference Paper

Krylov Methods are (nearly) Optimal for Low-Rank Approximation

• Ainesh Bakshi
• Shyam Narayanan

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: \begin{equation*}\min _{\|u\|_{2}=1}\left\|A\left(I-u u^{\top}\right)\right\|_{\mathcal{S}_{p}}\end{equation*}where $\|M\|_{\mathcal{S}_{p}}$ denotes the $\ell_{p}$ norm of the singular values of M. Given $\varepsilon\gt 0$, our goal is to output a unit vector v such that \begin{equation*}\left\|A\left(I-v v^{\top}\right)\right\|_{\mathcal{S}_{p}} \leqslant\left(1+\varepsilon\right) \min _{\|u\|_{2}=1}\left\|A\left(I-u u^{\top}\right)\right\|_{\mathcal{S}_{p}}\end{equation*}Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal 1 number of matrix-vector products for Spectral $(p=\infty)$, Frobenius $(p=2)$ and Nuclear $(p=1)$ LRA. In particular, for Spectral LRA, we show that any algorithm requires $\Omega\left(\log (n) / \varepsilon^{1 / 2}\right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods [40]. Our lower bound addresses Open Question 1 in [59], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1. 2 in [5]. Next, we show that for any fixed constant p, i. e. $1 \leqslant p=O(1)$, there is an upper bound of $O\left(\log (1 / \varepsilon) / \varepsilon^{1 / 3}\right)$ matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the $O\left(\log (n / \varepsilon) / \varepsilon^{1 / 3}\right)$ bound recently obtained in [5], and matches their $\Omega\left(1 / \varepsilon^{1 / 3}\right)$ lower bound, to a $\log (1 / \varepsilon)$ factor. 1 For Spectral LRA, the upper and lower bounds match up to a fixed universal constant. For Frobenius and Nuclear LRA, they match up to a $\log (1 / \varepsilon)$ factor.

NeurIPS Conference 2023 Conference Paper

Near-Linear Time Algorithm for the Chamfer Distance

• Ainesh Bakshi
• Piotr Indyk
• Rajesh Jayaram
• Sandeep Silwal
• Erik Waingarten

For any two point sets $A, B \subset \mathbb{R}^d$ of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as $\texttt{CH}(A, B)=\sum_{a \in A} \min_{b \in B} d_X(a, b)$, where $d_X$ is the underlying distance measure (e. g. , the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward $O(d n^2)$-time brute force algorithm. Further, Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first $(1+\epsilon)$-approximate algorithm for estimating Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\epsilon^2)$ and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a $(1+\epsilon)$-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.

ICLR Conference 2023 Conference Paper

Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation

• Ainesh Bakshi
• Piotr Indyk
• Praneeth Kacham
• Sandeep Silwal
• Samson Zhou

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain \emph{subquadratic} time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recently developed Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from \emph{weighted vertex} and \emph{weighted edge sampling} on kernel graphs, \emph{simulating random walks} on kernel graphs, and \emph{importance sampling} on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in \emph{sublinear} (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

ICML Conference 2023 Conference Paper

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems

• Ainesh Bakshi
• Allen Liu
• Ankur Moitra
• Morris Yau

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-series data, using mixture models can lead to a better fit or even a richer understanding of underlying subpopulations represented in the data. In this work we give a new approach to learning mixtures of linear dynamical systems that is based on tensor decompositions. As a result, our algorithm succeeds without strong separation conditions on the components, and can be used to compete with the Bayes optimal clustering of the trajectories. Moreover our algorithm works in the challenging partially-observed setting. Our starting point is the simple but powerful observation that the classic Ho-Kalman algorithm is a relative of modern tensor decomposition methods for learning latent variable models. This gives us a playbook for how to extend it to work with more complicated generative models.

STOC Conference 2022 Conference Paper

Low-rank approximation with 1/ε 1/3 matrix-vector products

• Ainesh Bakshi
• Kenneth L. Clarkson
• David P. Woodruff

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten- p norm. Here, given access to a matrix A through matrix-vector products, an accuracy parameter є, and a target rank k , the goal is to find a rank- k matrix Z with orthonormal columns such that || A ( I − Z Z ⊤ ) || S p ≤ (1+є)min U ⊤ U = I k || A ( I − U U ⊤ ) || S p , where || M || S p denotes the ℓ p norm of the the singular values of M . For the special cases of p =2 (Frobenius norm) and p = ∞ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses Õ( k /√є) matrix-vector products, improving on the naïve Õ( k /є) dependence obtainable by the power method, where Õ(·) suppresses poly(log( dk /є)) factors.

STOC Conference 2022 Conference Paper

Robustly learning mixtures of k arbitrary Gaussians

• Ainesh Bakshi
• Ilias Diakonikolas
• He Jia
• Daniel M. Kane
• Pravesh K. Kothari
• Santosh S. Vempala

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ d , for any fixed k , in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.

ICLR Conference 2021 Conference Paper

Learning a Latent Simplex in Input Sparsity Time

• Ainesh Bakshi
• Chiranjib Bhattacharyya
• Ravindran Kannan
• David P. Woodruff
• Samson Zhou

We consider the problem of learning a latent $k$-vertex simplex $K\in\mathbb{R}^d$, given $\mathbf{A}\in\mathbb{R}^{d\times n}$, which can be viewed as $n$ data points that are formed by randomly perturbing some latent points in $K$, possibly beyond $K$. A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast in this view of learning a latent simplex. Bhattacharyya and Kannan (SODA 2020) give an algorithm for learning such a $k$-vertex latent simplex in time roughly $O(k\cdot\text{nnz}(\mathbf{A}))$, where $\text{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{A}$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $\mathbf{A}$, which holds in many of these applications. Further, we show this assumption is necessary, as otherwise an algorithm for learning a latent simplex would imply a better low rank approximation algorithm than what is known. We obtain a spectral low-rank approximation to $\mathbf{A}$ in input-sparsity time and show that the column space thus obtained has small $\sin\Theta$ (angular) distance to the right top-$k$ singular space of $\mathbf{A}$. Our algorithm then selects $k$ points in the low-rank subspace with the largest inner product (in absolute value) with $k$ carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the $\Theta(k\cdot\text{nnz}(\mathbf{A}))$ running time.

SODA Conference 2021 Conference Paper

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

• Ainesh Bakshi
• Pravesh K. Kothari

In list-decodable subspace recovery, the input is a collection of n points αn (for some α ≪ 1/2) of which are drawn i. i. d. from a distribution D with a isotropic rank r covariance Π∗ (the inliers ) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a O (1/ α ) size list of candidate covariances that contains a close to Π∗. Two recent independent works [56, 3] gave algorithms for this problem that work whenever D satisfies an algorithmic variant of anti-concentration condition (certifiable anticoncentration). The running time of both these algorithms, however, is and the error bounds on ‖Π – Π∗‖ F grow with r (polynomially in r in [56] and logarithmically in [3]) that can be as large as Ω( d ). In this work, we improve on these results on all three fronts: we obtain dimension-independent error in fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a poly(1/ α ) d O (1) time algorithm that outputs a list containing a satisfying. Our result only needs certifiable hypercontractivity of degree 2 polynomials -a condition satisfied by a much broader family of distributions in contrast to certifiable anticoncentration. As a result, in addition to Gaussians, our algorithm applies to uniform distribution on the hypercube and q -ary cubes and arbitrary product distributions with subgaussian marginals. Prior work [56] had identified such distributions as potential hard examples as such distributions do not exhibit strong enough anti-concentration. When D satisfies certifiable anti-concentration, we obtain a stronger error guarantee of for any arbitrary η > 0 in d O (poly(1/ α )+log(1/ η )) time. The proof of the first result uses certifiable hypercontractivity of degree 2 polynomials to give a low-degree sum-of-squares proof of identifiability of the low dimensional structure in the presence of overwhelming fraction of outliers in input data. Our second result relies on a novel bootstrapping of the guarantees from the first with a new exponential error reduction mechanism within SoS along with certifiable anti-concentration. 1

STOC Conference 2021 Conference Paper

Robust linear regression: optimal rates in polynomial time

• Ainesh Bakshi
• Adarsh Prasad

We obtain robust and computationally efficient estimators for learning several linear models that achieve statistically optimal convergence rate under minimal distributional assumptions. Concretely, we assume our data is drawn from a k -hypercontractive distribution and an є-fraction is adversarially corrupted. We then describe an estimator that converges to the optimal least-squares minimizer for the true distribution at a rate proportional to є 2−2/ k , when the noise is independent of the covariates. We note that no such estimator was known prior to our work, even with access to unbounded computation. The rate we achieve is information-theoretically optimal and thus we resolve the main open question in Klivans, Kothari and Meka [COLT’18].

FOCS Conference 2020 Conference Paper

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures

• Ainesh Bakshi
• Ilias Diakonikolas
• Samuel B. Hopkins 0001
• Daniel M. Kane
• Sushrut Karmalkar
• Pravesh K. Kothari

We give the first outlier-robust efficient algorithm for clustering a mixture of k statistically separated d - dimensional Gaussians ( k-GMMs). Concretely, our algorithm takes input an ε-corrupted sample from a k-GMM and outputs an approximate clustering that misclassifies at most k O(k) (ε+η) fraction of the points whenever every pair of mixture components are separated by 1-exp(-poly(k/η)) in total variation distance. This is the statistically weakest possible notion of separation and allows, for e. g. , clustering of mixtures with components with the same mean with covariances differing in a single unknown direction or separated in Frobenius distance. The running time of our algorithm is d poly(k/η). Such results were not known prior to our work, even for k=2. More generally, our algorithms succeed for mixtures of any distribution that satisfies two well-studied analytic assumptions - sum-of-squares certifiable hypercontractivity and anti-concentration. As an immediate corollary, they extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the d-dimensional unit sphere. Even the information theoretic clusterability of separated distributions satisfying our analytic assumptions was not known and is likely to be of independent interest. Our algorithms build on the recent flurry of work relying on certifiable anti-concentration first introduced in [1], [2]. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves giving a low-degree sum-of-squares proof of statements that relate parameter (i. e. mean and covariances) distance to total variation distance by relying only on hypercontractivity and anti-concentration.

FOCS Conference 2020 Conference Paper

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation

• Ainesh Bakshi
• Nadiia Chepurko
• David P. Woodruff

Recently, Musco and Woodruff (FOCS, 2017) showed that given an n×n positive semidefinite (PSD) matrix A, it is possible to compute a (1+ε-approximate relative-error low-rank approximation to A by querying Õ(nk/ε 2. 5 ) entries of A in time Õ(nk/ε 2. 5 +nk ω-1 /ε 2(ω-1) ). They also showed that any relative-error low-rank approximation algorithm must query Ω(nk/ε) entries of A, this gap has since remained open. Our main result is to resolve this question by obtaining an optimal algorithm that queries Õ(nk/ε) entries of A and outputs a relative-error low-rank approximation in Õ(n·(k/ε) ω-1 ) time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent ω is 2. We then extend our techniques to negative-type distance matrices. Here, our input is a pair-wise distance matrix A corresponding to a point set P={x 1, x 2, .. ., x n } such that A i, j =||x i -x j ||2 2. Bakshi and Woodruff (NeurIPS, 2018) showed a bi-criteria, relative-error low-rank approximation for negative-type metrics. Their algorithm queries Õ(nk/ε 2. 5 ) entries and outputs a rank-( k+4) matrix. We show that the bi-criteria guarantee is not necessary and obtain an Õ(nk/ε) query algorithm, which is optimal. Our algorithm applies to all distance matrices that arise from metrics satisfying negative-type inequalities, including l 1, l 2, spherical metrics, hypermetrics and effective resistances on a graph. We also obtain faster algorithms for ridge regression. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. We assume that the Frobenius norm of the corruption is bounded. Here, we relax the notion of approximation to additive-error, since it is information-theoretically impossible to obtain a relative-error approximation in this setting. While a sample complexity lower bound precludes sublinear algorithms for arbitrary PSD matrices, we provide the first sublinear time and query algorithms when the corruption on the diagonal entries is bounded. As a special case, we show sample-optimal sublinear time algorithms for low-rank approximation of correlation matrices corrupted by noise.

FOCS Conference 2020 Conference Paper

Testing Positive Semi-Definiteness via Random Submatrices

• Ainesh Bakshi
• Nadiia Chepurko
• Rajesh Jayaram

We study the problem of testing whether a matrix A ∈ \mathbbR n×n with bounded entries ( ||A||∞ ≤ 1) is positive semidefinite (PSD), or ε-far in Euclidean distance from the PSD cone, meaning that, where B\succeq 0 denotes that B is PSD. Our main algorithmic contribution is a non-adaptive tester which distinguishes between these cases using only ~O(1/ε 4 ) queries to the entries of A. 11 Throughout the paper, ~O(·) hides log(1/ε) factors. If instead of the Eucledian norm we considered the distance in spectral norm, we obtain the “ l∞-gap problem”, where A is either PSD or satisfies. For this related problem, we give a ~O(1/ε 2 ) query tester, which we show is optimal up to log(1/ε) factors. Both our testers randomly sample a collection of principal sub-matrices and check whether these sub-matrices are PSD. Consequentially, our algorithms achieve one-sided error: whenever they output that A is not PSD, they return a certificate that A has negative eigenvalues. We complement our upper bound for PSD testing with Eucledian norm distance by giving a ~Ω(1/ε 2 ) lower bound for any non-adaptive algorithm. Our lower bound construction is general, and can be used to derive lower bounds for a number of spectral testing problems. As an example of the applicability of our construction, we obtain a new ~Ω(1/ε 4 ) sampling lower bound for testing the Schatten-1 norm with a εn 1. 5 gap, extending a result of Balcan, Li, Woodruff, and Zhang [11]. In addition, our hard instance results in new sampling lower bounds for estimating the Ky-Fan Norm, and the cost of rank- k approximations, i. e. .

NeurIPS Conference 2018 Conference Paper

Sublinear Time Low-Rank Approximation of Distance Matrices

• Ainesh Bakshi
• David Woodruff

Let $\PP=\{ p_1, p_2, \ldots p_n \}$ and $\QQ = \{ q_1, q_2 \ldots q_m \}$ be two point sets in an arbitrary metric space. Let $\AA$ represent the $m\times n$ pairwise distance matrix with $\AA_{i, j} = d(p_i, q_j)$. Such distance matrices are commonly computed in software packages and have applications to learning image manifolds, handwriting recognition, and multi-dimensional unfolding, among other things. In an attempt to reduce their description size, we study low rank approximation of such matrices. Our main result is to show that for any underlying distance metric $d$, it is possible to achieve an additive error low rank approximation in sublinear time. We note that it is provably impossible to achieve such a guarantee in sublinear time for arbitrary matrices $\AA$, and our proof exploits special properties of distance matrices. We develop a recursive algorithm based on additive projection-cost preserving sampling. We then show that in general, relative error approximation in sublinear time is impossible for distance matrices, even if one allows for bicriteria solutions. Additionally, we show that if $\PP = \QQ$ and $d$ is the squared Euclidean distance, which is not a metric but rather the square of a metric, then a relative error bicriteria solution can be found in sublinear time. Finally, we empirically compare our algorithm with the SVD and input sparsity time algorithms. Our algorithm is several hundred times faster than the SVD, and about $8$-$20$ times faster than input sparsity methods on real-world and and synthetic datasets of size $10^8$. Accuracy-wise, our algorithm is only slightly worse than that of the SVD (optimal) and input-sparsity time algorithms.