CMSA Computer Science for Mathematicians: Testing Positive Semi-Definiteness via Random Submatrices

CMSA EVENTS

Speaker:

Rajesh Jayaram - CMU

Given an n x n matrix A with bounded entries, we study the problem of testing whether A is positive semi-definite (PSD) via only a small number of queries to the entries of A. While in general one must read the entire matrix A to determine if it is PSD, we demonstrate that testing whether A is PSD or ``far'' from PSD (under some norm) is indeed possible with query complexity which only depends on the distance to the PSD cone. This setup is commonly referred to as the property testing framework. We consider two natural norms of n x n matrices: the spectral norm and the Frobenius (Euclidean) norm. We give a query-optimal algorithm for the former, and present new upper and lower bounds for the latter.

Both of these algorithms have a very simple structure: they randomly sample a collection of principal submatrices and check whether these submatrices are PSD.  Thus, our problem can phrased purely as a question in random matrix theory: given a (entry-wise bounded) matrix A which is at distance D (in some norm) from the PSD cone, what is the probability that a random k x k principal submatrix is not PSD? For the spectral norm, this problem can be tightly answered by classical arguments (e.g. scalar valued concentration), however the case of the Euclidean norm appears to be more involved, and will require matrix concentration based arguments.