# Testing Positive Semi-Definiteness via Random Submatrices

arXiv: https://arxiv.org/abs/2005.06441 · HTML: https://mlsanity.com/paper/2005.06441/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2020.

## Built on by (most cited first, 3 of 3)

- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)

## Abstract (arXiv)

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.