Optimal bounds on the positivity of a matrix from a few moments
Gemma de las Cuevas, Tobias Fritz, and Tim Netzer
Contact the author: Please use for correspondence this email.
Submission date: 28. Aug. 2018
MSC-Numbers: 44A50, 47A10, 47A30, 12D15
Keywords and phrases: moment problem, positive semidefinite, positive polynomial, sum of squares
Download full preprint: PDF (627 kB)
In many contexts one encounters Hermitian operators M on a Hilbert space whose dimension is so large that it is impossible to write down all matrix entries in an orthonormal basis. How does one determine whether such M is positive semideﬁnite? Here we approach this problem by deriving asymptotically optimal bounds to the distance to the positive semideﬁnite cone in Schatten p-norm for all integer p ∈ [1,∞), assuming that we know the moments tr(Mk) up to a certain order k = 1,…,m. We then provide three methods to compute these bounds and relaxations thereof: the sos polynomial method (a semideﬁnite program), the Handelman method (a linear program relaxation), and the Chebyshev method (a relaxation not involving any optimization). We investigate the analytical and numerical performance of these methods and present a number of example computations, partly motivated by applications to tensor networks and to the theory of free spectrahedra.