# Visualise Gram sets of nonnegative polynomials in the cone of PSD matrices

I am currently reading Harnessing Sparsity over the Continuum: Atomic Norm Minimisation for Super Resolution by Yuejie Chi and Maxime Ferreira Da Costa. In the box "From Bounded Polynomials to Linear Matrix Inequalities" on page 5 the following plot can be found:

It aims to show that if a trigonometric polynomial $$S$$ is larger than another, $$R$$, everywhere on the unit circle, that for any pair of matrices in their respective Gram sets $$G \in \mathcal{G}(R)$$, $$H \in \mathcal{G}(S)$$, the one belonging to the dominating polynomial, $$H$$, is "more positive semidefinite than the other": $$H \succeq G$$.

Background A (hermitian) trigonometric polynomial is $$R(z) = \sum_{k = -n}^{n} r_k z^{-k},$$ with $$r_{-k} = r_{k}^*$$. Let $$\psi(z) = [1, z, z^2, \ldots, z^{n - 1}]^{\mathsf{T}}$$ and $$\Theta_k$$ be the Hermitian Toeplitz matrix whose $$k$$ diagonal is only ones. A Hermitian matrix $$G$$ is a Gram matrix associated with $$R$$ (denoted by $$G \in \mathcal{G}(R)$$) if $$R(z) = \psi(z^{-1})^{\mathsf{T}} G \psi(z).$$ If $$G \in \mathcal{G}(R)$$, then $$r_k = \text{Tr}(\Theta_k G)$$. A trigonometric polynomial is nonnegative of the unit circle if and only if there exists a positive semidefinite matrix $$G$$ with $$r_k = \text{Tr}(\Theta_k G)$$.

My Question I know that the set of Hermitian positive semidefinite matrices $$C$$ form a proper pointed (i.e. $$C \cap (-C) = \{ 0 \}$$) convex cone, so I understand the yellow cone to be an accurate representation of $$C$$, which is the set from which all Gram matrices come from. But why are the Gram sets $$\mathcal{G}$$ represented as ellipses (and thus connected sets)? Is there a map, which projects $$C$$ onto a proper pointed convex cone in $$\mathbb R^2$$ such that this representation is valid? What about if we only consider $$2 \times 2$$ matrices?

why are the Gram sets $$\mathcal{G}$$ represented as ellipses (and thus connected sets)?

I guess the Gram sets are represented as ovals because those are simple and natural representations of subsets of a set, like Venn diagrams, and they usually do not have a corresponding geometrical interpretation.

But since a space $$\Bbb H_n$$ of all $$n\times n$$ Hermitian matrices is (an $$n^2$$ dimensional) linear space over $$\Bbb R$$, the sets $$\mathcal G(R)$$ have a natural geometrical representation. For each $$G=\|g_{ij}\|\in\Bbb H_n$$ put $$\mathcal R(G)(z)= \psi(z^{-1})^{\mathsf{T}} G \psi(z)=\sum_{1\le i,j\le n} g_{ij}z^{j-i},$$ which is a Hermitian trigonometric polynomial. I guess $$\mathcal R(G)$$ is non-negative on the unit circle iff $$G$$ is positive semidefinite, that is $$G\in C$$. Given a Hermitian trigonometric polynomial $$R$$, a set $$\mathcal G(R)$$ consists of Hermitian $$n\times n$$ matrices $$H$$ such that $$\mathcal R(G)=R$$. Since $$\mathcal R$$ is a linear mapping from $$\Bbb H_n$$ to a space $$\Bbb{Tr}_{n-1}$$ of all Hermitian trigonometric polynomials of “degree” $$n-1$$, a preimage $$\mathcal R^{-1}(R)$$ of each point $$R\in \Bbb{Tr}_{n-1}$$ is an affine subspace of $$\Bbb H_n$$. It has dimension of $$\operatorname{dim}\operatorname{ker}\mathcal R=\operatorname{dim} \Bbb H_n-\operatorname{dim} \Bbb{Tr}_{n-1}=(n-1)^2$$. Thus a set of all positive semidefinite matrices $$G$$ such that $$\mathcal R(G)=R$$ is an intersection of the affine subspace $$\mathcal R^{-1}(R)$$ with the cone $$C$$. How this cone looks like, what shape this intersection can have, and whether can it be elliptical? I guess the shape of the cone $$C$$ can be already studied. Sylvester’s criterion suggests that it can be complicated.

Is there a map, which projects $$C$$ onto a proper pointed convex cone in $$\mathbb R^2$$ such that this representation is valid?

Any linear map $$P$$ from $$\Bbb H_n$$ to $$\Bbb R^2$$ “projects” $$C$$ to a convex cone and keeps affine subspaces, so in this case the intersections are restricted to points, lines, rays, segments or to the whole cone.

What about if we only consider $$2 \times 2$$ matrices?

Already in this case $$G\in C$$ iff $$g_{11}\ge 0$$, $$g_{22}\ge 0$$, and $$g_{11}g_{22}\ge (\operatorname{Re} g_{12})^2+(\operatorname{Im} g_{12})^2$$. This is a four-dimensional shape, so it is hard to visualize it. But since $$\operatorname{dim}\operatorname{ker}\mathcal R=1$$, the intersections $$\mathcal R^{-1}(R)\cap C$$ are at most one-dimensional.

• The reason I ask about the ellipses and $2 \times 2$ matrices is that I have seen $2 \times 2$ matrices represented by ellipses with the half axis lengths determined by their eigenvalues (and one could choose the center of the ellipsis to be $(\lambda_1, \lambda_2)$), where $\lambda_1 \ge \lambda_2$ are the sorted eigenvalues of the Hermitian matrix. Is it true that if $G \preceq H$ the corresponding ellipsis would like in the plot? Jul 27, 2020 at 7:46
• @ViktorGlombik I guess this is a different representation of linear maps of $\Bbb C^n$ given by these matrices in respective basises. Maybe $H \preceq G$ iff the ellipse representing $H$ is contained in the ellipse representing $G$. But here the ellipse is in $\Bbb C^n$ and corresponds to a matrix in $\Bbb H_n$, whereas in the representation from the paper, I guess, the ellipse is a subset of $\Bbb H_n$ consisting of matrices $G$ with the same $\mathcal R(G)$. Jul 27, 2020 at 8:41
• @ViktorGlombik thanks for your interest in our paper. The explainations of Alex Ravsky are correct, and I admit that adding some perspective could have eased its understanding. The yellow cone is meant to represent the cone of PSD matrices. Noticing that the set of matrices $\mathcal{G}(R)$ is an affine subspace of $\mathbb{H}_n$, its intersection with the cone is hereby schematized as a "conic" (an ellipsis, or roughly an oval). Note that this illustration is meant to be a sketch, and that the precise geometry of this intersection can have a complicated geometry that depends on the dimension Jul 29, 2020 at 1:24
• Note that the Bounded Real Lemma states that $R(\tau) \leq S(\tau)$ iff there exist two such matrices $G$ and $H$ such that $G \preceq H$. However, you will not have $G \preceq H$ for any matrix $G \in \mathcal{G}(S)$ and $H \in \mathcal{G}(R)$. Moreover, the property you mentioned can be true in dimension 2, as the trace is invariant across $\mathcal{G}(R)$, so we will have $\lambda_1 + \lambda_2 = 2*R(0) = cst$, and the parametric plot $(\lambda_1, \lambda_2)$ as $H$ describes $\mathcal{G}(R)$ will be a straight line. However, I doubt this could generalize easily in higher dimensions. Jul 29, 2020 at 2:44