# Frames and Combinatorial & Algebraic Geometry

This last week, I attended a workshop at Universitat Bremen on Frames and Combinatorial & Algebraic Geometry. The organizers (Emily King and Eva Maria Feichtner) did a phenomenal job, and I was impressed by the quality of the talks (see this page for the slides). Below are a few of the things that we discussed throughout the workshop:

— Strohmer’s Problem —

At this year’s SampTA conference, Thomas Strohmer posed an interesting frame theory problem during his plenary talk. On the first day of the workshop, Ole Christensen suggested that we study the problem, and it ended up being one of our main focuses. Here’s a technical statement of the problem sans frame-theoretic jargon:

Strohmer’s Problem. Let $A$ be a known $n\times d$ matrix, let $D$ be an unknown $n\times n$ diagonal matrix, and let $X$ be an unknown $d\times m$ matrix. Under what conditions does $y=DAX$ uniquely determine $D$ and/or $X$?

This problem is motivated by the real-world problem of self-calibration (see for example this blog entry). In particular, the columns of $X$ represent unknown test signals, whereas $D$ represents unknown parameters of a linear sensor $DA$. The goal of self-calibration is to calibrate your sensor without requiring knowledge of the input (this is particularly important for applications like deep-space imaging).

Viewing the rows of $DA$ as measurement vectors, then knowing $A$ amounts to knowing the directions of the measurement vectors. By counting degrees of freedom, one can conclude that $m=1$ test signal is insufficient to determine $(D,X)$ without additional information. We therefore seek conditions on $A$ for which one can determine all or almost all pairs $(D,X)$ from $y=DAX$ when $m\geq 2$. We made quite a bit of progress along these lines, and we intend to write up our findings in the coming weeks.

— Necessary conditions for ETF existence —

On Wednesday, I gave a talk that described the state of the literature with several open problems in frame theory. One of these problems concerns necessary conditions on $(M,N)$ for the existence of an $M\times N$ equiangular tight frame (ETF). Indeed, while we have a slew of such conditions in the case where the ETF is real, there is a striking absence of conditions available in the complex case. Last year, Ferenc Szollosi (in this paper) identified 667 polynomials in 12 variables whose complex zero locus contains the $3\times 8$ complex ETFs, and then he leveraged Nullstellensatz:

Nullstellensatz. The complex zero locus of a collection of polynomials $f_1,\ldots,f_k\in\mathbb{C}[x_1,\ldots,x_n]$ is empty if and only if

$1\in\langle f_1,\ldots,f_k\rangle.$

Note that the ($\Leftarrow$) direction above immediately follows from contraposition: Every polynomial in the ideal vanishes on points in the zero locus. Ferenc took about an hour of computer time to establish that 1 forms a Grobner basis for the ideal, thereby establishing the Nullstellensatz condition. Unfortunately, calculating a Grobner basis is often very slow; talking to Ferenc, it seems infeasible to use the same technique to establish nonexistence results for larger values of $N$. This motivates the development of new techniques.

Inspired by some of the work of Pablo Parrilo, I suggested a sum-of-squares program for establishing nonexistence. After discussing more with Cynthia Vinzant, it became clear that my suggestion is actually an instance of a broad collection of techniques which follow from Positivstellensatz. Let $\mathrm{SOS}[x_1,\ldots,x_n]$ denote the cone of polynomials that can be expressed as a sum of squares:

$\mathrm{SOS}[x_1,\ldots,x_n] = \Big\{ \sum_{i}g_i^2 : g_i\in\mathbb{R}[x_1,\ldots,x_n] \Big\}.$

Positivstellensatz. The real zero locus of a collection of polynomials $f_1,\ldots,f_k\in\mathbb{R}[x_1,\ldots,x_n]$ is empty if and only if

$-1\in \mathrm{SOS}[x_1,\ldots,x_n] + \langle f_1,\ldots,f_k\rangle.$

Note that the Nullstellensatz condition implies the P-satz condition, which corresponds to the fact that the complex zero locus contains the real zero locus. Also, the ($\Leftarrow$) direction above similarly follows from contraposition. In the context of ETFs, P-satz is perhaps more appropriate than Nullstellensatz since the algebraic variety defining ETFs is inherently real (this is due to the presence of complex conjugates in the inner products).

While the standard method of testing Nullstellensatz involves computing a Grobner basis, it seems that P-satz is tested by first guessing an upper bound on the degrees of the terms of the desired SOS polynomial (and perhaps even the degrees of the multipliers of the ideal element). After such a truncation, hunting for the expression of -1 can be formulated as a semidefinite program (!). Note that one could similarly truncate to verify the Nullstellensatz condition (thereby avoiding slow Grobner basis calculations), and hunting for the expression of 1 can then be formulated as a linear system. I’ve always heard that real algebraic geometry tends to be harder than algebraic geometry over an algebraically closed field, but the difference between SDPs and linear systems is striking to me.

This research program for ETF nonexistence proofs is still in progress. We encountered some puzzling difficulties with SOSTOOLS, so we are still working to isolate a particular technique to apply, but hopefully, we’ll be able to disprove the existence of $4\times 9$ ETFs in the coming months.

— Eigensteps vs. Proteins —

One of the remaining fundamental problems in frame theory is the Paulsen problem, which asks how far the nearest unit norm tight frame (UNTF) is from a frame which is simultaneously close to being unit norm and close to being tight. I suspect that eigensteps will play a leading role in the eventual solution to this problem.

Recall that the eigensteps of a matrix $\Phi\in\mathbb{C}^{M\times N}$ is the matrix $\Lambda(\Phi)\in\mathbb{R}^{M\times (N+1)}$ whose $j$th column is the spectrum of $\Phi_j\Phi_j^*$, where $\Phi_j$ denotes the matrix of the first $j$ columns of $\Phi$ (here, $j$ runs from $0$ to $N$). By convention, the zeroth column of $\Lambda(\Phi)$ is all zeros. The image of this eigensteps mapping is the so-called eigensteps polytope, defined by interlacing inequalities. Given any point in the eigensteps polytope, one can iteratively produce any point in the preimage of this point by considering the eigenspaces of $\Phi_j\Phi_j^*$ and using the eigenvalues of $\Phi_{j+1}\Phi_{j+1}^*$ to determine the sizes of the components of the $(j+1)$st column of $\Phi$ in terms of these eigenspaces (perhaps surprisingly, all of this has a closed form expression; see Theorem 2 in this paper).

The eigensteps of UNTFs form a subpolytope of the eigensteps polytope, and so a solution to the Paulsen problem will follow from establishing the relationship between distance in $\mathbb{C}^{M\times N}$ and distance in the corresponding eigensteps polytope. Overall, the Paulsen problem motivates the further study of eigensteps (which, by the way, this paper does a fantastic job of pursuing).

The purpose of the workshop was to make connections between communities, but I was shocked to learn of the resemblance between eigensteps and another (independently derived) parameterization of another natural variety of vectors. In particular, Chris Manon gave a chalk talk on one of his papers, in which he parameterizes the set of $n$ unit vectors $\{\varphi_i\}_{i=1}^n\subseteq\mathbb{R}^3$ that sum to zero (think protein configurations; see also this paper and that paper). In particular, one can consider the norms of the partial sums $\mu(\Phi)=\{\|\sum_{i=1}^j \varphi_i\|\}_{j=0}^n$. Then the image of this moment map is a polytope defined by various applications of the triangle inequality. Moreover, given a generic point in this polytope, one may iteratively find any member of the preimage by picking $\varphi_{j+1}$ to lie in the circle of points which are 1 away from $\varphi_j$ and $\mu_{j+1}$ away from the origin (one has to be more careful if an intermediate $\mu_j$ happens to be zero).

Discussing with Chris, it sounds like we might learn a lot about UNTFs by somehow passing to toric geometry, where mathematical technology is advanced enough to observe certain important features. I’m definitely interested to see if this identification bears fruit.

— Dan Edidin’s Smoothie Problem —

Dan Edidin gave a talk on his recent paper about phase retrieval with projections. This paper discusses conditions for injectivity in mappings of the form $x\bmod\{\pm1\}\mapsto\{\|P_jx\|\}$, where each $P_j$ is an orthogonal projection operator. (Observe that this reduces to the phase retrieval problem when each $P_j$ has rank 1.) What follows are the main results of his paper:

Theorem 1. $2M-1$ generic rank-deficient projections suffice for injectivity.

Theorem 2. $2M-1$ projections are necessary for injectivity when $M=2^k+1$ for some $k$.

Considering these results, one naturally wonders how many projections are necessary when Theorem 2 doesn’t apply. The first instance of this case is $M=4$, which Zhiqiang Xu studied in this paper. In particular, following the techniques of Cynthia Vinzant, he discovered $6=2M-2$ rank-2 projections which give injectivity. Also, this survey gives that 3-dimensional projective space requires at least 5 euclidean dimensions for an embedding, implying that injectivity is not possible with 4 projections of any rank.

BEGIN EDIT — Dan just reminded me of another of his beautiful results:

Theorem 3. The rank-deficient projections $\{P_i\}$ give injectivity if and only if $\{P_ix\}$ spans $\mathbb{R}^M$ for every nonzero $x$.

With this theorem, it is clear that 4 projections are insufficient in 4 dimensions, since we may pick $x$ from the nullspace of $P_1$— END EDIT

This naturally leads to the following:

Problem. Is it possible for 5 rank-2 projections over $\mathbb{R}^4$ to make the mapping $x\bmod\{\pm1\}\mapsto\{\|P_jx\|\}$ injective?

If you solve this problem, Dan will give you a smoothie. (Apparently, he’s a health nut, so he wouldn’t want to reward someone with Coca-Cola like I did here.)