Testing Positive Semi-Definiteness via Random Submatrices

We study the problem of testing whether a matrix A ∈ ℝn × n with bounded entries (|A|_∞ ≤ 1) is positive semi-definite (PSD), or ε-far in Euclidean distance from the PSD cone, meaning that minB succeq 0 |A - B|F2 > ε n2, 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 tildeO(1/ε4) queries to the entries of A. If instead of the Euclidean norm we considered the distance in spectral norm, we obtain the "ℓ_∞-gap problem", where A is either PSD or satisfies minBsucceq 0 |A- B|2 > ε n. For this related problem, we give a tildeO(1/ε2) query tester, which we show is optimal up to log(1/ε) factors. Our testers randomly sample a collection of principal submatrices and check whether these submatrices 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 Euclidean norm distance by giving a tildeOmega(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 tildeOmega(1/ε4) sampling lower bound for testing the Schatten-1 norm with a ε n1.5 gap, extending a result of Balcan, Li, Woodruff, and Zhang [SODA'19]. In addition, it yields new sampling lower bounds for estimating the Ky-Fan Norm, and the cost of the best rank-k approximation.