SOFT 2016: Summer of Frame Theory

Posted on by Dustin G. Mixon

This month, several experts in frame theory will be visiting my department, and so Matt Fickus and I decided to organize a workshop in the style of AIM. Considering the recent progress we’ve made on equiangular tight frames (ETFs) — namely, one, two, three, and four — we are hoping this workshop will spur further progress in this area. To kick off the month, I asked a few people to prepare hour-long chalk talks, and what follows are the extended abstracts:

1. Introduction to ETFs (Dustin G. Mixon)

Given a d-dimensional Hilbert space space \mathbb{H}_d and a positive integer n, we are interested in packing n lines through the origin so that the interior angle between any two is as large as possible. It is convenient to represent each line by a unit vector that spans the line, and in doing so, the problem amounts to finding unit vectors \{\varphi_i\}_{i=1}^n that minimize coherence:

\displaystyle{\mu\Big(\{\varphi_i\}_{i=1}^n\Big)=\max_{i\neq j}|\langle \varphi_i,\varphi_j\rangle|.}

This minimization amounts to a nonconvex optimization problem. To construct provably optimal packings, one must prove a lower bound on \mu for a given n and spatial dimension d, and then construct an ensemble which meets equality in that bound. To date, we know of three bounds that are sharp:

  • Trivial bound. \mu\geq0, sharp only if n\leq d
  • Welch bound. \mu\geq\sqrt{\frac{n-d}{d(n-1)}}, sharp only if \displaystyle{n\leq\left\{\begin{array}{cl}d^2&\text{ if }\mathbb{H}_d\text{ is complex}\\\binom{d+1}{2}&\text{ if }\mathbb{H}_d\text{ is real}\end{array}\right.}
  • Orthoplex bound. \mu\geq\frac{1}{\sqrt{d}}, sharp only if n\leq 2(d^2-1)

Of course, equality in the trivial bound occurs precisely when the vectors are orthogonal. It turns out that equality in the Welch bound occurs precisely when there exist constants \alpha and \beta such that

\displaystyle{|\langle \varphi_i,\varphi_j\rangle|=\alpha \text{ whenever }i\neq j \qquad \text{and} \qquad \sum_{i=1}^n\varphi_i\varphi_i^*=\beta\cdot\mathrm{Id}_{\mathbb{H}_d}}.

In words, the ensemble is \alpha-equiangular and \beta-tight, and so we call the ensemble an equiangular tight frame (ETF). Far less is known about ensembles that achieve equality in the orthoplex bound, though Bodmann and Haas have recently made an important stride in this direction.

ETFs were first introduced by Strohmer and Heath in 2003, and in the time since, they have proven to be notoriously difficult to construct. Still, they have found interesting connections with various combinatorial designs, and these connections have been particularly fruitful for constructing new infinite families of ETFs. In this talk we will discuss some of these success stories, paying particular attention to the research programs that led to their discovery.

2. Nonabelian Harmonic ETFs (Joseph W. Iverson)

A classic construction of equiangular tight frames relies on the discrete Fourier transform matrix (DFT) of a finite abelian group G. Each column of the DFT corresponds to an element of G, and each row gives the values of a homomorphism \chi \colon G \to \mathbb{T}, also called a character. In particular, the entries of the DFT are unimodular. The DFT is a scalar multiple of a unitary matrix, so if we pull out any subset of rows, the resulting short, fat matrix will be an equal-norm tight frame. We obtain an equiangular tight frame in this way if and only if the rows we extract correspond to something called a difference set in the dual group (see one, two, three).

Recent papers by the speaker (here) and by Thill and Hassibi (there) suggest a generalization of this procedure for a nonabelian group G. In this setting, we replace characters with irreducible unitary representations \pi \colon G \to U(d), where d is the dimension of the representation and U(d) is the group of d\times d unitary matrices. As in the abelian case, we can list the values of the irreducible representations in one, big matrix M. The only difference is that now it will be convenient to scale the values of \pi \colon G \to U(d) by \sqrt{d}. When G = S_3, for instance, we get a matrix like the following, with \omega=e^{2\pi i/3}:

\displaystyle{M = \begin{pmatrix}\left( 1 \right)&\left( 1 \right)&\left( 1 \right)&\left( 1 \right)&\left( 1 \right)&\left( 1 \right) \\[5 pt] \pmb{\left( 1 \right)}&\pmb{\left( 1 \right)}&\pmb{\left( 1 \right)}&\pmb{\left( -1 \right)}&\pmb{\left( -1 \right)}&\pmb{\left( -1 \right)} \\[5 pt] \hspace{-2 pt}\begin{pmatrix}\pmb{\sqrt{2}} & \hspace{-7 pt}\pmb{0} \\0 & \hspace{-7 pt} \sqrt{2}\end{pmatrix}& \hspace{-9 pt} \begin{pmatrix} \pmb{ \omega \sqrt{2} } & \hspace{-8 pt}\pmb{0} \\ 0 & \hspace{-8 pt}\omega^2 \sqrt{2} \end{pmatrix}&\hspace{-9 pt} \begin{pmatrix} \pmb{ \omega^2 \sqrt{2} } & \hspace{-8 pt}\pmb{0} \\ 0 & \hspace{-8 pt}\omega \sqrt{2} \end{pmatrix}&\hspace{-9 pt} \begin{pmatrix} \pmb{0} & \hspace{-7 pt}\pmb{ \sqrt{2} } \\ \sqrt{2} & \hspace{-7 pt}0 \end{pmatrix}&\hspace{-9 pt} \begin{pmatrix} \pmb{0} & \hspace{-8 pt}\pmb{ \omega\sqrt{2} } \\ \omega^2 \sqrt{2} & \hspace{-8 pt}0 \end{pmatrix}&\hspace{-9 pt} \begin{pmatrix} \pmb{0} & \hspace{-8 pt}\pmb{ \omega^2 \sqrt{2} } \\ \omega \sqrt{2} & \hspace{-8 pt}0 \end{pmatrix} \hspace{-2 pt} \end{pmatrix} \hspace{-3 pt}. }

Like before, we pull out any set of rows:

\displaystyle{\begin{pmatrix}\pmb{\left( 1 \right)}&\pmb{\left( 1 \right)}&\pmb{\left( 1 \right)}&\pmb{\left( -1 \right)}&\pmb{\left( -1 \right)}&\pmb{\left( -1 \right)} \\[5 pt] \begin{pmatrix}\pmb{\sqrt{2}} & \pmb{0}\end{pmatrix}&\begin{pmatrix}\pmb{ \omega \sqrt{2} } & \pmb{0}\end{pmatrix}&\begin{pmatrix} \pmb{ \omega^2 \sqrt{2} } & \pmb{0}\end{pmatrix}&\begin{pmatrix} \pmb{0} & \pmb{ \sqrt{2} }\end{pmatrix}&\begin{pmatrix} \pmb{0} & \pmb{ \omega\sqrt{2} }\end{pmatrix}&\begin{pmatrix} \pmb{0} & \pmb{ \omega^2 \sqrt{2} }\end{pmatrix}\end{pmatrix}.}

Once we collapse the columns, we get an equal-norm tight frame:

\displaystyle{\begin{pmatrix}1 & 1 & 1 & -1 & -1 & -1 \\ \sqrt{2} & \omega\sqrt{2} & \omega^2 \sqrt{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & \sqrt{2} & \omega \sqrt{2} & \omega^2 \sqrt{2} \\ \end{pmatrix}. }

Thill and Hassibi have a way of picking the rows in this process that ensures the resulting frame has low coherence. Let \hat{G} be the set of irreducible representations of G, up to unitary equivalence. Any group of automorphisms H \subset \mathrm{Aut}(G) acts on \hat{G} by precomposition:

(\alpha \cdot \pi)(x) = \pi(\alpha(x)) \qquad (\alpha \in H, \pi \in \hat{G}, x \in G).

Fix an irreducible \pi \in \hat{G}, and let E \subset \hat{G} be the orbit of \pi under the action of H. Now choose all of the rows of M that correspond to the representations in the orbit E, and make the resulting tight frame. The main result of Thill and Hassibi puts an upper bound on the coherence of this frame. In general, these will not be equiangular tight frames, but in at least one (abelian) example, Thill and Hassibi do get an ETF. We will give some updates on the production of ETFs using the row-extraction procedure for nonabelian groups.

3. Polyphase ETFs and abelian generalized quadrangles (Matthew Fickus)

We discuss a new way to construct ETFs which involves signing/phasing the incidence matrix of a balanced incomplete block design (BIBD).  As we’ll see, these phased BIBD ETFs are naturally represented as the columns of a rank-deficient, tall-skinny matrix.  In this form, it will be obvious that these vectors are equiangular but hard to see that they form a tight frame for their span.  This contrasts with many other known constructions of ETFs, such as harmonic ETFs and Steiner ETFs, where tightness is obvious but equiangularity is not.

To date, we have constructed three infinite families of phased BIBD ETFs, and one of these contains an infinite number of new complex ETFs.  For all of these, what we actually construct is a matrix obtained from a BIBD’s incidence matrix by replacing each of its nonzero entries with a monomial in the ring of polynomials (the convolution algebra) over a finite abelian group.  Evaluating the matrices at any nontrivial character of this group produces a phased BIBD ETF.

Being matrices with polynomial entries, any such generalized ETF is an example of a polyphase matrix of a filter bank. As we will explain, the filter banks corresponding to our polyphase BIBD ETFs are closely related to special types of combinatorial designs known as generalized quadrangles (GQs).  GQs have a rich literature, and we explain how each of our three infinite families of phased BIBD ETFs relate to it.

Our construction is also related to another recently introduced method for constructing complex ETFs, namely the one given in the recent paper “Equiangular lines and covers of the complete graph” by Coutinho, Godsil, Shirazi and Zhan.  Their construction generalizes a well-known connection between real ETFs and strongly regular graphs (SRGs), identifying certain types of complex ETFs with abelian distance-regular antipodal covers of complete graphs (DRACKNs).

Overall, we will see that certain special types of filter banks simultaneously yield ETFs, abelian GQs and abelian DRACKNs.  We also discuss some partial converses to these results.  For example, the existence of a certain type of phased BIBD ETF actually implies the existence of such a filter bank, which in turn implies the existence of certain GQs and DRACKNs.  This opens up some exciting new possibilities for future research: for a long time, frame theory has been leveraging the rich literature of combinatorial designs in order to construct ETFs; these results allow us to use frame theory to prove new results in combinatorial design.

4. Maximal ETFs by combinatorial techniques (John Jasper)

The most famous open problem in the study of equiangular tight frames (ETFs) concerns maximal ETFs, that is, ETFs with M^{2} vectors in \mathbb{C}^{M}. To those studying quantum information theory the collection of outer products of a maximal ETF is called a symmetric informationally complete positive operator valued measure (SIC-POVM). In his Ph.D. dissertation in 1999, Zauner conjectured that a SIC-POVM exists for each dimension M\geq 2. This open problem is now referred to as Zauner’s conjecture.

Zauner’s original conjecture was actually more detailed regarding how one can obtain a SIC-POVM. In particular, he conjectured that for each M\geq 2 there is a maximal ETF formed by taking the orbit of a single vector, called a fiducial vector, under the action of the Heisenberg group. A great deal of effort has been put into proving Zauner’s conjecture. Exact solutions are known for dimensions M=2,\ldots,15,17,19,24,35,48, and numerical solutions are known for M\leq 67. With one exception, these solutions are all obtained by finding a fiducial vector for the Heisenberg group.

There is some good evidence that the group theoretic approach suggested by Zauner may have some fundamental limitations (see this blog entry). Looking at the study of ETFs in general, we see that ETFs generated by a group are important, for example, harmonic ETFs. However, there are several more constructions that are more purely combinatorial in nature. These include Steiner ETFs, Kirkman ETFs, Tremain ETFs, and many more. In this talk, we will discuss some alternate approaches to finding maximal ETFs. One of the smallest examples of a Steiner ETF is actually a maximal ETF in dimension 3, and this is the only instance where these combinatorial constructions have yielded a maximal ETF so far. However, we have recently seen some tantalizing evidence that some previously unknown combinatorial structure is lurking inside of maximal ETFs, illuminating new connections to existing constructions. Our hope is that with some work, we can leverage this combinatorial structure into new constructions of ETFs, perhaps even new maximal ones.

5. Achieving the orthoplex bound and constructing weighted complex projective 2-designs with Singer sets (Nathaniel Hammen)

(Based on this paper by Bernhard G. Bodmann and John Haas)

In many situations, we desire a unit-norm frame that has a small maximum magnitude among pairwise inner products. According to a bound by Welch, equiangular tight frames are the minimizers for the maximum magnitude of pairwise inner products. However, in a K dimensional Hilbert space, the Welch bound is only achievable if the number of vectors in the frame is at most K^2. If the number of vectors in the frame is larger than this, then the orthoplex bound serves as an alternative to the Welch bound.

In analogy with the Welch bound, the orthoplex bound is only achievable if the number of vectors in the frame is at most 2(K^2-1). In this talk we show that if a unit-norm frame has a maximum magnitude of pairwise inner products that is less than or equal to the orthoplex bound and there exists a basis such that the inner products between a frame vector and a basis vector are all identical, then the frame formed by the union of these two sets satisfies the orthoplex bound. If the initial frame is tight, then the orthoplectic frame will also be tight. In particular, the union of an equiangular tight frame made up of at least K^2-K vectors with such a basis will always form a tight orthoplectic frame.

Two families of such orthoplectic frames are constructed using cyclic frames generated by difference sets and relative difference sets. When K-1 is a prime power, we obtain a tight frame with K^2+1 vectors, and when K is a prime power, we obtain a tight frame with K^2+K+1 vectors. In addition, the orthoplectic frames that are constructed can also be shown to be weighted 2-designs. These are useful in quantum state tomography.

6. Optimal subspace packings (Dustin G. Mixon)

While the previous talks have discussed packing 1-dimensional subspaces in a finite-dimensional Hilbert space, in this talk, we will pack higher-dimensional subspaces. In the 1-dimensional case, we considered the interior angle between two lines, also known as the principal angle. When the subspaces are higher-dimensional, which angle shall we attempt to maximize?

In the higher-dimensional case, there are actually several principal angles to work with. Given subspaces P and Q, the principal angles are defined iteratively: Find the unit vectors p_1\in P and q_1\in Q that maximize \langle p_1,q_1\rangle, and then for each i\geq 2, find a unit vector p_i\in P orthogonal to \{p_j\}_{j=1}^{i-1} and a unit vector q_i\in Q orthogonal to \{q_j\}_{j=1}^{i-1} that together maximize \langle p_i,q_i\rangle. Then the ith principal angle between P and Q is \arccos\langle p_i,q_i\rangle.

Now that we have principal angles, we can use them to define a worthy packing objective. When Conway, Hardin and Sloane first wrestled with this, they discussed several alternatives, and found that the so-called chordal distance was the easiest to work with theoretically:

\displaystyle{\mathrm{dist}_\mathrm{chord}(P,Q)=\sqrt{\sum_{i=1}^k\sin^2\theta_i},}

where P and Q are k-dimensional and \{\theta_i\}_{i=1}^k are the principal angles. Later, Dhillon, Heath, Strohmer and Tropp introduced another notion of distance, called the spectral distance:

\displaystyle{\mathrm{dist}_\mathrm{spec}(P,Q)=\min_{i\in\{1,\ldots,k\}}\sin\theta_i.}

When this latter notion of distance is large for all pairs in a given ensemble of subspaces, the ensemble is particularly well-suited for the compressed sensing of block-sparse signals (see this paper).

In this talk, we will discuss subspace packings which are chordal- and spectral-distance optimal. In particular, we will discuss generalizations of the Welch bound, as well as known constructions.

5 thoughts on “SOFT 2016: Summer of Frame Theory”

  1. do you have a link to the workshop? will the talks / slides be posted for those who can’t get there?

    Reply

  2. Is this workshop required participant US citizen? I wish I could be there. I like to know the details of all the papers. I only study on our own. Please let me join next time if possible.

    Reply

    1. Hi, Wei-Hsuan — This was held on AFIT’s campus, so yes, the participants were US citizens. Most of the extended abstracts above provide links to the papers upon which they were based. Feel free to email the speaker if you want more details. Judging by the success of the workshop, I’d be interested in organizing another one, but at a different location where we can invite you and a few other non-US citizens.

      Reply

      1. Great! Thank you for your reply. I expect to join next workshop and have more interaction with you. Thank you.

Leave a comment