4
$\begingroup$

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: enter image description here

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?

$\endgroup$
0

1 Answer 1

2
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jul 27, 2020 at 7:46
  • $\begingroup$ @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)$. $\endgroup$ Jul 27, 2020 at 8:41
  • 2
    $\begingroup$ @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 $\endgroup$ Jul 29, 2020 at 1:24
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 29, 2020 at 2:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .