Testing Positive Semi-Definiteness via Random Submatrices

We study the problem of testing whether a matrix A ∈ ×nwith bounded entries ( ||A||∞ ≤ 1) is positive semidefinite (PSD), or ε-far in Euclidean distance from the PSD cone, meaning that , where B0 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.11Throughout 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 εn1.5gap, 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. .