# Grassmanian packings: Trust region stochastic tuning for matrix incoherence

Josiah Park, Carlos Saltijeral, and Ming Zhong  ${\tt j.park@tamu.edu,\
csaltijeral@tamu.edu,\<EMAIL_ADDRESS>This research was supported by NSF
Tripods Grant CCF-1934904 (JP).

###### Abstract

We provide a new numerical procedure for constructing low coherence matrices,
Trust-Region Stochastic Tuning for Matrix Incoherence (TRST-MI) and detail the
results of experiments with a CPU/GPU parallelized implementation of this
method. These trials suggest the superiority of this approach over other
existing methods when the size of the matrix is large. We also present new
conjectures on optimal complex matrices motivated and guided by the
experimental results.

###### Index Terms:

Equiangular tight frames, line packings, complex projective codes, discrete
geometry, manifold optimization, parallelization, trust region method, MIMO.

##  I Introduction

Structured point configurations have generated much interest in recent years
in connection with their role in applications to coding theory, wireless beam-
forming, and compressed sensing. Some of these configurations, like packings
which have maximal separation of elements, arise naturally in communications
due their optimal properties for quantization. Multiple-Input Multiple-Output
(MIMO) wireless communication is one of the main areas where such
configurations (called Grassmannian constellations) have gained interest due
to desirable statistical properties for signal transmission [ARU, HMR+, LHS,
ZWG].

An optimal packing of lines or subspaces in $\mathbb{F}^{d}$
($\mathbb{F}=\mathbb{R},\mathbb{C}$, or $\mathbb{H}$) satisfies that the
minimal pairwise chordal distance is maximized over all choices of collections
of $k$-dimensional subspaces in $\mathbb{F}^{d}$,
$\Phi=\\{\boldsymbol{\varphi}_{j}\\}_{j=1}^{N}$. The difficulty in designing
such codebooks is demonstrated by the extensive literature addressing attempts
to numerically and algebraically devise means to construct optimal and near-
optimal packings. Conway, Hardin, and Sloane pioneered numerical searches for
real packings [CHS] hosting an online database of these configurations [Sl2].

For simplicity, we address here only the case that $k=1$, corresponding to the
problem of packing lines. In this case, lines may be identified with points in
the projective space $\mathbb{FP}^{d-1}$, and so we will call such packings
optimal projective codes. Any line through the origin in $\mathbb{F}^{d}$,

$x\mathbb{F}=\\{x\lambda\ |\ \lambda\in\mathbb{F}\setminus\\{0\\}\\}.$ (I.1)

can be identified with a unit vector (one interesting fact is that line
packings in $\mathbb{C}\mathbb{P}^{1}$ under this identification are
equivalent to finding optimally spread points on $\mathbb{S}^{2}$, we use this
later). Through this correspondence, the chordal distance between points
$x,y\in\mathbb{FP}^{d-1}$ (lines in $\mathbb{F}^{d}$), has a simple formula

$\rho(x,y)=\sqrt{1-|\langle x,y\rangle|^{2}}.$ (I.2)

The problem of maximizing the minimal chordal distance is then equivalent to
minimizing the coherence of a configuration, the maximal absolute value in the
off-diagonal elements of the Gram matrix of a set of unit vectors,
$\mathbf{\Phi}=\\{\boldsymbol{\varphi}_{j}\\}_{j=1}^{N}$,
$|\boldsymbol{\varphi}_{k}|=1$. We use $\mu(\Phi)$ to denote this quantity. In
searching for optimal codes then, the goal is to find the optimal values

$\mu_{N,d}=\min\limits_{\mathbf{\Phi}\subset\mathbb{S}_{\mathbb{F}}^{d-1}:\
|\Phi|=N}\max_{j\neq k}\
|\langle\boldsymbol{\varphi}_{j},\boldsymbol{\varphi}_{k}\rangle|.$

##  II Welch bound and equiangular lines

One unusually symmetric type of packing of lines satifies that every pair is
equally spaced. These projective codes are called equiangular tight frames
(ETFs), optimal simplices, or equiangular lines [LS]. The vectors in these
codes form a tight frame, and attain the Welch bound, a lower bound on the
coherence of a configuration (detailed below) [We]. When a tight frame is
represented by a $d\times N$ matrix over $\mathbb{F}$, it satisfies the
property that the composition, $\Phi\Phi^{*}$ is a constant times the $d\times
d$ identity matrix. Tight frames have similar properties to orthonormal bases,
but are additionally overcomplete, or redundant.

ETFs are precisely the systems of unit vectors which attain equality in the
Welch bound, a lower bound on the minimal coherence of any code in
$\mathbb{FP}^{d-1}$,

$\mu(\Phi)\geq\sqrt{\frac{N-d}{d(N-1)}}.$

The size of an ETF cannot become too large in connection with Gerzon’s bound,
which says that this size is bounded above by the dimension of a corresponding
space of symmetric matrices, $N\leq\binom{d+1}{2},d^{2}$, or $2d^{2}-d$ in the
real, complex, or quaternionic cases respectively.

It is generally an open question for which dimensions maximally sized
equiangular lines exist. Zauner’s conjecture posits that in the complex case
these configurations always exist, and this has been verified up to dimension
$21$, while numerical evidence suggests the conjecture holds at least up to
dimension $121$ [ABF+, Z]. In the real case, a variety of methods show that
equality in Gerzon’s bound cannot hold in several dimensions, and it is known
generally that $d+2$ must be the square of an odd integer if equality holds
[BMV]. In the quaternion case, there is a lack of numerical evidence for a
similar phenomena which appears in the complex setting [CKM].

It is worth mentioning there is a type of dual construction, in which any ETF
of size $N$ in $\mathbb{F}^{d}$ gives rise to another ETF of equal size in
$\mathbb{F}^{N-d}$. One may check that by completing the $d\times N$ matrix to
an appropriately scaled unitary matrix gives rise to another ETF. This is
known as Gale duality and the new ETF is referred to as the Naimark complement
of the first.

The Welch bound is only the first among several other lower bounds for the
coherence of $N$ lines in $\mathbb{F}^{d}$. These include the orthoplex bound,
the Levenshtein bound, and the Bukh-Cox bound [BC]. It happens, although
rarely when compared to Welch bound equality, that these bounds are met too
for configurations, for instance by mutually unbiased bases and more rarely,
the tight projective designs. For examples of the latter, take the tight
projective designs of size $40$ and $126$ in $\mathbb{CP}^{3}$ and
$\mathbb{CP}^{5}$ [DGS, H].

##  III Grassmanian packings and MISO

By exploiting radio channel information MIMO allows for sending and receiving
data simultaneously via multiple transmitting and receiving antennas. Complex
optimal projective codes (also called Grassmanian packings) give good
beamforming codebooks in MIMO but we focus below only on the specific case of
MISO (Multiple-Input Single-Output) systems here due the result of [LHS] which
shows that codebook design for single stream transmission is independent of
the number of receive antennas.

The typical MISO system with $d$ transmit antennas and a single receive
antenna can be modeled with a channel vector $\mathbf{h}=[h_{1},...,h_{d}]$
with independently and identically distributed (i.i.d.) complex Gaussian
entries with zero mean and unit variance
$\mathbf{h}\sim\mathcal{N}_{\mathbb{C}}(\bf{0},\mathbf{I}_{d})$. The channel
vector captures transmission conditions (like physical obstructions in the
path between antennas for instance) which result in the form of the received
signal. The channel is often assumed to be static over a small time period
(called the coherence time).

We transmit a symbol or bit $s$ over the channel using what is called a
beamforming vector $\boldsymbol{\varphi}$ where
$\boldsymbol{\varphi}=[\varphi^{1},\varphi^{2},\dots,\varphi^{d}]$ is a vector
in $\mathbb{C}^{d}$ with unit norm. Altogether this gives us a simple model
for the transmission of the symbol $s$ to the receiver

$y=\langle\boldsymbol{\varphi},\mathbf{h}s\rangle+\eta$

where $\eta$ is complex Gaussian noise of mean zero and variance $\sigma$, and
each of the $d$ entries of $\boldsymbol{\varphi}^{\dagger}s$ are transmitted
at the same time by the $d$ input antennas.

A well studied method for choosing the beamforming vector in the above
transmission model assumes that a codebook of potential beamforming vectors is
agreed upon first and accessible to the transmitter and receiver

$\mathbf{\Phi}=[\boldsymbol{\varphi}_{1},\boldsymbol{\varphi}_{2},\dots,\boldsymbol{\varphi}_{N}].$

Further it is assumed the receiver can measure in an error-free manner

$\max\limits_{i=1,\dots,N}|\langle\boldsymbol{\varphi}_{i},\mathbf{h}\rangle|^{2}$

and may select a $\boldsymbol{\varphi}_{i}$ which maximizes this quantity,
relaying the relevant index to the transmitter before it sends the symbol $s$.

At this point the transmitter uses the code word $\boldsymbol{\varphi}_{i}$ to
transmit the symbol $s$. This choice maximizes the signal-to-noise ratio (SNR)
within a small time interval of the receiver’s measurements

$\gamma=\frac{|\langle\boldsymbol{\varphi},\mathbf{h}\rangle|^{2}E_{s}}{\sigma}$

where $E_{s}=\mathbb{E}\left[|s|^{2}\right]$ is the average symbol error. Note
that the value of $s$ can now be trivially estimated from $y$ via dividing by
$\langle\boldsymbol{\varphi},\mathbf{h}\rangle$ [ZWG].

A good beamforming codebook in this setting unsurprisingly is found by taking
$\mathbf{\Phi}$ to be a complex line packing [LHS]. In other words if
$\mathbf{\Phi}$ minimizes coherence for all other $N$ systems of unit norm
vectors in $\mathbb{C}^{d}$ (or even approximately) then it serves as a good
set of vectors for the MISO transmission application above.

The quantization scheme that corresponds to the optimal choice of
$\boldsymbol{\varphi}_{i}$ above

$\mathcal{Q}_{\mathbf{\Phi}}(\mathbf{h}):\mathbf{h}\mapsto\arg\max\limits_{i=1,\dots,N}|\langle\boldsymbol{\varphi}_{i},\boldsymbol{h}\rangle|^{2}=\arg\min\limits_{i=1,\dots,N}d_{c}(\boldsymbol{\varphi}_{i},\boldsymbol{h})$

where $d_{c}$ is the chordal distance, when considered for
$h\sim\sigma_{\mathbb{CP}^{d-1}}$ uniformly distributed on the space of
complex lines and for codebook $\mathbf{\Phi}$ has a distortion metric

$\mathcal{D}(\mathbf{\Phi})=\mathbb{E}[d_{c}^{2}(\sigma_{\mathbb{CP}^{d-1}},\mathcal{Q}_{\mathbf{\Phi}}(\sigma_{\mathbb{CP}^{d-1}}))]$

which is hard to express generally. One of the main results of [LHS] is that
this distortion measure may be bounded by an increasing function of the
coherence of the codebook $\mathbf{\Phi}$ and so as a proxy for designing a
codebook which minimizes the distortion, we find one minimizing coherence.

##  IV Optimization procedure

We now introduce a new optimization procedure we use to optimize for low
coherence matrices or complex Grassmanian packings which we call Trust Region
Stochastic Tuning for Matrix Incoherence (TRST-MI). This procedure uses an
alternating method of computing successive smooth approximations to the
maximum function (log-sum-exp) coupled with an unconstrained minimization
procedure (trust region conjugate gradient method, a popular nonlinear
optimization method [NW]) used to minimize the smooth maximum function
approximation evaluated on the absolute value squared of inner products of a
unit norm projection of a given matrix. A random Monte-Carlo sampling
procedure is additionally employed to address the fact that many trials may
reach a local minima value far from the global minimum for the coherence.

The maximum approximation mentioned above takes the form

$F_{s,\delta}(\mathbf{x})=s+\delta\log{\left[\sum_{i=1}^{n}\mathop{\rm
exp}{\left(\frac{x_{i}-s}{\delta}\right)}\right]}$

where $s=\max\limits_{i}x_{i}$ and $\delta>0$ is small. The choice to optimize
successive approximations of the maximum magnititude of off-diagonal inner
products was investigated also in [ARU]. The reference [ZB] gives a good
survey of other numerical approaches for contructing line packings.

We choose a series of decreasing $\delta_{k}^{\prime}s$ (which are
experimentally chosen based on performance and guided by elementary
considerations) and feed the optimized matrix $\mathbf{x}^{\prime}$ which
comes out of minimization of $F_{s,\delta_{k}}(\mathbf{x})$ into a
minimization of the next approximation
$F_{s,\delta_{k+1}}(\mathbf{x}^{\prime})$. Eventually we reach a terminally
small value of $\delta$ which decreasing further tends not to result in any
considerate improvement in the optima quality (for similar time spent). The
variable $\mathbf{x}$ here corresponds to the upper triangular part of the
absolute value of the matrix of inner products obtained after normalizing the
columns of a matrix to be unit norm (it suffices to only compute the maximum
of the upper-triangular part by symmetry).

Algorithm 1 Trust-Regions-CG-Steihaug [NW][Alg. 7.2]

$z_{0}\leftarrow 0,\ r_{0}\leftarrow\nabla{f}_{k},\ d_{0}\leftarrow-
r_{0}=-\nabla f_{k}$

if $\|r_{0}\|<\epsilon_{k}$ then return $p_{k}\leftarrow z_{0}=0$

for $j=0,1,2,...$ do

if $d_{j}^{T}B_{k}d_{j}\leq 0$ then

Find $\tau$ s.t. $p_{k}=z_{j}+\tau d_{j}$ minimizes (†)

return $p_{k}$;

end if

$\alpha_{j}\leftarrow r_{j}^{T}r_{j}/d_{j}^{T}B_{k}d_{j}$

$z_{j+1}\leftarrow z_{j}+\alpha_{j}d_{j}$

if $\|z_{j}\|\geq\Delta_{k}$ then

Find $\tau\geq 0$ s.t. $p_{k}=z_{j}+\tau d_{j}$ and $\|p_{k}\|=\Delta_{k}$

return $p_{k}$;

end if

$r_{j+1}\leftarrow r_{j}+\alpha_{j}B_{k}d_{j}$

if $\|r_{j}\|<\epsilon_{k}$ then

return $p_{k}\leftarrow z_{j+1}$;

end if

end for

end if

(†): $\min_{p\in\mathbb{R}^{n}}m_{k}(p)=f_{k}+\nabla
f_{k}^{T}p+\frac{1}{2}p^{T}B_{k}p$ subject to

$\|p\|\leq\Delta_{k}$, where $B_{k}=\nabla^{2}f_{k}$

We now show how an elementary inequalities suggest a choice of $\delta$ which
gives good approximation to the maximum function.

######  Proposition 4.1.

Let $F_{s,\delta}(\mathbf{x})=s+\delta\log{\left[\sum_{i=1}^{n}\mathop{\rm
exp}{\left(\frac{x_{i}-s}{\delta}\right)}\right]}$, where
$s=\max\limits_{i}x_{i}$. Then,

$s\leq F_{s,\delta}(\mathbf{x})\leq s+\delta\log{n}.$

###### Proof.

The first (left) inequality is trivial since $\delta>0$ and

$\sum_{i=1}^{n}\mathop{\rm
exp}\left(\frac{x_{i}-s}{\delta}\right)\geq\mathop{\rm
exp}\left(\frac{s-s}{\delta}\right)=1.$

Let $y_{i}=\frac{x_{i}-s}{\delta}$, then

$\log\left[\sum_{i=1}^{n}\mathop{\rm
exp}(y_{i})\right]\leq\log\left[n\cdot\mathop{\rm
exp}(\max\limits_{i}y_{i})\right].$

Thus, since $\max\limits_{i}y_{i}=0,$ we have

$F_{s,\delta}(\mathbf{x})=s+\delta\log\left[\sum_{i=1}^{n}\mathop{\rm
exp}\left(\frac{x_{i}-s}{\delta}\right)\right]\leq s+\delta\log{n}.$

Note that the partial derivatives of the log-sum-exp approximation to the max
function, $F_{s,\delta}(\mathbf{x})$ are easy to compute. They are

$\frac{\partial}{\partial
x_{j}}F_{s,\delta}(\mathbf{x})=\frac{\delta\mathop{\rm
exp}\left(\frac{x_{j}-s}{\delta}\right)}{\sum_{i=1}^{n}\mathop{\rm
exp}\left(\frac{x_{i}-s}{\delta}\right)}.$

Since for our purposes $s$ is the maximum value of $x_{i}$,

$0\leq\mathop{\rm exp}\left(\frac{x_{j}-s}{\delta}\right)\leq 1.$

Also, as $\delta\rightarrow 0$ the gradient of $F_{s,\delta}(\mathbf{x})$
should become small with respect to the entries of the associated matrix. So
the gradient descent method will either progress slowly, or the gradient
tolerance stopping criteria will be reached very quickly. This analysis
provides an explanation for why the successive approximation then optimization
procedure mentioned above is employed instead of simply optimizing
$F_{s,\delta}(\mathbf{x})$ for very small $\delta$ to start.

TABLE I: A comparison of time needed to optimize for a single step (a single approximation of max function) for different large values of $(d,N)$ for CPU and GPU parallelized procedures. The GPU runs were completed on an Nvidia A100 80 GB RAM graphics processing unit. The CPU runs were done on either a single or 6 parallel cores on a Ryzen 5 3600 CPU.  $d$ | $N$ | Time GPU $(s)$ | Time CPU (6 cores) | Time CPU (1 core)
---|---|---|---|---
$4$ | $18000$ | $1161$ | $2927$ | $4075$
$5$ | $18000$ | $1918$ | $3896$ | $5661$
$6$ | $18000$ | $3400$ | $3641$ | $10128$
TABLE II: A comparison of time needed to optimize for different large values of $(d,N)$ for different procedures (all on CPU). The TRST-MI trials were completed on 6 parallel cores on a Ryzen 5 2600 CPU. The implementations of Alt. Proj. and GrassPack were non-parallelized and run in Matlab. When the number of points is large Alt. Proj. cannot reach the globally optimal values, while GrassPack also suffers in performance while taking more time for large arguments. Values are rounded up at fourth decimal. $d$ | $N$ | Time TRSTMI $(s)$ | Time Alt. Proj. $(s)$ | Time GrassPack $(s)$
---|---|---|---|---
|  | (Coherence) | (Coherence) | (Coherence)
$2$ | $4$ | $3.2$ | $0.6123$ | $0.092595$
|  | $(0.5774)$ | $(0.5774)$ | $(0.5774)$
$3$ | $9$ | $15$ | $1.1975$ | $4.929464$
|  | $(0.5001)$ | $(0.5001)$ | $(0.5008)$
$4$ | $16$ | $30$ | $2.727686$ | $12.565372$
|  | $(0.4473)$ | $(0.4473)$ | $(0.4473)$
$5$ | $25$ | $90$ | $8.569802$ | $35.070155$
|  | $(0.4083)$ | $(0.4510)$ | $(0.4085)$
$6$ | $36$ | $240$ | $14.457345$ | $75.183590$
|  | $(0.3778)$ | $(0.4460)$ | $(0.3785)$
$7$ | $49$ | $600$ | $26.150609$ | $625.222357$
|  | $(0.3834)$ | $(0.4502)$ | $(0.4134)$

######  Remark 4.1.

In our case $\mathbf{x}$ is the vectorized form of the upper part of a square
$N\times N$ matrix and hence $n=\frac{N(N-1)}{2}$. Hence to get $F_{s,\delta}$
within $\epsilon$ of the value of the max function we may take
$\delta\approx\frac{\epsilon}{2\log{N}}$.

######  Remark 4.2.

Without the shift by $s$ within the exponential function, evaluation of the
inner function will ‘blow up’ for small $\delta$. One way to practically
implement this is that the actual maximum may be computed regularly, after
some fixed number of iterations of the gradient based minimization procedure,
and then used as the approximate maximum for a number of subsequent
iterations.

Another way to address this is to use the so-called subgradient method for
nonsmooth optimization [Ne]. Here in our gradient based minimization procedure
we compute a subgradient as a proxy for the gradient of the non-smooth
function $\max\limits_{i}x_{i}$. We employ this method in our approach due to
observed improved performance.

######  Remark 4.3.

We are able to use an unconstrained minimization technique because we divide
each column of the $d\times N$ matrix representing configuration
$\mathbf{\Phi}$ by the norm of the associated column vectors (precluding a
zero vector column from our matrix). One way to improve performance might be
to use another representation of the unit norm columns (for instance using
manifold optimization such as in [CBS+]).

######  Remark 4.4.

We implement TRST-MI in PyTorch [PGM+] so as to allow for painless
parallelization support on CPU/GPU. We found that this led to notable
decreases in runtime and detail the result of some experiments in Table I. In
Table II we compare the runtime and performance of TRST-MI to other
established methods for constructing complex line packings [TDH+, MD].

######  Remark 4.5.

One approach which has been successful for finding high precision optimal
spherical codes (best packings of spherical caps on the surface of a sphere)
involves successive minimization of harmonic energies [Wa1, Wa2], an
adjustment of an algorithm from [K]. We find this procedure is very time
consuming for large problems, but expect that as a (likely expensive) post-
processing step, a singular energy optimization procedure may be applied to
the output of TRST-MI to further decrease coherence.

######  Remark 4.6.

In our experiments we found that TRST-MI improved on many existing estimates
for $\mu_{N,d}$ from the online databse [JKM]. We collected a few that we
expect will be harder to improve upon in Table IV.

##  V Conjectures from Numerics

A well-known phenomena that appears when studying best packing problems in
compact spaces is that one can obtain other seemingly optimal packings from
’exceptional’ packings by removing one or more points. This is not unique to
packings of subspaces, but is a phenomena which appears in a variety of
geometric packing questions.

One example of this phenomena can be understood via the orthoplex bound, a
coherence lower bound similar to the Welch bound. By removing points from
mutually unbiased bases (MUBs) the orthoplex bound shows one often obtains an
optimal packing.

######  Proposition 5.1 (Orthoplex and Levenshtein bound, [CHS, Le]).

Fix $d>1$, select $\Phi\in\mathbb{C}^{d\times N}$ with unit norm columns, and
set $\mu=\mu(\Phi)$. Then

$\ \mu(\Phi)\geq\frac{1}{\sqrt{d}},\ \ \textrm{if $n>d^{2}$,}\\\ \vspace{2
mm}$ (V.1) $\ \mu(\Phi)\geq\sqrt{\frac{2n-d(d+1)}{(n-d)(d+1)}},\ \ \textrm{if
$n>d^{2}$.}$ (V.2)

Equality in the orthoplex bound (V.1) requires $n\leq 2d^{2}-1$, and equality
in the Levenshtein bound (V.2) requires that $\Phi$ be tight with angle set
$\\{0,\mu^{2}\\}$.

Two orthonormal bases in $\mathbb{CP}^{d-1}$ are said to be mutually unbiased
if they are aligned so that the inner product of any pair of vectors,
$\varphi_{j},\varphi_{k}$, each from distinct bases, satisfies

$|\langle\varphi_{j},\varphi_{k}\rangle|=\frac{1}{\sqrt{d}}.$

It is known that the maximal number of MUBs in $\mathbb{CP}^{d-1}$ is no
larger than $d+1$, and that for prime power dimension, $d=p^{k}$, it is known
this maximum number is attained. Interestingly, it is an open question what is
the maximal number of MUBs in dimension $d=6$, where it is conjectured that at
most $3$ exist.

An immediate consequence of the orthoplex bound is that for $d=p^{k}$, where
$p$ prime, any $(d+1)$-MUB gives rise to an optimal projective packing of
$N=(d+1)d-j$ points, $j=0,\dots,d-1$ by removal of any $j$ points in the
$(d+1)$-MUB. In particular, $\mu_{N,d}=\frac{1}{\sqrt{d}}$ for $d$ and $N$ as
above. It is an interesting question of whether such configurations are the
unique coherence minimizers.

Our first conjecture suggests a similar phenomena occurs for maximal complex
equiangular tight frames (also known as SIC-POVMs [RBSC]).

######  Conjecture 5.1.

For $d\geq 2$, there exists a SIC of $N=d^{2}$ points and for each
$N=d^{2}-j$, $j=0,\dots d-2$, each optimal projective code of size $N$ is
given by the removal of some $j$ points from the SIC. In particular,
$\mu_{N,d}=\frac{1}{\sqrt{d+1}}$ for $d$ and $N$ as above.

The first statement on existence is just Zauner’s conjecture. However, if the
above statement is true, this would imply non-existence of an ETF of size $N$,
for $N$ slightly smaller than $d^{2}$ as above, since

$\frac{1}{\sqrt{d+1}}>\sqrt{\frac{d^{2}-j-d}{d(d^{2}-j-1)}},$

holds for any $j\in\\{1,\dots,d-2\\}$. For comparison, the only non-existence
result for complex ETFs (excluding those ruled out by Gerzon’s bound) shows
for $d=3$ there does not exist an ETF of size $N=8$, a special case of the
above conjecture. Conjecture 5.1 also appears for the specific case of $d=3$
in [JKM].

It is interesting how sharp the threshold is for removing points while still
obtaining an optimal packing. We expect that for $d=2,3,4,$ and $5$ the above
conjecture gives the right threshold. Besides maximally sized MUBs or SICs
there are several other exceptional configurations for which it appears one
can remove a point, still obtaining an optimal packing. In increasing
dimension, some examples from numerics appear to be the tight $3$-design in
$\mathbb{CP}^{3}$ of $40$ points, the $W(K_{5})$ line system of $45$ points in
$\mathbb{CP}^{4}$, an ETF of $N=31$ points in $\mathbb{CP}^{5}$, and an ETF of
$28$ points in $\mathbb{CP}^{6}$.

We expect that the $126$ point tight $3$-design also has the above property. A
newly found highly symmetric, small sized projective $3$-design (described in
full in [BGM+]) of $85$ points in $\mathbb{CP}^{4}$ is also expected to have
this property (and in particular is expected to be a new optimal code). In all
of the above cases, it is not clear how many points can be removed so as to
obtain an optimal packing, nor for what reason seeming differences in this
number occur for similar configurations.

One phenomena which is displayed numerically in the complex case is that small
complex optimal codes appear to have a single distinct distance between points
for $N$ up to some threshold $m(d)$ which appears to increase non-trivially
with the dimension $d$. Since a one distance set cannot become too large,
there is a maximum size $m(d)\leq d^{2}$ for which there exists an optimal
code of size $N\in[d,m(d)]$ with only a single distinct distance appearing. By
default $m(d)\geq d+1$, since the orthonormal basis and the simplex are
optimal codes.

From our optimal candidates in dimensions $d=2$ through $8$ and increasing
$N$, there is a value of $N$ where numerically optimal configurations go from
having very small differences in the absolute value of their off-diagonal Gram
matrix entries to noticeably large differences. Another interesting problem is
to characterize how this parameter $m(d)$ behaves.

TABLE III: Consecutive small values of $N$ for which it appears an optimal code in $\mathbb{CP}^{d-1}$ of size $N$ can be taken to have a single distance appearing. $d$ | $N$
---|---
2 | 2–3
3 | 3–4
4 | 4–8
5 | 5–13
6 | 6–16
7 | 7–19
8 | 8–22
TABLE IV: A comparison of select coherence values (rounded up at sixth digit) obtained via TRST-MI to established constructive upper bounds from [JKM].  $d$ | $N$ | TRSTMI coh. |  [JKM] database coh.
---|---|---|---
3 | 27 | 0.734233 | 0.73726116
3 | 28 | 0.737797 | 0.73884638
6 | 24 | 0.371529 | 0.37267800

##  VI Acknowledgements

The first author would like to acknowledge AIM for providing aid to attend the
‘Discrete Geometry and Automorphic Forms’ organized by Henry Cohn and Maryna
Viazovska where work on this project began. Portions of this research were
conducted with the advanced computing resources provided by Texas A&M High
Performance Research Computing.

The authors would also like to acknowledge helpful correspondence from Henry
Cohn, Simon Foucart, John Jasper, Emily J. King, Dustin G. Mixon, and
Oleksandr Vlasiuk.

Figure VI.1: Comparison of lower bounds for $\mu_{N,d}$ against constructive
numerical upper bounds for $N\leq 100$ and $\mathbb{C}\mathbb{P}^{1}$,
$\mathbb{C}\mathbb{P}^{2}$, and $\mathbb{C}\mathbb{P}^{3}$ obtained via the
TRST-MI optimization procedure (minimum values among 20 random intializations
for each set of parameters). With log-sum-exp approximation level
‘eps’$=7,8,9$ for the maximum function (corresponding to
$\delta=10^{-7}-10^{-8}$) and the scale taken in the plots, the difference
with the values coming from Sloane’s database for optimal spherical codes are
indistiguishable [Sl1]. Some successive coherence values are smaller than
those preceding. Since removing a point from a larger configuration does not
increase the coherence, the plots can be improved in some cases trivially. We
show the raw optimized values instead.

## References

  * [ABF+] M. Appleby, I. Bengtsson, S. Flammia and D. Goyeneche  Tight frames, Hadamard matrices and Zauner’s conjecture. J. Phys. A 52(29) (2019). MR3983953
  * [ARU] D. Agrawal, T. J. Richardson and R. L. Urbanke.  Multiple-antenna signal constellations for fading channels. IEEE Trans. on Info. Theory, 47(6) (2001), 2618–2626.
  * [BMV] E. Bannai, A. Munemasa, and B. Venkov.  The nonexistence of certain tight spherical designs.  Algebra i Analiz 16 (2004), 1–23. MR2090848
  * [BC] B. Bukh and C. Cox.  Nearly orthogonal vectors and small antipodal spherical codes. Israel J. Math. 238 (2020), 359–388. arXiv:1803.02949
  * [BGM+] D. Bilyk, A. Glazyrin, R. Matzke, J. Park, and O. Vlasiuk.  Optimal measures for $p$-frame energies on spheres.  preprint, arXiv:1908.00885.
  * [CBS+] D. Cuevas, C. Beltran, I. Santamaria, V. Tucek and G. Peters.  A Fast Algorithm for Designing Grassmannian Constellations.  WSA 2021, 25th International ITG Workshop on Smart Antennas, 2021, 1–6.
  * [CHS] J. H. Conway, R. H. Hardin, and N. J. A. Sloane.  Packing lines, planes, etc.: packings in Grassmannian spaces Experiment. Math. 5 (1996), 139–-159. MR1418961
  * [CKM] H. Cohn, A. Kumar, and G. Minton.  Optimal simplices and codes in projective spaces.  Geom. Topol. 20 (2016), 1289–1357. arXiv:1308.3188 MR3523059
  * [DGS] P. Delsarte, J. M. Goethals, and J. J. Seidel.  Spherical codes and designs. Geometriae Dedicata, 6 (1977), 363–388. MR0485471
  * [H] S. G. Hoggar.  t-designs in projective spaces. European J. Combin., 3 (1982), 233–254. MR0679208
  * [HMR+] B. M. Hochwald, T. L. Marzetta, T. J. Richardson, W. Sweldens and R. Urbanke.  Systematic design of unitary space-time constellations IEEE Trans. on Info. Theory, 46(6), 2000.
  * [JKM] J. Jasper, E. King, D. Mixon.  Game of Sloanes: Best known packings in complex projective space. preprint, arXiv:1907.07848.
  * [K] D. Kottwitz.  The densest packing of equal circles on a sphere. Acta Crystallographica Section A: Foundations of Crystallography,47 (1991), 158–165.
  * [Le] V. I. Levenshtein.  Bounds on the maximal cardinality of a code with bounded modules of the inner product. Soviet Math. Dokl., 263 1303–1308, (1982). MR0653223
  * [LS] P.W.H. Lemmens and J.J. Seidel.  Equiangular Lines.  Journal of Algebra 24, 494-512 (1973).
  * [LHS] D. J. Love, R. W. Heath, and T. Strohmer.  Grassmannian beamforming for multiple-input multiple-output wireless systems. IEEE transactions on information theory 49(10) (2003), 2735–2747.
  * [MD] A. Medra and T. N. Davidson.  Flexible Codebook Design for Limited Feedback Systems Via Sequential Smooth Optimization on the Grassmannian Manifold. IEEE Transactions on Signal Processing, 62(5), (2014), 1305–1318.
  * [Ne] Y. Nesterov.  Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science and Business Media, (2003). MR2142598
  * [NW] J. Nocedal, and S. J. Wright.  Numerical Optimization. Springer, (1999). MR2244940
  * [PGM+] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, … and S. Chintala.  Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019).
  * [RBSC] J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves.  Symmetric informationally complete quantum measurements. J. Math. Phys. 45 (2004), 2171–2180. arXiv:quant-ph/0310075 MR2059685
  * [Sl1] N. J. Sloane.  Spherical Codes.  Online resource, http://neilsloane.com/packings/.
  * [Sl2] N. J. Sloane.  How to Pack Lines, Planes, 3-Spaces, Etc. Online resource, http://neilsloane.com/grass/.
  * [TDH+] J. A. Tropp, I. S. Dhillon, R. W. Heath, and T. Strohmer.  Designing structured tight frames via an alternating projection method. IEEE Transactions on information theory 51(1) (2005), 188–209. MR2234581
  * [Wa1] J. Wang.  Online resource.  https://aimath.org/data/paper/WangSphericalCode/.
  * [Wa2] J. Wang.  Finding and investigating exact spherical codes. Experimental Mathematics 18(2) (2009), 249–256. MR2549693
  * [We] L. Welch.  Lower bounds on the maximum cross correlation of signals. IEEE Trans. Inf. Theor., 20 (2006), 397–399.
  * [Z] G. Zauner.  Grundzüge einer nichtkommutativen Designtheorie. PhD thesis, University of Vienna, 1999.  Published in English translation: Int. J. Quantum Inf. 9 (2011), 445–507. MR2931102
  * [ZWG] S. Zhou, Z. Wang, and G. B. Giannakis.  Performance analysis for transmit-beamforming with finite-rate feedback. Proc. of 38th Conf. on Info. Sciences and Systems. Princeton University (2004).
  * [ZB] H. Zörlein and M. Bossert.  Coherence Optimization and Best Complex Antipodal Spherical Codes. IEEE Transactions on Signal Processing, 63(24), 6606–6615, (2015).