Tim Netzer

Tim Netzer, Daniel Plaumann, Andreas Thom

We consider the problem of writing real polynomials as determinants of symmetric linear matrix polynomials. This problem of algebraic geometry, whose roots go back to the nineteenth century, has recently received new attention from the viewpoint of convex optimization. We relate the question to sums of squares decompositions of a certain Hermite matrix. If some power of a polynomial admits a definite determinantal representation, then its Hermite matrix is a sum of squares. Conversely, we show how a determinantal representation can sometimes be constructed from a sums-of-squares decomposition of the Hermite matrix. We finally show that definite determinantal representations always exist, if one allows for denominators.

Gemma De las Cuevas, Andreas Klingler, Martha Lewis et al.

To give vector-based representations of meaning more structure, one approach is to use positive semidefinite (psd) matrices. These allow us to model similarity of words as well as the hyponymy or is-a relationship. Psd matrices can be learnt relatively easily in a given vector space $M\otimes M^*$, but to compose words to form phrases and sentences, we need representations in larger spaces. In this paper, we introduce a generic way of composing the psd matrices corresponding to words. We propose that psd matrices for verbs, adjectives, and other functional words be lifted to completely positive (CP) maps that match their grammatical type. This lifting is carried out by our composition rule called Compression, Compr. In contrast to previous composition rules like Fuzz and Phaser (a.k.a. KMult and BMult), Compr preserves hyponymy. Mathematically, Compr is itself a CP map, and is therefore linear and generally non-commutative. We give a number of proposals for the structure of Compr, based on spiders, cups and caps, and generate a range of composition rules. We test these rules on a small sentence entailment dataset, and see some improvements over the performance of Fuzz and Phaser.