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$
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Ramanujan Jul 27 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$ – Alex Ravsky Jul 27 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$ – Maxime Ferreira Da Costa Jul 29 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$ – Maxime Ferreira Da Costa Jul 29 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.