Testing Positive Semi-Definiteness via Random Submatrices

We study the problem of testing whether a matrix $$\mathbf{A}$ \in $\mathbb{R}$^{n \times n}$withboundedentries($|$\mathbf{A}$|\infty \leq 1$) is positive semi-definite (PSD), or $ϵ$-far in Euclidean distance from the PSD cone, meaning that $\min{$\mathbf{B}$ \succeq 0} |$\mathbf{A}$ - $\mathbf{B}$|_F^2 > \epsilon n^2$,where$$\mathbf{B}$ \succeq 0$denotesthat$$\mathbf{B}$$ is PSD. Our main algorithmic contribution is a non-adaptive tester which distinguishes between these cases using only $\tilde{O}(1\mathrm{/}{ϵ}^4)$ queries to the entries of $\mathbf{A}$. If instead of the Euclidean norm we considered the distance in spectral norm, we obtain the “${\mathrm{\ell }}_{\mathrm{\infty }}$-gap problem”, where $\mathbf{A}$ is either PSD or satisfies ${\min }_{\mathbf{B}⪰0}\mathrm{\parallel }\mathbf{A}-\mathbf{B}{\mathrm{\parallel }}_2>ϵn$. For this related problem, we give a $\tilde{O}(1\mathrm{/}{ϵ}^2)$ query tester, which we show is optimal up to $\log (1\mathrm{/}ϵ)$ 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 $\mathbf{A}$ is not PSD, they return a certificate that $\mathbf{A}$ has negative eigenvalues. We complement our upper bound for PSD testing with Euclidean norm distance by giving a $\tilde{\mathrm{\Omega }}(1\mathrm{/}{ϵ}^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 $\tilde{\mathrm{\Omega }}(1\mathrm{/}{ϵ}^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 [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.