# Sparse Signal Processing with Frame Theory

Dustin G. Mixon

###### Abstract

Many emerging applications involve sparse signals, and their processing is a
subject of active research. We desire a large class of sensing matrices which
allow the user to discern important properties of the measured sparse signal.
Of particular interest are matrices with the restricted isometry property
(RIP). RIP matrices are known to enable efficient and stable reconstruction of
sufficiently sparse signals, but the deterministic construction of such
matrices has proven very difficult. In this thesis, we discuss this matrix
design problem in the context of a growing field of study known as frame
theory. In the first two chapters, we build large families of equiangular
tight frames and full spark frames, and we discuss their relationship to RIP
matrices as well as their utility in other aspects of sparse signal
processing. In Chapter 3, we pave the road to deterministic RIP matrices,
evaluating various techniques to demonstrate RIP, and making interesting
connections with graph theory and number theory. We conclude in Chapter 4 with
a coherence-based alternative to RIP, which provides near-optimal
probabilistic guarantees for various aspects of sparse signal processing while
at the same time admitting a whole host of deterministic constructions.

Robert Calderbank June 2012

###### Acknowledgements.

This thesis is based on a series of papers I coauthored with a long list of
friends, colleagues and mentors: Boris Alexeev, Waheed U. Bajwa, Afonso S.
Bandeira, Jameson Cahill, Robert Calderbank, Matthew Fickus, Negar Kiyavash,
Christopher J. Quinn, Janet Tremain, and Percy Wong. Each member of this list
taught me a thing or two throughout the course of my thesis research, and I
very much appreciate it! My time at Princeton has been a lot of fun, thanks in
large part to the good friends I’ve made here. From eating sushi, to playing
board games, to solving fun math riddles, the experience has been a blast, and
I’ll always remember it. My wife has a gift for filling my life with beauty
and love, and last year, she gave me a beautiful new life to love. Thank you,
Tessia and Charlotte, for making my life wonderful. Finally, I thank my
parents for their unfailing love and support, and I thank God for His role in
all of these things. This research was supported in part by the A.B. Krongard
Fellowship. The views expressed in this thesis are those of the author and do
not reflect the official policy or position of the United States Air Force,
Department of Defense, or the U.S. Government. To all those who never
dedicated a dissertation to themselves.
And to my daughter, Charlotte.

###  0.1 Overview

In several applications, data is traditionally collected in massive quantities
before employing a reasonable compression strategy. The result is a storage
bottleneck that can be prevented with a data collection alternative known as
_compressed sensing_. The philosophy behind compressed sensing is that we
might as well target the meaningful data features up front instead of spending
our storage budget on less-telling measurements. As an example, natural images
tend to have a highly compressible wavelet decomposition because many of the
wavelet cofficients are typically quite small. In this case, one might
consider targeting large wavelet coefficients as desired image features; in
fact, removing the contribution of the smallest wavelet coefficients will have
little qualitative effect on the image [57], and so using sparsity in this way
is intuitively reasonable.

Let $x$ be an unknown $N$-dimensional vector with the property that at most
$K$ of its entries are nonzero, that is, $x$ is $K$_-sparse_. The goal of
compressed sensing is to construct relatively few non-adaptive linear
measurements along with a stable and efficient reconstruction algorithm that
exploits this sparsity structure. Expressing each measurement as a row of an
$M\times N$ matrix $\Phi$, we have the following noisy system:

$y=\Phi x+z.$ (1)

In the spirit of _compressed_ sensing, we only want a few measurements: $M\ll
N$. Also, in order for there to exist an inversion process for (1), $\Phi$
must map $K$-sparse vectors injectively, or equivalently, every subcollection
of $2K$ columns of $\Phi$ must be linearly independent. Unfortunately, the
natural reconstruction method in this general case, i.e., finding the sparsest
approximation of $y$ from the dictionary of columns of $\Phi$, is known to be
${\mathsf{NP}}$-hard [108]. Moreover, the independence requirement does not
impose any sort of dissimilarity between the columns of $\Phi$, meaning
distinct identity basis elements could lead to similar measurements, thereby
bringing instability in reconstruction.

To get around the ${\mathsf{NP}}$-hardness of sparse approximation, we need
more structure in the matrix $\Phi$. Indeed, several efficient reconstruction
algorithms have been considered (e.g., Basis Pursuit [61, 62, 77], Orthogonal
Matching Pursuit [62, 134], and the Least Absolute Shrinkage and Selection
Operator [20]), and their original performance guarantees depend on the
additional structure that the columns of $\Phi$ are nearly orthogonal to each
other. Depending on the algorithm, this structure in the sensing matrix
enables successful reconstruction when noise term $z$ in (1) is zero,
adversarial, or stochastic, but for any of the original guarantees to apply,
the sparsity level must be $K=\mathrm{O}(\sqrt{M})$. To reconstruct signals
with larger sparsity levels, Candès and Tao [39] impose a much stronger
requirement on the sensing matrix: that every submatrix of $2K$ columns of
$\Phi$ be well-conditioned. To be explicit, we have the following definition:

######  Definition 1.

The matrix $\Phi$ has the _$(K,\delta)$ -restricted isometry property (RIP)_
if

$(1-\delta)\|x\|^{2}\leq\|\Phi x\|^{2}\leq(1+\delta)\|x\|^{2}$

for every $K$-sparse vector $x$. The smallest $\delta$ for which $\Phi$ is
$(K,\delta)$-RIP is the _restricted isometry constant (RIC)_ $\delta_{K}$.

In words, matrices which satisfy RIP act as a near-isometry on sufficiently
sparse vectors. Among other things, this structure imposes near-orthogonality
between the columns of $\Phi$, and so in light of the previous results, it is
not surprising that RIP sensing matrices enable efficient reconstruction:

######  Theorem 2 (Theorem 1.3 in [34]).

Suppose an $M\times N$ matrix $\Phi$ has the $(2K,\delta)$-restricted isometry
property for some $\delta<\sqrt{2}-1$. Assuming $\|z\|\leq\varepsilon$, then
for every $K$-sparse vector $x\in\mathbb{R}^{N}$, the following reconstruction
from (1):

$\tilde{x}=\arg\min\|\hat{x}\|_{1}\qquad\mbox{s.t.
}\|y-\Phi\hat{x}\|\leq\varepsilon$

satisfies $\|\tilde{x}-x\|\leq C\varepsilon$, where $C$ only depends on
$\delta$.

The exciting part about this guarantee is how the sparsity level $K$ of
recoverable signals scales with the number of measurements $M$. Certainly, we
expect at least $K\sim\sqrt{M}$ since RIP is a stronger matrix requirement
than near-orthogonality between columns. In analyzing the sparsity level,
random matrices have found the most success, specifically matrices with
independent Gaussian or Bernoulli entries [17], or matrices whose rows were
randomly selected from the discrete Fourier transform matrix [118]. With high
probability, these random constructions support sparsity levels $K$ on the
order of $\smash{\frac{M}{\log^{\alpha}N}}$ for some $\alpha\geq 1$.
Intuitively, this level of sparsity is near-optimal because $K$ cannot exceed
$\smash{\frac{M}{2}}$ by the linear independence condition. Thus, Theorem 2 is
a substantial improvement over the previous guarantees, and this has prompted
further investigation of RIP matrices. Unfortunately, it is difficult to check
whether a particular instance of a random matrix is $(K,\delta)$-RIP, as this
involves the calculation of singular values for all $\smash{\binom{N}{K}}$
submatrices of $K$ columns of the matrix. For this reason, and for the sake of
reliable sensing standards, many have pursued deterministic RIP matrix
constructions; Tao discusses the significance of this open problem in [132].

Throughout this thesis, we consider the problem from a variety of directions.
In Chapter 1, we observe a technique which is commonly used to analyze the
restricted isometry of deterministic constructions: the Gershgorin circle
theorem. This technique fails to demonstrate RIP for large sparsity levels; it
is only capable of showing RIP for sparity levels on the order of $\sqrt{M}$,
as opposed to $M$. This limitation has become known as the “square-root
bottleneck.” To illustrate that this bottleneck is not merely an artifact of
the Gershgorin analysis, we consider a construction which is optimal in the
Gershgorin sense, and we establish that this construction is $(K,\delta)$-RIP
for every $K\leq\delta\sqrt{M}$ but is not $(K,1-\varepsilon)$-RIP for any
$K>\sqrt{2M}$. The first inequality is proved by the Gershgorin circle
theorem, while the second uses the _spark_ of the matrix, that is, the number
of nonzero entries in the sparsest vector in its nullspace. While this
disparity between $\sqrt{M}$ and $M$ is significant in many applications, such
constructions are particularly well-suited for the sparse signal processing
application of digital fingerprinting, and so we briefly investigate this
application.

For the applications with larger sparsity levels, we note that spark
deficiency is incompatible with restricted isometry; indeed, any matrix which
is $(K,1-\varepsilon)$-RIP necessarily has spark strictly greater than $K$. As
such, in Chapter 2, we consider $M\times N$ _full spark_ matrices, that is,
matrices whose spark is as large as possible: $M+1$. We start by finding
various full spark constructions using Vandermonde matrices and discrete
Fourier transforms. These deterministic constructions are particularly
attractive as RIP candidates because they satisfy the necessary condition of
large spark, a property which is difficult to verify in general. To solidify
this notion of difficulty, we also show that the problem of testing whether a
matrix is full spark is hard for ${\mathsf{NP}}$ under randomized polynomial-
time reductions; this contrasts with the similar problem of testing for RIP,
which currently has unknown computational complexity [93]. To demonstrate that
full spark matrices are useful in their own right, we use them to solve
another important problem in sparse signal processing: signal recovery without
phase.

To date, the only deterministic RIP construction that manages to go beyond the
square-root bottleneck is given by Bourgain et al. [29]. In Chapter 3, we
discuss the technique they use to demonstrate RIP. It is important to stress
the significance of their contribution: Before [29], it was unclear how
deterministic analysis might break the bottleneck, and as such, their result
is a major theoretical achievement. On the other hand, their improvement over
the square-root bottleneck is notably slight compared to what random matrices
provide. However, we show that their technique can actually be used to
demonstrate RIP for sparsity levels much larger than $\sqrt{M}$, meaning one
could very well demonstrate random-like performance given the proper
construction. Our result applies their technique to random matrices, and it
inadvertently serves as a simple alternative proof that certain random
matrices are RIP. We also introduce another technique, and we show that it can
demonstrate RIP for similarly large sparsity levels. Later, we propose a
specific class of full spark matrices as candidates for being RIP. Using a
correspondence between these matrices and the Paley graphs, we observe certain
combinatorial and number-theoretic implications; this lends some probabilistic
intuition for a new bound on the clique number of Paley graphs of prime order.

After investigating deterministic RIP matrices in Chapters 1–3, we have yet to
find deterministic $M\times N$ sensing matrices which provably allow for the
efficient reconstruction of signals with sparsity level
$K\sim\smash{\frac{M}{\log^{\alpha}N}}$ for some $\alpha\geq 1$. To fill this
gap, in Chapter 4, we consider an alternative model for the sparsity in our
signal, namely, that the locations of the nonzero entries are drawn uniformly
at random. With this model, we show that a particularly simple algorithm
called _one-step thresholding_ can reconstruct the signal with high
probability provided $K=\mathrm{O}(\frac{M}{\log N})$. In fact, this
performance guarantee requires relatively modest structure in the sensing
matrix: that the columns are nearly orthogonal to each other and well-
distributed over the unit sphere. Indeed, this structural requirement is much
less stringent than RIP, and we provide a catalog of random and
_deterministic_ sensing matrices which satisfy these conditions. Later, we
further analyze the two conditions separately, finding new fundamental limits
on near-orthogonality and illustrating how to manipulate a given sensing
matrix to achieve good distribution over the sphere.

Throughout this thesis, we use ideas from _frame theory_ , and so it is
fitting to take some time to review the basics:

###  0.2 A brief introduction to frame theory

A _frame_ is a sequence $\\{\varphi_{i}\\}_{i\in\mathcal{I}}$ in a Hilbert
space $\mathcal{H}$ with _frame bounds_ $0<A\leq B<\infty$ that satisfy

$A\|x\|^{2}\leq\sum_{i\in\mathcal{I}}|\langle x,\varphi_{i}\rangle|^{2}\leq
B\|x\|^{2}\qquad\forall x\in\mathcal{H}.$

Frames were introduced by Duffin and Schaeffer [64] in the context of
nonharmonic Fourier analysis, where $\mathcal{H}=L^{2}(-\pi,\pi)$ and the
frame elements $\varphi_{i}$ are sinusoids of irregularly spaced frequencies.
However, the modern application of frame theory to signal processing came
decades later after the landmark paper of Daubechies et al. [55]. This paper
gave the first nontrivial examples of _tight frames_ , that is, frames with
equal frame bounds $A=B$. The utility of tight frames lies partially in their
painless reconstruction formula:

$x=\frac{1}{A}\sum_{i\in\mathcal{I}}\langle x,\varphi_{i}\rangle\varphi_{i}.$

Note that orthonormal bases are tight frames with $A=B=1$; in this way, frames
form a natural and useful generalization. While this founding research in
frame theory concerned frames over infinite-dimensional Hilbert spaces, many
of today’s applications of frames require a finite-dimensional treatment. In
fact, finite frame theory has found some important progress in the past decade
[18, 33, 42, 43, 47, 129], and the remainder of this section will discuss the
basics of this field.

In finite dimensions, say, $\mathcal{H}=\mathbb{C}^{M}$, a frame is given by
the columns of a full-rank $M\times N$ matrix
$\Phi=[\varphi_{1}\cdots\varphi_{N}]$ with $N\geq M$. Here, the extreme
eigenvalues of $\Phi\Phi^{*}$ are the frame bounds, and a tight frame has
equal frame bounds; equivalently, a frame $\Phi$ is tight if

  * (i)

the rows are equal-norm and orthogonal.

As established above, tight frames $\Phi$ are useful because they give a
redundant linear encoding $y=\Phi^{*}x$ of a signal $x$ that permits painless
recovery: $x=\frac{1}{A}\Phi y$, where $A$ is the common squared-norm of the
rows. Constructing tight frames is rather simple: perform Gram-Schmidt on the
rows of any frame to orthogonalize with equal norms. For the sake of democracy
in the entries of the encoding $y$, some applications opt for a _unit norm
tight frame (UNTF)_ [45], which has the additional property that

  * (ii)

the columns are unit-norm.

Constructing UNTFs has proven a bit more difficult, and there has been a lot
of research to characterize these [18, 33, 127]. As a special example of a
UNTF, take any rows from a discrete Fourier transform matrix and normalize the
resulting columns. In addition to unit-norm tightness, it is often beneficial
to have the columns of $\Phi$ be incoherent, and this occurs when $\Phi$ is an
_equiangular tight frame (ETF)_ , that is, a UNTF with the final property that

  * (iii)

the sizes of the inner products between distinct columns are equal.

ETFs do not exist for all matrix dimensions [19], and there are only three
general constructions to date [70, 141, 146]; these invoke block designs,
strongly regular graphs, and difference sets, respectively.

To mitigate any confusion, the reader should be aware that throughout the
literature, both UNTFs and ETFs are referred to as _Welch-bound equality
sequences_ [120]. As one might expect, each achieves equality in one of two
important inequalities, and it is important to review them. Consider $M\times
N$ matrices $\Phi=[\varphi_{1}\cdots\varphi_{N}]$ which have (ii), but not
necessarily (i) or (iii). As such, $\Phi$ might not be a frame, but we can
still take the Hilbert-Schmidt norm of the Gram matrix of its columns:

$\|\Phi^{*}\Phi\|_{\mathrm{HS}}^{2}=\sum_{n=1}^{N}\sum_{n^{\prime}=1}^{N}|\langle\varphi_{n},\varphi_{n^{\prime}}\rangle|^{2}.$

This is oftentimes called the _frame potential_ of $\Phi$ [18], and its
significance will become apparent shortly. Since the columns of $\Phi$ have
unit norm, and since $\Phi^{*}\Phi$ has at most $M$ nonzero eigenvalues, we
have

$N^{2}=\big{(}\mathrm{Tr}(\Phi^{*}\Phi)\big{)}^{2}=\bigg{(}\sum_{m=1}^{M}\lambda_{m}(\Phi^{*}\Phi)\bigg{)}^{2}\leq
M\sum_{m=1}^{M}\big{(}\lambda_{m}(\Phi^{*}\Phi)\big{)}^{2}=M\|\Phi^{*}\Phi\|_{\mathrm{HS}}^{2},$

where the inequality follows from the Cauchy-Schwarz inequality with the all-
ones vector. As such, equality is achieved if and only if the $M$ largest
eigenvalues of $\Phi^{*}\Phi$ are equal; since these are also the eigenvalues
of $\Phi\Phi^{*}$, this implies that $\Phi\Phi^{*}$ is a multiple identity,
and so $\Phi$ satisfies (ii). Thus, the frame potential of $\Phi$ satisfies
$\|\Phi^{*}\Phi\|_{\mathrm{HS}}^{2}\geq\frac{N^{2}}{M}$, with equality if and
only if $\Phi$ is a UNTF. Some call this the _Welch bound_ , and therefore say
that UNTFs have Welch-bound equality.

Another bound is also (more correctly) referred to as the Welch bound, and its
derivation uses the previous one. It concerns the _worst-case coherence_ of an
$M\times N$ matrix $\Phi=[\varphi_{1}\cdots\varphi_{N}]$ that satisfies (ii):

$\mu:=\max_{\begin{subarray}{c}n,n^{\prime}\in\\{1,\ldots,N\\}\\\ n\neq
n^{\prime}\end{subarray}}|\langle\varphi_{n},\varphi_{n^{\prime}}\rangle|.$

Since the columns of $\Phi$ have unit norm, we have

$\frac{N^{2}}{M}\leq\|\Phi^{*}\Phi\|_{\mathrm{HS}}^{2}=\sum_{n=1}^{N}\sum_{n^{\prime}=1}^{N}|\langle\varphi_{n},\varphi_{n^{\prime}}\rangle|^{2}\leq
N+N(N-1)\mu^{2}.$

Again, equality is achieved in the first inequality if and only if $\Phi$
satisfies (i). Also, equality is achieved in the second inequality if and only
if $\Phi$ satisfies (iii). Rearranging gives the following:

######  Theorem 3 (Welch bound [129, 143]).

Every $M\times N$ matrix $\Phi$ with unit-norm columns has worst-case
coherence

$\mu\geq\sqrt{\frac{N-M}{M(N-1)}},$

with equality if and only if $\Phi$ is an equiangular tight frame.

Equiangular lines have long been a subject of interest [97], and since
equiangular tight frames have minimal coherence, they are particularly useful
in a number of applications. Recent work on ETFs was spurred by results
inspired by communication theory [26, 84, 129] that show that the linear
encoders provided by ETFs are optimally robust against channel erasures. In
the real setting, the existence of an ETF of a given size is equivalent to the
existence of a strongly regular graph with certain corresponding parameters
[84, 122]. Such graphs have a rich history and remain an active topic of
research [31]; the specific ETFs which arise from particular graphs are
detailed in [141]. Some of this theory generalizes to the complex-variable
setting in the guise of complex Seidel matrices [25, 27, 65]. Many approaches
to constructing ETFs have focused on the special case in which every entry of
$\Phi$ is a root of unity [88, 115, 128, 130, 146]. Other approaches are given
in [46, 125, 137]. In the complex setting, much attention has focused on the
maximal case of $M^{2}$ vectors in $\mathbb{C}^{M}$ [9, 68, 91, 116, 121].

In the next chapter, we construct one of three known general families of ETFs,
and we evaluate their performance as RIP matrices. Having reviewed the frame-
theoretic background for this thesis, the interested reader is encouraged to
discover more about frame theory in [49].

##  Chapter 1 Steiner equiangular tight frames

In this chapter, we provide a new method for constructing equiangular tight
frames (ETFs), that is, matrices $\Phi$ with orthogonal and equal-norm rows,
and unit-norm columns whose inner products are equal in modulus. As discussed
earlier, such frames have minimal worst-case coherence, and are therefore
quite useful in applications. However, up to this point, they have proven
notoriously difficult to construct. By contrast, the construction of _Steiner
equianglar tight frames_ is particularly simple: a tensor-like combination of
a Steiner system and a regular simplex. This simplicity permits us to resolve
an open question regarding ETFs and the restricted isometry property (RIP): we
show that the RIP performance of some ETFs is unfortunately no better than the
so-called “square-root bottleneck.”

In the next section, we provide some simple tests for demonstrating whether a
given matrix is RIP; not only will this clarify the notion of the square-root
bottleneck, it will show how ETFs are in some sense optimal as deterministic
RIP matrices, thereby motivating the construction of ETFs. Later, we provide
the main result of this chapter, namely Theorem 7, which shows how certain
Steiner systems may be combined with regular simplices to produce ETFs [69,
70]. In the third section, we discuss each of the known infinite families of
such Steiner systems, and compute the corresponding infinite families of ETFs
they generate. We further provide some necessary and asymptotically sufficient
conditions, namely Theorem 8, to aid in the quest for discovering other
examples of such frames that lie outside of the known infinite families.
Finally, after demonstrating that Steiner ETFs fail to break the square-root
bottleneck, we consider their application to the design of digital
fingerprints to combat data piracy [103, 104].

###  1.1 Simple tests for restricted isometry

Before formally defining Steiner equiangular tight frames, we motivate their
construction by reviewing a couple common methods for determining whether a
matrix is RIP:

Positive test for RIP: | Apply the Gershgorin circle theorem to the submatrices $\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$.
---|---
Negative test for RIP: | Find a sparse vector in the nullspace of $\Phi$.

In what follows, we discuss each of these tests in more detail, and later, we
will use these tests to analyze Steiner ETFs as RIP matrices.

####  1.1.1 Applying Gershgorin’s circle thoerem

Take an $M\times N$ matrix $\Phi$, and recall Definition 1. For a given $K$,
we wish to find some $\delta$ for which $\Phi$ is $(K,\delta)$-RIP. To this
end, it is useful to consider the following expression for the restricted
isometry constant:

######  Lemma 4.

The smallest $\delta$ for which $\Phi$ is $(K,\delta)$-RIP is given by

$\delta_{K}=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\|\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-I_{K}\|_{2},$
(1.1)

where $\Phi_{\mathcal{K}}$ denotes the submatrix consisting of columns of
$\Phi$ indexed by $\mathcal{K}$.

###### Proof.

We first note that $\Phi$ being $(K,\delta)$-RIP trivially implies that $\Phi$
is $(K,\delta+\varepsilon)$-RIP for every $\varepsilon>0$. It therefore
suffices to show that the expression for $\delta_{K}$ in (1.1) satisfies two
criteria: (i) $\Phi$ is $(K,\delta_{K})$-RIP, and (ii) $\Phi$ is not
$(K,\delta)$-RIP for any $\delta<\delta_{K}$. To this end, pick some
$K$-sparse vector $x$. To prove (i), we need to show that

$(1-\delta_{K})\|x\|^{2}\leq\|\Phi x\|^{2}\leq(1+\delta_{K})\|x\|^{2}.$ (1.2)

Let $\mathcal{K}\subseteq\\{1,\dots,N\\}$ be the size-$K$ support of $x$, and
let $x_{\mathcal{K}}$ be the corresponding subvector. Then rearranging (1.2)
gives

$\delta_{K}\geq\Big{|}\tfrac{\|\Phi
x\|^{2}}{\|x\|^{2}}-1\Big{|}=\Big{|}\tfrac{\langle\Phi_{\mathcal{K}}x_{\mathcal{K}},\Phi_{\mathcal{K}}x_{\mathcal{K}}\rangle-\langle
x_{\mathcal{K}},x_{\mathcal{K}}\rangle}{\|x_{\mathcal{K}}\|^{2}}\Big{|}=\Big{|}\Big{\langle}\tfrac{x_{\mathcal{K}}}{\|x_{\mathcal{K}}\|},(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-I_{K})\tfrac{x_{\mathcal{K}}}{\|x_{\mathcal{K}}\|}\Big{\rangle}\Big{|}.$
(1.3)

Since the expression for $\delta_{K}$ in (1.1) maximizes (1.3) over all
supports $\mathcal{K}$ and entry values $x_{\mathcal{K}}$, the inequality
necessarily holds; that is, $\Phi$ is necessarily $(K,\delta_{K})$-RIP.
Furthermore, equality is achieved by the support $\mathcal{K}$ which maximizes
(1.1) and the eigenvector $x_{\mathcal{K}}$ corresponding to the largest
eigenvalue of $\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-I_{K}$; this proves
(ii). ∎

Note that we are not tasked with actually computing $\delta_{K}$; rather, we
recognize that $\Phi$ is $(K,\delta)$-RIP for every $\delta\geq\delta_{K}$,
and so we seek an upper bound on $\delta_{K}$. The following classical result
offers a particularly easy-to-calculate bound on eigenvalues:

######  Theorem 5 (Gershgorin circle theorem [73]).

For each eigenvalue $\lambda$ of a $K\times K$ matrix $A$, there is an index
$i\in\\{1,\ldots,K\\}$ such that

$\Big{|}\lambda-A[i,i]\Big{|}\leq\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{K}\Big{|}A[i,j]\Big{|}.$

To use this theorem, take some $\Phi$ with unit-norm columns. Note that
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$ is the Gram matrix of the columns
indexed by $\mathcal{K}$, and as such, the diagonal entries are $1$, and the
off-diagonal entries are inner products between distinct columns of $\Phi$.
Let $\mu$ denote the _worst-case coherence_ of
$\Phi=[\varphi_{1}\cdots\varphi_{N}]$:

$\mu:=\max_{\begin{subarray}{c}i,j\in\\{1,\ldots,N\\}\\\ i\neq
j\end{subarray}}|\langle\varphi_{i},\varphi_{j}\rangle|.$

Then the size of each off-diagonal entry of
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$ is $\leq\mu$, regardless of our
choice for $\mathcal{K}$. Therefore, for every eigenvalue $\lambda$ of
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-I_{K}$, the Gershgorin circle
theorem gives

$|\lambda|=|\lambda-0|\leq\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{K}|\langle\varphi_{i},\varphi_{j}\rangle|\leq(K-1)\mu.$
(1.4)

Since (1.4) holds for every eigenvalue $\lambda$ of
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-I_{K}$ and every choice of
$\mathcal{K}\subseteq\\{1,\ldots,N\\}$, we conclude from (1.1) that
$\delta_{K}\leq(K-1)\mu$, i.e., $\Phi$ is $(K,(K-1)\mu)$-RIP. This process of
using the Gershgorin circle theorem to demonstrate RIP for deterministic
constructions has become standard in the community [8, 60, 70].

Recall that random RIP constructions support sparsity levels $K$ on the order
of $\smash{\frac{M}{\log^{\alpha}N}}$ for some $\alpha\geq 1$. To see how well
the Gershgorin circle theorem demonstrates RIP, we need to express $\mu$ in
terms of $M$ and $N$. To this end, we consider the Welch bound (Theorem 3):

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

Since equiangular tight frames (ETFs) achieve equality in the Welch bound (as
demonstrated in Section 0.2), we can further analyze what it means for an
$M\times N$ ETF $\Phi$ to be $(K,(K-1)\mu)$-RIP. In particular, since Theorem
2 requires that $\Phi$ be $(2K,\delta)$-RIP for $\delta<\sqrt{2}-1$, it
suffices to have $\smash{\frac{2K}{\sqrt{M}}<\sqrt{2}-1}$, since this implies

$\delta=(2K-1)\mu=(2K-1)\sqrt{\frac{N-M}{M(N-1)}}\leq\frac{2K}{\sqrt{M}}<\sqrt{2}-1.$
(1.5)

That is, ETFs form sensing matrices that support sparsity levels $K$ on the
order of $\sqrt{M}$. Most other deterministic constructions have identical
bounds on sparsity levels [8, 60, 70]. In fact, since ETFs minimize coherence,
they are necessarily optimal constructions in terms of the Gershgorin
demonstration of RIP, but the question remains whether they are actually RIP
for larger sparsity levels; the Gershgorin demonstration fails to account for
cancellations in the sub-Gram matrices
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$, and so this technique is too weak
to indicate either possibility.

####  1.1.2 Spark considerations

Recall that, in order for an inversion process for (1) to exist, $\Phi$ must
map $K$-sparse vectors injectively, or equivalently, every subcollection of
$2K$ columns of $\Phi$ must be linearly independent. This linear independence
condition can be nicely expressed in more general terms, as the following
definition provides:

######  Definition 6.

The _spark_ of a matrix $\Phi$ is the size of the smallest linearly dependent
subset of columns, i.e.,

$\mathrm{Spark}(\Phi)=\min\Big{\\{}\|x\|_{0}:\Phi x=0,~{}x\neq 0\Big{\\}}.$

This definition was introduced by Dohono and Elad [61] to help build a theory
of sparse representation that later gave birth to modern compressed sensing.
The concept of spark is also found in matroid theory, where it goes by the
name _girth_. The condition that every subcollection of $2K$ columns of $\Phi$
is linearly independent is equivalent to $\mathrm{Spark}(\Phi)>2K$. Relating
spark to RIP, suppose $\Phi$ is $(K,\delta)$-RIP with
$\mathrm{Spark}(\Phi)\leq K$. Then there exists a nonzero $K$-sparse vector
$x$ such that $(1-\delta)\|x\|^{2}\leq\|\Phi x\|^{2}=0$, and so $\delta\geq
1$. The reason behind this stems from our necessary linear independence
condition: RIP implies linear independence, and so small spark implies linear
dependence, which in turn implies not RIP.

As an example of using spark to test RIP, consider the $M\times 2M$ matrix
$\Phi=[I~{}~{}F]$ that comes from concatenating the identity matrix $I$ with
the unitary discrete Fourier transform matrix $F$. In this example, columns
from a common orthonormal basis are orthogonal, while columns from different
bases have an inner product of size $\frac{1}{\sqrt{M}}$. As such, the
Gershgorin analysis gives that $\Phi$ is $(K,\delta)$-RIP for all
$\delta\geq\frac{K-1}{\sqrt{M}}$. However, when $M$ is a perfect square, the
Dirac comb $x$ of $\sqrt{M}$ Kronecker deltas is an eigenvector of $F$, and so
concatenating $Fx$ with $-x$ produces a $2\sqrt{M}$-sparse vector in the
nullspace of $\Phi$. In other words, $\mathrm{Spark}(\Phi)\leq 2\sqrt{M}$, and
so $\Phi$ is not $(K,1-\varepsilon)$-RIP for any $K\geq 2\sqrt{M}$. After
building Steiner equiangular tight frames, we will see that they perform
similarly as RIP matrices.

###  1.2 Constructing Steiner equiangular tight frames

Steiner systems and block designs have been studied for over a century; the
background facts presented here on these topics are taken from [1, 52]. In
short, a $(v,b,r,k,\lambda)$-block design is a $v$-element set $V$ along with
a collection $\mathcal{B}$ of $b$ size-$k$ subsets of $V$, dubbed blocks, that
have the property that any element of $V$ lies in exactly $r$ blocks and that
any $2$-element subset of $V$ is contained in exactly $\lambda$ blocks. The
corresponding incidence matrix is a $v\times b$ matrix $A$ that is one in a
given entry if that block contains the corresponding point, and is otherwise
zero; in this chapter, it is more convenient for us to work with the $b\times
v$ transpose $A^{\mathrm{T}}$ of this incidence matrix. Our particular
construction of ETFs involves a special class of block designs known as
$(2,k,v)$-Steiner systems. These have the property that any $2$-element subset
of $V$ is contained in exactly one block, that is, $\lambda=1$. With respect
to our purposes, the crucial facts are the following:

> The transpose $A^{\mathrm{T}}$ of the $\\{{0,1}\\}$-incidence matrix $A$ of
> a $(2,k,v)$-Steiner system:
>
>   1. (i)
>
> is of size $\smash{\frac{v(v-1)}{k(k-1)}}\times v$,
>
>   2. (ii)
>
> has $k$ ones in each row,
>
>   3. (iii)
>
> has $\smash{\frac{v-1}{k-1}}$ ones in each column, and
>
>   4. (iv)
>
> has the property that any two of its columns have a inner product of one.
>
>

The first three facts follow immediately from solving for
$\smash{b=\frac{v(v-1)}{k(k-1)}}$ and $\smash{r=\frac{v-1}{k-1}}$, using the
well-known relations $vr=bk$ and $r(k-1)=\lambda(v-1)$. Meanwhile, (iv) comes
from the fact that $\lambda=1$: each column of $A^{\mathrm{T}}$ corresponds to
an element of the set, and the inner product of any two columns computes the
number of blocks that contains the corresponding pair of points. This in hand,
we present the main result of this chapter; here, the density of a matrix is
the ratio of the number of nonzero entries of that matrix to the total number
of its entries:

######  Theorem 7.

Every $(2,k,v)$-Steiner system generates an equiangular tight frame consisting
of $N=v(1+\frac{v-1}{k-1})$ vectors in $M=\frac{v(v-1)}{k(k-1)}$-dimensional
space with redundancy $\smash{\frac{N}{M}=k(1+\frac{k-1}{v-1})}$ and density
$\smash{\frac{k}{v}=(\frac{N-1}{M(N-M)})^{\frac{1}{2}}}$.

Moreover, if there exists a real Hadamard matrix of size
$\smash{1+\frac{v-1}{k-1}}$, then such frames are real.

Specifically, a $\frac{v(v-1)}{k(k-1)}\times v(1+\frac{v-1}{k-1})$ ETF matrix
$\Phi$ may be constructed as follows:

  1. 1.

Let $A^{\mathrm{T}}$ be the $\smash{\frac{v(v-1)}{k(k-1)}}\times v$ transpose
of the adjacency matrix of a $(2,k,v)$-Steiner system.

  2. 2.

For each $j=1,\dotsc,v$, let $H_{j}$ be any
$(1+\frac{v-1}{k-1})\times(1+\frac{v-1}{k-1})$ matrix that has orthogonal rows
and unimodular entries, such as a possibly complex Hadamard matrix.

  3. 3.

For each $j=1,\dotsc,v$, let $\Phi_{j}$ be the
$\smash{\frac{v(v-1)}{k(k-1)}\times(1+\frac{v-1}{k-1})}$ matrix obtained from
the $j$th column of $A^{\mathrm{T}}$ by replacing each of the one-valued
entries with a distinct row of $H_{j}$, and every zero-valued entry with a row
of zeros.

  4. 4.

Concatenate and rescale the $\Phi_{j}$’s to form
$\Phi=(\frac{k-1}{v-1})^{\frac{1}{2}}[\Phi_{1}\cdots\Phi_{v}]$.

It is important to note that a version of this ETF construction was previously
employed by Seidel in Theorem 12.1 of [122] to prove the existence of certain
strongly regular graphs. In the context of that result, our contributions are
as follows: (i) the realization that when Seidel’s block design arises from a
particular type of Steiner system, the resulting strongly regular graph indeed
corresponds to a real ETF; (ii) noting that in this case, the graph theory may
be completely bypassed, as the idea itself directly produces the requisite
frame $\Phi$; and (iii) having bypassed the graph theory, realizing that this
construction immediately generalizes to the complex-variable setting if
Seidel’s requisite Hadamard matrix is permitted to become complex. These
realizations permit us to exploit the vast literature on Steiner systems [52]
to construct several new infinite families of ETFs, in both the real and
complex settings. Moreover, these ETFs are extremely sparse in their native
space; sparse tight frames have recently become a subject of interest in their
own right [44].

We refer to the ETFs produced by Theorem 7 as $(2,k,v)$-Steiner ETFs. In
essence, the idea of the construction is that the nonzero rows of any
particular $\Phi_{j}$ form a regular simplex in
$\smash{\frac{v-1}{k-1}}$-dimensional space; these vectors are automatically
equiangular amongst themselves; by requiring the entries of these simplices to
be unimodular, and requiring that distinct blocks have only one entry of
mutual support, one can further control the inner products of vectors arising
from distinct blocks. This idea is best understood by considering a simple
example, such as the ETF that arises from a $(2,2,4)$-Steiner system whose
transposed incidence matrix is

$A^{\mathrm{T}}=\begin{bmatrix}+&+&&\\\ +&&+&\\\ +&&&+\\\ &+&+&\\\ &+&&+\\\
&&+&+\end{bmatrix}.$

One can immediately verify that $A^{\mathrm{T}}$ corresponds to a block
design: there is a set $V$ of $v=4$ elements, each corresponding to a column
of $A^{\mathrm{T}}$; there is also a collection $\mathcal{B}$ of $b=6$ subsets
of $V$, each corresponding to a row of $A^{\mathrm{T}}$; every row contains
$k=2$ elements; every column contains $r=3$ elements; any given pair of
elements is contained in exactly one row, that is, $\lambda=1$, a fact which
is equivalent to having the inner product of any two distinct columns of
$A^{\mathrm{T}}$ being $1$. To form an ETF, for each of the four columns of
$A^{\mathrm{T}}$ we must choose a $4\times 4$ matrix $H$ with unimodular
entries and orthogonal rows; the size of $H$ is always one more than the
number $r$ of ones in a given column of $A^{\mathrm{T}}$. Though in principle
one may choose a different $H$ for each column, we choose them all to be the
same, namely the Hadamard matrix:

$H=\begin{bmatrix}+&+&+&+\\\ +&-&+&-\\\ +&+&-&-\\\ +&-&-&+\end{bmatrix}.$

To form the ETF, for each column of $A^{\mathrm{T}}$ we replace each of its
$1$-valued entries with a distinct row of $H$. Again, though in principle one
may choose a different sequence of rows of $H$ for each column, we simply
decide to use the second, third and fourth rows, in that order. The result is
a real ETF of $N=16$ elements of dimension $M=6$:

$\Phi=\frac{1}{\sqrt{3}}\left[\begin{array}[]{cccccccccccccccc}+&-&+&-&+&-&+&-\\\
+&+&-&-&&&&&+&-&+&-\\\ +&-&-&+&&&&&&&&&+&-&+&-\\\ &&&&+&+&-&-&+&+&-&-\\\
&&&&+&-&-&+&&&&&+&+&-&-\\\ &&&&&&&&+&-&-&+&+&-&-&+\end{array}\right].$ (1.6)

One can immediately verify that the rows of $\Phi$ are orthogonal and have
constant norm, implying $\Phi$ is indeed a tight frame. One can also easily
see that the inner products of two columns from the same block are
$-\frac{1}{3}$, while the inner products of columns from distinct blocks are
$\pm\frac{1}{3}$. Theorem 7 states that this behavior holds in general for any
appropriate choice of $A^{\mathrm{T}}$ and $H$.

###### Proof of Theorem 7.

To verify $\Phi$ is a tight frame, note that the inner product of any two
distinct rows of $\Phi$ is zero, as they are the sum of the inner products of
the corresponding rows of the $\Phi_{j}$’s over all $j=1,\dotsc,v$; for any
$j$, these shorter inner products are necessarily zero, as they either
correspond to inner products of distinct rows of $H_{j}$ or to inner products
with zero vectors. Moreover, the rows of $\Phi$ have constant norm: as noted
in (ii) above, each row of $A^{\mathrm{T}}$ contains $k$ ones; since each
$H_{j}$ has unimodular entries, the squared-norm of any row of $\Phi$ is the
squared-scaling factor $\frac{k-1}{v-1}$ times a sum of
$\smash{k(1+\frac{v-1}{k-1})}$ ones, which, as is necessary for any unit norm
tight frame, equals the redundancy $\smash{\frac{N}{M}=k(1+\frac{k-1}{v-1})}$.

Having that $\Phi$ is tight, we show $\Phi$ is also equiangular. We first note
that the columns of $\Phi$ have unit norm: the squared-norm of any column of
$\Phi$ is $\smash{\frac{k-1}{v-1}}$ times the squared-norm of a column of one
of the $\Phi_{j}$’s; since the entries of $H_{j}$ are unimodular and (iii)
above gives that each column of $A^{\mathrm{T}}$ contains
$\smash{\frac{v-1}{k-1}}$ ones, the squared-norm of any column of $\Phi$ is
$\smash{(\frac{k-1}{v-1})(\frac{v-1}{k-1})1=1}$, as claimed. Moreover, the
inner products of any two distinct columns of $\Phi$ has constant modulus.
Indeed, the fact (iv) that any two distinct columns of $A^{\mathrm{T}}$ have
but a single entry of mutual support implies the same is true for columns of
$\Phi$ that arise from distinct $\Phi_{j}$ blocks, implying the inner product
of such columns is $\smash{\frac{k-1}{v-1}}$ times the product of two
unimodular numbers. That is, the squared-magnitude of the inner products of
two columns that arise from distinct blocks is
$\smash{\frac{N-M}{M(N-1)}=(\frac{k-1}{v-1})^{2}}$, as needed. Meanwhile, the
same holds true for columns that arise from the same block $\Phi_{j}$. To see
this, note that since $H_{j}$ is a scalar multiple of a unitary matrix, its
columns are orthogonal. Moreover, $\Phi_{j}$ contains all but one of the
$H_{j}$’s rows, namely one for each of the $1$-valued entries of
$A^{\mathrm{T}}$, à la (iii). Thus, the inner products of the portions of
$H_{j}$ that lie in $\Phi_{j}$ are their entire inner product of zero, less
the contribution from the left-over entries. Overall, the inner product of two
columns of $\Phi$ that arise from the same $\Phi_{j}$ block is
$\smash{\frac{k-1}{v-1}}$ times the negated product of one entry of $H_{j}$
and the conjugate of another; since the entries of $H_{j}$ are unimodular, we
have that the squared-magnitude of such inner products is
$\smash{\frac{N-M}{M(N-1)}=(\frac{k-1}{v-1})^{2}}$, as needed.

Thus $\Phi$ is an ETF. Moreover, as noted above, its redundancy is
$\smash{\frac{N}{M}=k(1+\frac{k-1}{v-1})}$. All that remains to verify is its
density: as the entries of each $H_{j}$ are all nonzero, the proportion of
$\Phi$’s nonzero entries is the same as that of the incidence matrix $A$,
which is clearly $\frac{k}{v}$, having $k$ ones in each $v$-dimensional row.
Moreover, substituting $\smash{N=v(1+\frac{v-1}{k-1})}$ and
$\smash{M=\frac{v(v-1)}{k(k-1)}}$ into the quantity
$\smash{\frac{N-1}{M(N-M)}}$ reveals it to be $\frac{k^{2}}{v^{2}}$, and so
the density can be alternatively expressed as
$\smash{(\frac{N-1}{M(N-M)})^{\frac{1}{2}}}$. ∎

In the next section, we apply Theorem 7 to produce several infinite families
of Steiner ETFs. Before doing so, however, we pause to remark on the
redundancy and sparsity of such frames. In particular, note that since the
parameters $k$ and $v$ of the requisite Steiner system always satisfy $2\leq
k\leq v$, the redundancy $k(1+\frac{k-1}{v-1})$ of Steiner ETFs is always
between $k$ and $2k$; the redundancy is therefore on the order of $k$, and is
always strictly greater than $2$. If a low-redundancy ETF is desired, one can
always take the Naimark complement [43] of an ETF of $N$ elements in
$M$-dimensional space to produce a new ETF of $N$ elements in
$(N-M)$-dimensional space; though the complement process does not preserve
sparsity, it nevertheless transforms any Steiner ETF into a new ETF whose
redundancy is strictly less than $2$. However, such a loss of sparsity should
not be taken lightly. Indeed, the low density of Steiner ETFs gives them a
large computational advantage over their non-sparse brethren.

To clarify, the most common operation in frame-theoretic applications is the
evaluation of the analysis operator $\Phi^{*}$ on a given
$x\in\mathbb{C}^{M}$. For a non-sparse $\Phi$, this act of computing
$\Phi^{*}x$ requires $\mathrm{O}(MN)$ operations; for a frame $\Phi$ of
density $D$, this cost is reduced to $\mathrm{O}(DMN)$. Indeed, using the
explicit value of $\smash{D=(\frac{N-1}{M(N-M)})^{\frac{1}{2}}}$ given in
Theorem 7 as well as the aforementioned fact that the redundancy of such
frames necessarily satisfies $\frac{N}{M}>2$, we see that the cost of
evaluating $\Phi^{*}x$ when $\Phi$ is a Steiner ETF is on the order of
$\smash{(\frac{M(N-1)}{N-M})^{\frac{1}{2}}N<(2M)^{\frac{1}{2}}N}$ operations,
a dramatic cost savings when $M$ is large. Further efficiency is gained when
$\Phi$ is real, as its nonzero elements are but a fixed scaling factor times
the entries of a real Hadamard matrix, implying $\Phi^{*}x$ can be evaluated
using only additions and subtractions. The fact that every entry of $\Phi$ is
either $0$ or $\pm 1$ further makes real Steiner ETFs potentially useful for
applications that require binary measurements, such as design of experiments.

###  1.3 Examples of Steiner equiangular tight frames

In this section, we apply Theorem 7 to produce several infinite families of
Steiner ETFs. When designing frames for real-world applications, three
considerations reign supreme: size, redundancy and sparsity. As noted above,
every Steiner ETF is very sparse, a serious computational advantage in high-
dimensional signal processing. Moreover, some of these infinite families, such
as those arising from finite affine and projective geometries, provide great
flexibility in choosing the ETF’s size and redundancy. Indeed, these
constructions provide the first known guarantee that for a given application,
one is always able to find ETFs whose frame elements lie in a space whose
dimension matches, up to an order of magnitude, that of one’s desired class of
signals, while simultaneously permitting one to have an almost arbitrary fixed
level of redundancy, a handy weapon in the fight against noise. To be clear,
recall that the redundancy of a Steiner ETF is always strictly greater than
$2$. Moreover, general bounds on the maximal number of equiangular lines [97]
require that any real $M\times N$ ETF satisfy $\smash{N\leq\frac{M(M+1)}{2}}$
and any complex ETF satisfy $N\leq M^{2}$; thus, the redundancy of an ETF is
never truly arbitrary. Nevertheless, if one prescribes a given level of
redundancy in advance, the Steiner method can produce arbitrarily large ETFs
whose redundancy is approximately the prime power closest to the desired
level.

####  1.3.1 Infinite families of Steiner equiangular tight frames

We now detail eight infinite families of ETFs, each generated by applying
Theorem 7 to one of the eight completely understood infinite families of
$(2,k,v)$-Steiner systems. Table 1.1 summarizes the most important features of
each family, and Table 1.2 gives the first few examples of each type,
summarizing those that lie in 100 dimensions or less.

##### All two-element blocks: $(2,2,v)$-Steiner ETFs for any $v\geq 2$.

The first infinite family of Steiner systems is so simple that it is usually
not discussed in the design-theory literature. For any $v\geq 2$, let $V$ be a
$v$-element set, and let $\mathcal{B}$ be the collection of all $2$-element
subsets of $V$. Clearly, we have $\smash{b=\frac{v(v-1)}{2}}$ blocks, each of
which contains $k=2$ elements; each point is contained in $r=v-1$ blocks, and
each pair of points is indeed contained in but a single block, that is,
$\lambda=1$.

By Theorem 7, the ETFs arising from these $(2,2,v)$-Steiner systems consist of
$N=v(1+\frac{v-1}{k-1})=v^{2}$ vectors in
$\smash{M=\frac{v(v-1)}{k(k-1)}=\frac{v(v-1)}{2}}$-dimensional space. Though
these frames can become arbitrarily large, they do not provide any freedom
with respect to redundancy: $\smash{\frac{N}{M}=2\frac{v}{v-1}}$ is
essentially $2$. These frames have density $\smash{\frac{k}{v}=\frac{2}{v}}$.
Moreover, these ETFs can be real-valued if there exists a real Hadamard matrix
of size $\smash{1+\frac{v-1}{k-1}}=v$. In particular, it suffices to have $v$
to be a power of $2$; should the Hadamard conjecture prove true, it would
suffice to have $v$ divisible by $4$.

One example of such an ETF with $v=4$ was given in the previous section. For a
complex example, consider $v=3$. The $b\times v$ transposed incidence matrix
$A^{\mathrm{T}}$ is $3\times 3$, with each row corresponding to a given
$2$-element subset of $\\{{0,1,2}\\}$:

$A^{\mathrm{T}}=\begin{bmatrix}+&+&\\\ +&&+\\\ &+&+\end{bmatrix}.$

To form the corresponding $3\times 9$ ETF $\Phi$, we need a $3\times 3$
unimodular matrix with orthogonal rows, such as a DFT; letting
$\smash{\omega=\mathrm{e}^{2\pi\mathrm{i}/3}}$, we can take

$H=\left[\begin{array}[]{lll}1&1&1\\\ 1&\omega^{2}&\omega\\\
1&\omega&\omega^{2}\end{array}\right].$

To form $\Phi$, in each column of $A^{\mathrm{T}}$, we replace each $1$-valued
entry with a distinct row of $H$. Always choosing the second and third rows
yields an ETF of $9$ elements in $\mathbb{C}^{3}$:

$\Phi=\frac{1}{\sqrt{2}}\left[\begin{array}[]{lllllllll}1&\omega^{2}&\omega&1&\omega^{2}&\omega&&&\\\
1&\omega&\omega^{2}&&&&1&\omega^{2}&\omega\\\
&&&1&\omega&\omega^{2}&1&\omega&\omega^{2}\end{array}\right].$

This is the only known instance of when the Steiner-based construction of
Theorem 7 produces a maximal ETF, that is, one that has $N=M^{2}$.

##### Steiner triple systems: $(2,3,v)$-Steiner ETFs for any $v\equiv 1,3\bmod
6$.

Steiner triple systems, namely $(2,3,v)$-Steiner systems, have been a subject
of interest for over a century, and are known to exist precisely when $v\equiv
1,3\bmod 6$ [52]. Each of the $\smash{b=\frac{v(v-1)}{6}}$ blocks contains
$k=3$ points, while each point is contained in $\smash{r=\frac{v-1}{2}}$
blocks. The corresponding ETFs produced by Theorem 7 consist of
$\smash{\frac{v(v+1)}{2}}$ vectors in $\smash{\frac{v(v-1)}{6}}$-dimensional
space. The density of such frames is $\frac{3}{v}$. As with ETFs stemming from
$2$-element blocks, Steiner triple systems offer little freedom in terms of
redundancy: $\smash{\frac{N}{M}=3\frac{v+1}{v-1}}$ is always approximately
$3$. Such ETFs can be real if there exists a real Hadamard matrix of size
$\smash{\frac{v+1}{2}}$.

##### Four element blocks: $(2,4,v)$-Steiner ETFs for any $v\equiv 1,4\bmod
12$.

It is known that $(2,4,v)$-Steiner systems exist precisely when $v\equiv
1,4\bmod 12$ [1]. Continuing the trend of the previous two families, these
ETFs can vary in size but not in redundancy: they consist of
$\smash{\frac{v(v+2)}{3}}$ vectors in $\smash{\frac{v(v-1)}{12}}$-dimensional
space, having redundancy $\smash{4\frac{v+2}{v-1}}$ and density
$\smash{\frac{4}{v}}$. Interestingly, such frames can never be real: with the
exception of the trivial $1\times 1$ and $2\times 2$ cases, the dimensions of
all real Hadamard matrices are divisible by $4$; since $v\equiv 1,4\bmod 12$,
the requisite matrices $H$ here are of size $\smash{\frac{v+2}{3}}\equiv
1,2\bmod 4$.

##### Five element blocks: $(2,5,v)$-Steiner ETFs for any $v\equiv 1,5\bmod
20$.

It is also known that $(2,5,v)$-Steiner systems exist precisely when $v\equiv
1,5\bmod 20$ [1]. The corresponding ETFs consist of $\smash{\frac{v(v+3)}{4}}$
vectors in $\smash{\frac{v(v-1)}{20}}$-dimensional space, having redundancy
$\smash{5\frac{v+3}{v-1}}$ and density $\smash{\frac{5}{v}}$. Such frames can
be real whenever there exists a real Hadamard matrix of size $\frac{v+3}{4}$.
In particular, letting $v=45$, we see that there exists a real Steiner ETF of
$540$ vectors in $99$-dimensional space, a fact not obtained from any other
known infinite family.

##### Affine geometries: $(2,q,q^{n})$-Steiner ETFs for any prime power $q$,
$n\geq 2$.

At this point, the constructions depart from those previously considered,
allowing both $k$ and $v$ to vary. In particular, using techniques from finite
geometry, one can show that for any prime power $q$ and any $n\geq 2$, there
exists a $(2,k,v)$-Steiner system with $k=q$ and $v=q^{n}$ [52]. The
corresponding ETFs consist of $\smash{q^{n}(1+\frac{q^{n}-1}{q-1})}$ vectors
in $\smash{q^{n-1}(\frac{q^{n}-1}{q-1}})$-dimensional space. Like the
preceding four classes of Steiner ETFs, these frames can grow arbitrarily
large: fixing any prime power $q$, one may manipulate $n$ to produce ETFs of
varying orders of magnitude. However, unlike the four preceding classes, these
affine Steiner ETFs also provide great flexibility in choosing redundancy.
That is, they provide the ability to pick $M$ and $N$ somewhat independently.
Indeed, the redundancy of such frames $q(1+\frac{q-1}{q^{n}-1})$ is
essentially $q$, which may be an arbitrary prime power. Moreover, as these
frames grow large, they also become increasingly sparse: their density is
$\smash{\frac{1}{q^{n-1}}}$. Because of their high sparsity and flexibility
with regards to size and redundancy, these frames, along with their projective
geometry-based cousins detailed below, are perhaps the best known candidates
for use in ETF-based applications. Such ETFs can be real if there exists a
real Hadamard matrix of size $1+\frac{q^{n}-1}{q-1}$, such as whenever $q=2$,
or when $q=5$ and $n=3$.

##### Projective geometries: $(2,q+1,\frac{q^{n+1}-1}{q-1})$-Steiner ETFs for
any prime power $q$, $n\geq 2$.

With finite geometry, one can show that for any prime power $q$ and any $n\geq
2$, there exists a $(2,k,v)$-Steiner system with $k=q+1$ and
$\smash{v=\frac{q^{n+1}-1}{q-1}}$ [52]. Qualitatively speaking, the ETFs that
these projective geometries generate share much in common with their affinely
generated cousins, possessing very high sparsity and great flexibility with
respect to size and redundancy. The technical details are as follows: they
consist of $\smash{\frac{q^{n+1}-1}{q-1}(1+\frac{q^{n}-1}{q-1})}$ vectors in
$\smash{\frac{(q^{n}-1)(q^{n+1}-1)}{(q+1)(q-1)^{2}}}$-dimensional space, with
density $\smash{\frac{q^{2}-1}{q^{n+1}-1}}$ and redundancy
$\smash{(q+1)(1+\frac{q-1}{q^{n}-1})}$. These frames can be real if there
exists a real Hadamard matrix of size $1+\frac{q^{n}-1}{q-1}$; note this
restriction is identical to the one for ETFs generated by affine geometries
for the same $q$ and $n$, implying that real Steiner ETFs generated by finite
geometries always come in pairs, such as the $6\times 16$ and $7\times 28$
ETFs generated when $q=2$, $n=2$, and the $28\times 64$ and $35\times 120$
ETFs generated when $q=2$, $n=3$.

##### Unitals: $(2,q+1,q^{3}+1)$-Steiner ETFs for any prime power $q$.

For any prime power $q$, one can show that there exists a $(2,k,v)$-Steiner
system with $k=q+1$ and $v=q^{3}+1$ [52]. Though one may pick a redundancy of
one’s liking, such a choice confines one to ETFs of a given size: they consist
of $(q^{2}+1)(q^{3}+1)$ vectors in
$\smash{\frac{q^{2}(q^{3}+1)}{q+1}}$-dimensional space, having redundancy
$\smash{(q+1)(1+\frac{1}{q^{2}})}$ and density $\smash{\frac{q+1}{q^{3}+1}}$.
These ETFs can never be real: the requisite Hadamard matrices are of size
$q^{2}+1$ which is never divisible by $4$ since $0$ and $1$ are the only
squares in $\mathbb{Z}_{4}$.

##### Denniston designs: $(2,2^{r},2^{r+s}+2^{r}-2^{s})$-Steiner ETFs for any
$2\leq r<s$.

For any $2\leq r<s$, one can show that there exists a $(2,k,v)$-Steiner system
with $k=2^{r}$ and $v=2^{r+s}+2^{r}-2^{s}$ [52]. By manipulating $r$ and $s$,
one can independently determine the order of magnitude of redundancy and size:
the corresponding ETFs consist of $(2^{s}+2)(2^{r+s}+2^{r}-2^{s})$ vectors in
$\smash{\frac{(2^{s}+1)(2^{r+s}+2^{r}-2^{s})}{2^{r}}}$-dimensional space,
having redundancy $\smash{2^{r}\frac{2^{s}+2}{2^{s}+1}}$ and density
$\smash{\frac{2^{r}}{2^{r+s}+2^{r}-2^{s}}}$. As such, this family has some
qualitative similarities to the familes of ETFs produced by affine and
projective geometries. However, unlike those families, the ETFs produced by
Denniston designs can never be real: the requisite Hadamard matrices are of
size $2^{s}+2$, which is never divisible by $4$.

Name | $M$ | $N$ | Redundancy | Real? | Restrictions
---|---|---|---|---|---
$2$-blocks | $\frac{v(v-1)}{2}$ | $v^{2}$ | $2\frac{v}{v-1}$ | $v$ | None
$3$-blocks | $\frac{v(v-1)}{6}$ | $\frac{v(v+1)}{2}$ | $3\frac{v+1}{v-1}$ | $\frac{v+1}{2}$ | $v\equiv 1,3\bmod 6$
$4$-blocks | $\frac{v(v-1)}{12}$ | $\frac{v(v+2)}{3}$ | $4\frac{v+2}{v-1}$ | Never | $v\equiv 1,4\bmod 12$
$5$-blocks | $\frac{v(v-1)}{20}$ | $\frac{v(v+3)}{4}$ | $5\frac{v+3}{v-1}$ | $\frac{v+3}{4}$ | $v\equiv 1,5\bmod 20$
Affine | $q^{n-1}(\frac{q^{n}-1}{q-1})$ | $q^{n}(1+\frac{q^{n}-1}{q-1})$ | $q(1+\frac{q-1}{q^{n}-1})$ | $1+\frac{q^{n}-1}{q-1}$ |  prime power $q$, $n\geq 2$
Projective | $\frac{(q^{n}-1)(q^{n+1}-1)}{(q+1)(q-1)^{2}}$ | $\frac{q^{n+1}-1}{q-1}(1+\frac{q^{n}-1}{q-1})$ | $(q+1)(1+\frac{q-1}{q^{n}-1})$ | $1+\frac{q^{n}-1}{q-1}$ |  prime power $q$, $n\geq 2$
Unitals | $\frac{q^{2}(q^{3}+1)}{q+1}$ | $(q^{2}\\!+1)(q^{3}\\!+1)$ | $(q+1)(1+\frac{1}{q^{2}})$ | Never |  prime power $q$
Denniston | $\frac{(2^{s}+1)(2^{r+s}+2^{r}-2^{s})}{2^{r}}$ | $(2^{s}\\!+2)(2^{r+s}\\!+2^{r}\\!-2^{s})$ | $2^{r}\frac{2^{s}+2}{2^{s}+1}$ | Never | $2\leq r<s$
Table 1.1: Eight infinite families of Steiner ETFs, each arising from a known infinite family of $(2,k,v)$-Steiner designs. Each family permits both $M$ and $N$ to grow very large, but only a few families—affine, projective and Denniston—give one the freedom to simultaneously control the proportion between $M$ and $N$, namely the redundancy $\frac{N}{M}$ of the ETF. The column denoted “Real?” indicates the size for which a real Hadamard matrix must exist in order for the resulting ETF to be real; it suffices to have this size be a power of $2$; if the Hadamard conjecture is true, it would suffice for this number to be divisible by $4$. $M$ | $N$ | $k$ | $v$ | $r$ | $\mathbb{R}/\mathbb{C}$ | Construction of the Steiner system
---|---|---|---|---|---|---
6 | 16 | 2 | 4 | 3 | $\mathbb{R}$ |  $2$-blocks of $v=4$; Affine with $q=2$, $n=2$
7 | 28 | 3 | 7 | 3 | $\mathbb{R}$ |  $3$-blocks of $v=7$; Projective with $q=2$, $n=2$
28 | 64 | 2 | 8 | 7 | $\mathbb{R}$ |  $2$-blocks of $v=8$; Affine with $q=2$, $n=3$
35 | 120 | 3 | 15 | 7 | $\mathbb{R}$ |  $3$-blocks of $v=15$; Projective with $q=2$, $n=3$
66 | 144 | 2 | 12 | 11 | $\mathbb{R}$ |  $2$-blocks of $v=12$
99 | 540 | 5 | 45 | 11 | $\mathbb{R}$ |  $5$-blocks of $v=45$
3 | 9 | 2 | 3 | 2 | $\mathbb{C}$ |  $2$-blocks of $v=3$
10 | 25 | 2 | 5 | 4 | $\mathbb{C}$ |  $2$-blocks of $v=5$
12 | 45 | 3 | 9 | 4 | $\mathbb{C}$ |  $3$-blocks of $v=9$; Affine with $q=3$, $n=2$
13 | 65 | 4 | 13 | 4 | $\mathbb{C}$ |  $4$-blocks of $v=13$; Projective with $q=3$, $n=2$
15 | 36 | 2 | 6 | 5 | $\mathbb{C}$ |  $2$-blocks of $v=6$
20 | 96 | 4 | 16 | 5 | $\mathbb{C}$ |  $4$-blocks of $v=16$; Affine with $q=4$, $n=2$
21 | 49 | 2 | 7 | 6 | $\mathbb{C}$ |  $2$-blocks of $v=7$
21 | 126 | 5 | 21 | 5 | $\mathbb{C}$ |  $5$-blocks of $v=21$; Projective with $q=4$, $n=2$
26 | 91 | 3 | 13 | 6 | $\mathbb{C}$ |  $3$-blocks of $v=13$
30 | 175 | 5 | 25 | 6 | $\mathbb{C}$ |  $5$-blocks of $v=25$; Affine with $q=5$, $n=2$
31 | 217 | 6 | 31 | 6 | $\mathbb{C}$ | Projective with $q=5$, $n=2$
36 | 81 | 2 | 9 | 8 | $\mathbb{C}$ |  $2$-blocks of $v=9$
45 | 100 | 2 | 10 | 9 | $\mathbb{C}$ |  $2$-blocks of $v=10$
50 | 225 | 4 | 25 | 8 | $\mathbb{C}$ |  $4$-blocks of $v=25$
55 | 121 | 2 | 11 | 10 | $\mathbb{C}$ |  $2$-blocks of $v=11$
56 | 441 | 7 | 49 | 8 | $\mathbb{C}$ | Affine with $q=7$, $n=2$
57 | 190 | 3 | 19 | 9 | $\mathbb{C}$ |  $3$-blocks of $v=19$
57 | 513 | 8 | 57 | 8 | $\mathbb{C}$ | Projective with $q=7$, $n=2$
63 | 280 | 4 | 28 | 9 | $\mathbb{C}$ | Unital with $q=3$; Denniston with $r=2$, $s=3$
70 | 231 | 3 | 21 | 10 | $\mathbb{C}$ |  $3$-blocks of $v=21$
72 | 640 | 8 | 64 | 9 | $\mathbb{C}$ | Affine with $q=8$, $n=2$
73 | 730 | 9 | 73 | 9 | $\mathbb{C}$ | Projective with $q=8$, $n=2$
78 | 169 | 2 | 13 | 12 | $\mathbb{C}$ |  $2$-blocks of $v=13$
82 | 451 | 5 | 41 | 19 | $\mathbb{C}$ |  $5$-blocks of $v=41$
90 | 891 | 9 | 81 | 10 | $\mathbb{C}$ | Affine with $q=9$, $n=2$
91 | 196 | 2 | 14 | 13 | $\mathbb{C}$ |  $2$-blocks of $v=14$
91 | 1001 | 10 | 91 | 10 | $\mathbb{C}$ | Projective with $q=9$, $n=2$
100 | 325 | 3 | 25 | 12 | $\mathbb{C}$ |  $3$-blocks of $v=25$
Table 1.2: The ETFs of dimension 100 or less that can be constructed by
applying Theorem 7 to the eight infinite families of Steiner systems detailed
in Section 1.3. That is, these ETFs represent the first few examples of the
general constructions summarized in Table 1.1. For each ETF, we give the
dimension $M$ of the underlying space, the number of frame vectors $N$, as
well as the number $k$ of elements that lie in any block of a $v$-element set
in the corresponding $(2,k,v)$-Steiner system. We further give the value $r$
of the number of blocks that contain a given point; by Theorem 8,
$|{\langle{f_{n}},{f_{n^{\prime}}}\rangle}|=\frac{1}{r}$ measures the angle
between any two frame elements. We also indicate whether the given frame is
real or complex, and the method(s) of constructing the corresponding Steiner
system.

####  1.3.2 Conditions for the existence of Steiner equiangular tight frames

$(2,k,v)$-Steiner systems have been actively studied for over a century, with
many celebrated results. Nevertheless, much about these systems is still
unknown. In this subsection, we discuss some known partial characterizations
of the Steiner systems which lie outside of the eight families we have already
discussed, as well as what these results tell us about the existence of
certain ETFs. To begin, recall that, for a given $k$ and $v$, if a
$(2,k,v)$-Steiner system exists, then the number $r$ of blocks that contain a
given point is necessarily $\smash{\frac{v-1}{k-1}}$, while the total number
of blocks $b$ is $\smash{\frac{v(v-1)}{k(k-1)}}$. As such, in order for a
$(2,k,v)$-Steiner system to exist, it is necessary for $(k,v)$ to be
admissible, that is, to have the property that $\smash{\frac{v-1}{k-1}}$ and
$\smash{\frac{v(v-1)}{k(k-1)}}$ are integers.

However, this property is not sufficient for existence: it is known that a
$(2,6,16)$-Steiner system does not exist [1] despite the fact that
$\smash{\frac{v-1}{k-1}}=3$ and $\smash{\frac{v(v-1)}{k(k-1)}}=8$. In fact,
letting $v$ be either $16$, $21$, $36$, or $46$ results in an admissible pair
with $k=6$, despite the fact that none of the corresponding Steiner systems
exist; there are twenty-nine additional values of $v$ which form an admissible
pair with $k=6$ and for which the existence of a corresponding Steiner system
remains an open problem [1]. Similar nastiness arises with $k\geq 7$. The good
news is that admissibility, though not sufficient for existence, is, in fact,
asymptotically sufficient: for any fixed $k$, there exists a corresponding
admissible index $v_{0}(k)$ for which for all $v>v_{0}(k)$ such that
$\smash{\frac{v-1}{k-1}}$ and $\smash{\frac{v(v-1)}{k(k-1)}}$ are integers, a
$(2,k,v)$-Steiner system indeed exists [1]. Moreover, explicit values of
$v_{0}(k)$ are known for small $k$: $v_{0}(6)=801$, $v_{0}(7)=2605$,
$v_{0}(8)=3753$, $v_{0}(9)=16497$. We now detail the ramifications of these
design-theoretic results on frame theory:

######  Theorem 8.

If an $M\times N$ Steiner equiangular tight frame exists, then letting
$\smash{\alpha=(\frac{N-M}{M(N-1)})^{\frac{1}{2}}}$, the corresponding block
design has parameters:

$v=\tfrac{N\alpha}{1+\alpha},\qquad b=M,\qquad r=\tfrac{1}{\alpha},\qquad
k=\tfrac{N}{M(1+\alpha)}.$

In particular, if such a frame exists, then these expressions for $v$, $k$ and
$r$ are necessarily integers.

Conversely, for any fixed $k\geq 2$, there exists an index $v_{0}(k)$ for
which for all $v>v_{0}(k)$ such that $\smash{\frac{v-1}{k-1}}$ and
$\smash{\frac{v(v-1)}{k(k-1)}}$ are integers, there exists a Steiner
equiangular tight frame of $\smash{v(1+\frac{v-1}{k-1})}$ vectors for a space
of dimension $\smash{\frac{v(v-1)}{k(k-1)}}$.

In particular, for any fixed $k\geq 2$, letting $v$ be either $jk(k-1)+1$ or
$jk(k-1)+k$ for increasingly large values of $j$ results in a sequence of
Steiner equiangular tight frames whose redundancy is asymptotically $k$; these
frames can be real if there exist real Hadamard matrices of sizes $jk+1$ or
$jk+2$, respectively.

###### Proof.

To prove the necessary conditions on $M$ and $N$, recall that Steiner ETFs,
namely those ETFs produced by Theorem 7, have $\smash{N=v(1+\frac{v-1}{k-1})}$
and $\smash{M=\frac{v(v-1)}{k(k-1)}}$. Together, these two equations imply
$N=v+kM$. Solving for $k$ and substituting the resulting expression into
$\smash{N=v(1+\frac{v-1}{k-1})}$ yields the quadratic equation
$0=(M-1)v^{2}+2(N-M)v-N(N-M)$. With some algebra, the only positive root of
this equation can be found to be $\smash{v=\frac{N\alpha}{1+\alpha}}$, as
claimed. Substituting this expression for $v$ into $N=v+kM$ yields
$\smash{k=\tfrac{N}{M(1+\alpha)}}$. Having $v$ and $k$, the previously
mentioned relations $bk=vr$ and $v-1=r(k-1)$ imply
$\smash{r=\frac{v-1}{k-1}=\frac{1}{\alpha}}$ and $\smash{b=\frac{v}{k}r=M}$,
as claimed.

The second set of conclusions is the result of applying Theorem 7 to the
aforementioned $(2,k,v)$-Steiner ETFs that are guaranteed to exist for all
sufficiently large $v$, provided $\smash{\frac{v-1}{k-1}}$ and
$\smash{\frac{v(v-1)}{k(k-1)}}$ are integers. The final set of conclusions are
then obtained by applying this fact in the special cases where $v$ is either
$jk(k-1)+1$ or $jk(k-1)+k$. In particular, if $v=jk(k-1)+1$ then
$\smash{\frac{v-1}{k-1}=jk}$ and
$M=\smash{\frac{v(v-1)}{k(k-1)}=j\big{(}jk(k-1)+1\big{)}}$ are integers, and
the resulting ETF of $(jk+1)\big{(}jk(k-1)+1\big{)}$ vectors has a redundancy
of $\smash{k+\frac{1}{j}}$ that tends to $k$ for large $j$; such an ETF can be
real if there exists a real Hadamard matrix of size $jk+1$. Meanwhile, if
$v=jk(k-1)+k$ then $\smash{\frac{v-1}{k-1}=jk+1}$ and
$M=\smash{\frac{v(v-1)}{k(k-1)}=(jk+1)\big{(}j(k-1)+1\big{)}}$ are integers,
and the resulting ETF of $k(jk+2)\big{(}j(k-1)+1\big{)}$ vectors has a
redundancy of $\smash{k\frac{jk+2}{jk+1}}$ that tends to $k$ for large $j$;
such an ETF can be real if there exists a real Hadamard matrix of size $jk+2$.
∎

We conclude this section with a few thoughts on Theorems 7 and 8. First, we
emphasize that the method of Theorem 7 is a method for constructing some ETFs,
and by no means constructs them all. Indeed, as noted above, the redundancy of
Steiner ETFs is always strictly greater than $2$; while some of those ETFs
with $\frac{N}{M}<2$ will be the Naimark complements of Steiner ETFs, one must
admit that the Steiner method contributes little towards the understanding of
those ETFs with $\frac{N}{M}=2$, such as those arising from Paley graphs
[141]. Moreover, Theorem 8 implies that not even every ETF with
$\frac{N}{M}>2$ arises from a Steiner system: though there exists an ETF of
$76$-elements in $\mathbb{R}^{19}$ [141], the corresponding parameters of the
design would be $v=\frac{38}{3}$, $r=5$ and $k=\frac{10}{3}$, not all of which
are integers.

That said, the method of Theorem 7 is truly significant: comparing Table 1.2
with a comprehensive list of all real ETFs of dimension $50$ or less [141], we
see the Steiner method produces $4$ of the $17$ ETFs that have redundancy
greater than $2$, namely $6\times 16$, $7\times 28$, $28\times 64$ and
$35\times 120$ ETFs. Interestingly, an additional $4$ of these $17$ ETFs can
also be produced by the Steiner method, but only in complex form, namely those
of $15\times 36$, $20\times 96$, $21\times 126$ and $45\times 100$ dimensions;
it is unknown whether this is the result of a deficit in our analysis or the
true non-existence of real-valued Steiner-based constructions of these sizes.
The plot further thickens when one realizes that an additional $2$ of these
$17$ real ETFs satisfy the necessary conditions of Theorem 8, but that the
corresponding $(2,k,v)$-Steiner systems are known to not exist: if a $28\times
288$ ETF was to arise as a result of Theorem 7, the corresponding Steiner
system would have $k=6$ and $v=36$, while the $43\times 344$ ETF would have
$k=7$ and $v=43$; in fact, $(2,6,36)$\- and $(2,7,43)$-Steiner systems cannot
exist [1]. With our limited knowledge of the rich literature on Steiner
systems, we were unable to resolve the existence of two remaining candidates:
$23\times 276$ and $46\times 736$ ETFs could potentially arise from
$(2,10,46)$\- and $(2,14,92)$-Steiner systems, respectively, provided they
exist.

###  1.4 Restricted isometry and digital fingerprinting

In the previous section, we used Theorem 7 to construct many examples of
Steiner ETFs. In this section, we investigate the feasibility of using such
frames for applications in sparse signal processing. Regarding restricted
isometry, one of the sad consequences of the Steiner construction method in
Theorem 7 is that we now know there is a large class of ETFs for which the
seemingly coarse estimate from the Gershgorin analysis (1.4) is, in fact,
accurate. In particular, recall that Gershgorin guarantees that every $M\times
N$ ETF is $(K,\delta)$-RIP whenever $K\leq\delta\sqrt{M}$. Furthermore, recall
from Theorem 7 that every Steiner ETF is built by carefully overlapping $v$
regular simplices, each consisting of $r+1$ vectors in an $r$-dimensional
subspace of $b$-dimensional space. Thus, the corresponding subcollection of
$r+1$ vectors that lie in a given block are linearly dependent. Considering
the value of $r$ given in Theorem 8, we see that Steiner ETFs $\Phi$ have

$\mathrm{Spark}(\Phi)\leq
r+1=\sqrt{\frac{M(N-1)}{N-M}}+1\leq\sqrt{\frac{MN}{N-N/2}}+1=\sqrt{2M}+1,$

where the last inequality uses the fact that Steiner ETFs have redundancy
$\frac{N}{M}\geq 2$. Therefore, Steiner ETFs are not $(K,1-\varepsilon)$-RIP
for any $K>\sqrt{2M}$, that is, they fail to break the square-root bottleneck.
This begs the open question: Are there any ETFs which are as RIP as random
matrices, or does being optimal in the Gershgorin sense necessarily come at
the cost of being able to support large sparsity levels? In Chapter 3, we
address this problem directly and make some interesting connections with graph
theory and number theory, but we do not give a conclusive answer.

Despite their provably suboptimal performance as RIP matrices, we will see
that Steiner ETFs are particularly well-suited for the application of digital
fingerprints. Digital media protection has become an important issue in recent
years, as illegal distribution of licensed material has become increasingly
prevalent. A number of methods have been proposed to restrict illegal
distribution of media and ensure only licensed users are able to access it.
One method involves cryptographic techniques, which encrypt the media before
distribution. By doing this, only the users with appropriate licensed hardware
or software have access; satellite TV and DVDs are two such examples.
Unfortunately, cryptographic approaches are limited in that once the content
is decrypted (legally or illegally), it can potentially be copied and
distributed freely.

An alternate approach involves marking each copy of the media with a unique
signature. The signature could be a change in the bit sequence of the digital
file or some noise-like distortion of the media. The unique signatures are
called _fingerprints_ , by analogy to the uniqueness of human fingerprints.
With this approach, a licensed user could illegally distribute the file, only
to be implicated by his fingerprint. The potential for prosecution acts as a
deterrent to unauthorized distribution. However, fingerprinting systems are
vulnerable when multiple users form a _collusion_ by combining their copies to
create a forged copy. This attack can reduce and distort the colluders’
individual fingerprints, making identification of any particular user
difficult. Some examples of potential attacks involve comparing the bit
sequences of different copies, averaging copies in the signal space, as well
as introducing noise, rotations, or cropping.

One of the principal approaches to designing fingerprints with robustness to
collusions uses what is called the _distortion assumption_. In this regime,
fingerprints are noise-like distortions to the media in signal space. In order
to preserve the overall quality of the media, limits are placed on the
magnitude of this distortion. The content owner limits the power of the
fingerprint he adds, and the collusion limits the power of the noise they add
in their attack. When applying the distortion assumption, the literature
typically assumes that the collusion linearly averages their individual copies
to forge the host signal. Also, while results using the distortion assumption
tend to accommodate fewer users than those with other assumptions, this
assumption is distinguished by its natural embedding of fingerprints, namely
in the signal space.

Cox et al. introduced one of the first robust fingerprint designs under the
distortion assumption [54]; the robustness was later analytically proven in
[92]. Different fingerprint designs have since been studied, including
orthogonal fingerprints [142] and simplex fingerprints [94]. We propose ETFs
as a fingerprint design under the distortion assumption, and we analyze their
performance against the worst-case collusion [103, 104]. Using analysis from
Ergun et al. [66], we will show that ETFs perform particularly well as
fingerprints; as a matter of fact, Steiner ETF fingerprints perform comparably
to orthogonal and simplex fingerprints on average, while accommodating several
times as many users [104]. We start by formally presenting the fingerprinting
and collusion processes.

####  1.4.1 Problem setup

A content owner has a host signal that he wishes to share, but he wants to
mark it with fingerprints before distributing it. We view this host signal as
a vector $s\in\mathbb{R}^{M}$, and the marked versions of this vector will be
given to $N>M$ users. Specifically, the $n$th user is given

$\hat{s}_{n}:=s+\varphi_{n},$

where $\varphi_{n}\in\mathbb{R}^{M}$ denotes the $n$th fingerprint; we assume
the fingerprints have equal norm. We wish to design the fingerprints
$\\{\varphi_{n}\\}_{n=1}^{N}$ to be robust to a linear averaging attack. In
particular, let $\mathcal{K}\subseteq\\{1,\ldots,N\\}$ denote a collection of
users who together make a different copy of the host signal. Then their linear
averaging attack produces a forgery:

$f:=\sum_{k\in\mathcal{K}}x_{k}\hat{s}_{k}+z,\qquad\sum_{k\in\mathcal{K}}x_{k}=1,\qquad
x_{k}\geq 0~{}~{}~{}\forall k,$ (1.7)

where $z$ is a noise vector introduced by the colluders. This attack model is
illustrated in Figure 1.1.

$s$fingerprintassignment$\varphi_{1}$$\varphi_{2}$$\varphi_{3}$$\vdots$$\varphi_{N-2}$$\varphi_{N-1}$$\varphi_{N}$$\hat{s}_{1}$$\vdots$$\hat{s}_{N-2}$$\hat{s}_{N-1}$$\underbrace{}_{\mathcal{K}}$linear-
average-plus-noiseforgery
process$\hat{s}_{2}$$x_{2}$$\hat{s}_{3}$$x_{3}$$\vdots$$\vdots$$\hat{s}_{N}$$x_{N}$$z$$f$
Figure 1.1: The fingerprint and forgery processes. First, the content owner
makes different copies of his host signal $s$ by adding fingerprints
$\varphi_{n}$ which are unknown to the users. Next, a subcollection
$\mathcal{K}\subseteq\\{1,\ldots,N\\}$ of the users collude to create a
forgery $f$ by picking a convex combination of their copies and adding noise
$z$. In this example, the forgery coalition $\mathcal{K}$ includes users $2$,
$3$, and $N$.

Certainly, the ultimate goal of the content owner is to detect every member of
the forgery coalition. This can prove difficult in practice, though,
particularly when some individuals contribute little to the forgery, with
$x_{k}\ll\frac{1}{|\mathcal{K}|}$. However, in the real world, if at least one
colluder is caught, then other members could be identified through the legal
process. As such, we consider _focused_ detection, where a test statistic is
computed for each user, and we perform a binary hypothesis test to decide
whether that particular user is guilty.

Our detection procedure is as follows: With the cooperation of the content
owner, the host signal can be subtracted from a forgery to isolate the
fingerprint combination:

$y:=f-s=\sum_{k\in\mathcal{K}}x_{k}\varphi_{k}+z.$ (1.8)

To help the content owner discern who is guilty, we then use a normalized
correlation function as a test statistic for each user $n$:

$T_{n}(y):=\frac{\langle y,\varphi_{n}\rangle}{\|\varphi_{n}\|^{2}}.$

Having devised a test statistic, let $H_{1}(n)$ denote the guilty hypothesis
($n\in\mathcal{K}$) and $H_{0}(n)$ denote the innocent hypothesis
($n\not\in\mathcal{K}$). Then picking some correlation threshold $\tau$, we
use the following detector:

$D_{\tau}(n):=\left\\{\begin{array}[]{ll}H_{1}(n),&T_{n}(y)\geq\tau,\\\
H_{0}(n),&T_{n}(y)<\tau.\end{array}\right.$ (1.9)

To determine the effectiveness of our fingerprint design and focused detector,
we will investigate the corresponding error probabilities, but first, we build
our intuition for fingerprint design using a certain geometric figure of
merit.

####  1.4.2 A geometric figure of merit for fingerprint design

For each user $n$, consider the distance between forgeries deriving from two
types of potential collusions: those of which $n$ is a member, and those of
which $n$ is not. Intuitively, if every fingerprint combination involving $n$
is distant from every combination not involving $n$, then even with moderate
noise, there should be little ambiguity as to whether the $n$th user was
involved. To make this precise, for each user $n$, we define the “guilty” and
“not guilty” sets of noiseless fingerprint combinations:

$\displaystyle\mathcal{G}_{K,n}$
$\displaystyle:=\bigg{\\{}\frac{1}{|\mathcal{K}|}\sum_{k\in\mathcal{K}}\varphi_{k}:n\in\mathcal{K}\subseteq\\{1,\ldots,N\\},~{}|\mathcal{K}|\leq
K\bigg{\\}},$ $\displaystyle\neg\mathcal{G}_{K,n}$
$\displaystyle:=\bigg{\\{}\frac{1}{|\mathcal{K}|}\sum_{k\in\mathcal{K}}\varphi_{k}:n\not\in\mathcal{K}\subseteq\\{1,\ldots,N\\},~{}|\mathcal{K}|\leq
K\bigg{\\}}.$

In words, $\mathcal{G}_{K,n}$ is the set of size-$K$ fingerprint combinations
of equal weights which include $n$, while $\neg\mathcal{G}_{K,n}$ is the set
of combinations which do not include $n$. Note that in our setup (1.7), the
weights $x_{k}$ were arbitrary values which sum to $1$. We will show in
Theorem 11 that the best attack from the collusion’s perspective uses equal
weights so that no single colluder is particularly vulnerable. From this
perspective, it makes sense to bound the distance between these two sets:

$\mathrm{dist}(\mathcal{G}_{K,n},\neg\mathcal{G}_{K,n}):=\min\\{\|y-y^{\prime}\|_{2}:y\in\mathcal{G}_{K,n},~{}y^{\prime}\in\neg\mathcal{G}_{K,n}\\}.$
(1.10)

Note that by taking $\Phi$ to be the $M\times N$ matrix whose columns are the
fingerprints $\varphi_{n}$, the fingerprint combination (1.8) can be rewritten
as $y=\Phi x+z$, where the entries of $x$ are $x_{k}$ when $k\in\mathcal{K}$
and zero otherwise. Thus, if the matrix of fingerprints $\Phi$ is
$(K,\delta)$-RIP with $\delta<\sqrt{2}-1$, then we can recover the $K$-sparse
vector $x$ using Theorem 2. However, the error in the estimate $\tilde{x}$ of
$x$ will be on the order of $10$ times the size of the noise $z$ [34]. Due to
the potential legal ramifications of false accusations, this order of error is
not tolerable. Note that the methods of compressed sensing recover the entire
vector $x$, the support of which identifies the entire collusion. By contrast,
we will investigate RIP matrices for fingerprint design, but to minimize false
accusations, we will use focused detection (1.9) to identify colluders.

We now investigate how well RIP matrices perform with respect to our geometric
figure of merit. Without loss of generality, we assume the fingerprints are
unit norm; since they have equal norm, the fingerprint combination can be
scaled by $\frac{1}{\|\varphi_{n}\|}$ before the detection phase. With this in
mind, we have the following a lower bound on the distance (1.10) between the
“guilty” and “not guilty” sets corresponding to any user $n$:

######  Theorem 9.

Suppose fingerprints $\Phi=[\varphi_{1}\cdots\varphi_{N}]$ have restricted
isometry constant $\delta_{2K}$. Then

$\mathrm{dist}(\mathcal{G}_{K,n},\neg\mathcal{G}_{K,n})\geq\sqrt{\frac{1-\delta_{2K}}{K(K-1)}}.$
(1.11)

###### Proof.

Take $\mathcal{K},\mathcal{K}^{\prime}\subseteq\\{1,\ldots,N\\}$ such that
$|\mathcal{K}|,|\mathcal{K}^{\prime}|\leq K$ and
$n\in\mathcal{K}\setminus\mathcal{K}^{\prime}$. Then the left-hand inequality
of the restricted isometry property gives

$\displaystyle\bigg{\|}\frac{1}{|\mathcal{K}|}\sum_{n\in\mathcal{K}}\varphi_{n}-\frac{1}{|\mathcal{K}^{\prime}|}\sum_{n\in\mathcal{K}^{\prime}}\varphi_{n}\bigg{\|}^{2}$
$\displaystyle=\bigg{\|}\Big{(}\frac{1}{|\mathcal{K}|}-\frac{1}{|\mathcal{K}^{\prime}|}\Big{)}\sum_{n\in\mathcal{K}\cap\mathcal{K}^{\prime}}\varphi_{n}+\frac{1}{|\mathcal{K}|}\sum_{n\in\mathcal{K}\setminus\mathcal{K}^{\prime}}\varphi_{n}-\frac{1}{|\mathcal{K}^{\prime}|}\sum_{n\in\mathcal{K}^{\prime}\setminus\mathcal{K}}\varphi_{n}\bigg{\|}^{2}$
$\displaystyle\geq(1-\delta_{|\mathcal{K}\cup\mathcal{K}^{\prime}|})\bigg{(}|\mathcal{K}\cap\mathcal{K}^{\prime}|\Big{(}\frac{1}{|\mathcal{K}|}-\frac{1}{|\mathcal{K}^{\prime}|}\Big{)}^{2}+\frac{|\mathcal{K}\setminus\mathcal{K}^{\prime}|}{|\mathcal{K}|^{2}}+\frac{|\mathcal{K}^{\prime}\setminus\mathcal{K}|}{|\mathcal{K}^{\prime}|^{2}}\bigg{)}$
$\displaystyle=\frac{1-\delta_{|\mathcal{K}\cup\mathcal{K}^{\prime}|}}{|\mathcal{K}||\mathcal{K}^{\prime}|}\bigg{(}|\mathcal{K}|+|\mathcal{K}^{\prime}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|\bigg{)}.$
(1.12)

For a fixed $|\mathcal{K}|$, we will find a lower bound for

$\frac{1}{|\mathcal{K}|}\bigg{(}|\mathcal{K}|+|\mathcal{K}^{\prime}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|\bigg{)}=1+\frac{|\mathcal{K}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|}{|\mathcal{K}^{\prime}|}.$
(1.13)

Since we can have
$|\mathcal{K}\cap\mathcal{K}^{\prime}|>\frac{|\mathcal{K}|}{2}$, we know
$\frac{|\mathcal{K}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|}{|\mathcal{K}^{\prime}|}<0$
when (1.13) is minimized. That said, $|\mathcal{K}^{\prime}|$ must be as small
as possible, i.e.,
$|\mathcal{K}^{\prime}|=|\mathcal{K}\cap\mathcal{K}^{\prime}|$. Thus, when
(1.13) is minimized, we have

$\frac{1}{|\mathcal{K}|}\bigg{(}|\mathcal{K}|+|\mathcal{K}^{\prime}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|\bigg{)}=\frac{|\mathcal{K}|}{|\mathcal{K}\cap\mathcal{K}^{\prime}|}-1,$

i.e., $|\mathcal{K}\cap\mathcal{K}^{\prime}|$ must be as large as possible.
Since $n\in\mathcal{K}\setminus\mathcal{K}^{\prime}$, we have
$|\mathcal{K}\cap\mathcal{K}^{\prime}|\leq|\mathcal{K}|-1$. Therefore,

$\frac{1}{|\mathcal{K}|}\bigg{(}|\mathcal{K}|+|\mathcal{K}^{\prime}|-2|\mathcal{K}\cap\mathcal{K}^{\prime}|\bigg{)}\geq\frac{1}{|\mathcal{K}|-1}.$
(1.14)

Substituting (1.14) into (1.12) gives

$\bigg{\|}\frac{1}{|\mathcal{K}|}\sum_{n\in\mathcal{K}}\varphi_{n}-\frac{1}{|\mathcal{K}^{\prime}|}\sum_{n\in\mathcal{K}^{\prime}}\varphi_{n}\bigg{\|}^{2}\geq\frac{1-\delta_{|\mathcal{K}\cup\mathcal{K}^{\prime}|}}{|\mathcal{K}|(|\mathcal{K}|-1)}\geq\frac{1-\delta_{2K}}{K(K-1)}.$

Since this bound holds for every $n$, $\mathcal{K}$ and $\mathcal{K}^{\prime}$
with $n\in\mathcal{K}\setminus\mathcal{K}^{\prime}$, we have (1.11). ∎

Combining Theorem 9 with the Gershgorin estimate $\delta_{2K}\leq(2K-1)\mu$ in
terms of worst-case coherence $\mu$ yields the following:

######  Corollary 10.

Suppose fingerprints $\Phi=[\varphi_{1}\cdots\varphi_{N}]$ are unit-norm with
worst-case coherence $\mu$. Then

$\mathrm{dist}(\mathcal{G}_{K,n},\neg\mathcal{G}_{K,n})\geq\sqrt{\frac{1-(2K-1)\mu}{K(K-1)}}.$
(1.15)

In words, Corrolary 10 says that less coherent fingerprints provide a greater
distance between the “guilty” and “not guilty” sets. It is therefore fitting
to consider minimizers of worst-case coherence, namely equiangular tight
frames. One type of ETF has already been proposed for fingerprint design: the
simplex [94]. The simplex is an ETF with $N=M+1$ and $\mu=\frac{1}{M}$. In
fact, [94] gives a derivation for the exact value of the distance (1.10) in
this case:

$\mathrm{dist}(\mathcal{G}_{K,n},\neg\mathcal{G}_{K,n})=\sqrt{\frac{1}{K(K-1)}\frac{N}{N-1}}.$
(1.16)

The bound (1.15) is lower than (1.16) by a factor of
$\sqrt{1-\frac{2K}{M+1}}$, and for practical cases in which $K\ll M$, the two
are particularly close. Overall, ETF fingerprint design is a natural
generalization of the provably optimal simplex design of [94].

Having applied the Gershgorin analysis to illustrate how ETF fingerprints
perform with respect to our geometric figure of merit, we have yet to
establish any fingerprint-specific consequences of Steiner ETFs not being as
RIP as random matrices. Certainly, whether $K$ scales as $\sqrt{M}$ or $M$ is
an important distinction in the compressed sensing community, but
interestingly, in the context of fingerprints, this difference offers no
advantage. To be clear, Ergun et al. [66] showed that for any fingerprinting
system, there is a tradeoff between the probabilities of successful detection
and false positives imposed by a linear-average-plus-noise attack from
sufficiently large collusions. Specifically, a collusion of size
$K=\mathrm{\Omega}\big{(}\sqrt{\frac{M}{\log M}}\big{)}$ is sufficient to
overcome the fingerprints, as the detector will not be able to identify any
attacker without incurring a false-alarm probability that is too large to be
admissible in court. This constraint is more restrictive than the coherence-
based reconstruction guarantees which require $K=\mathrm{O}(\sqrt{M})$, and so
from this perspective, random RIP constructions are no better for fingerprint
design than deterministic constructions.

####  1.4.3 Error analysis

We now investigate the errors associated with using ETF fingerprints and a
focused correlation detector with linear-average-plus-noise attacks. To do
this, we assume that the noise $z$ included in the attack (1.7) has
independent Gaussian entries of mean zero and variance $\sigma^{2}$. One type
of error we can expect is the false-positive error, in which an innocent user
$n\notin\mathcal{K}$ is found guilty ($T_{n}(y)\geq\tau$). This could have
significant ramifications in legal proceedings, so this error probability
$\mathrm{Pr}\big{[}T_{n}(y)\geq\tau\big{|}H_{0}(n)\big{]}$ should be kept
extremely low. To ensure this type of error is improbable, we consider the
_worst-case type I error probability_ , which depends on the fingerprint
design $\Phi$, the correlation threshold $\tau$, and the weights
$\\{x_{k}\\}_{k=1}^{K}$ used by the colluders in their linear average:

$\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K}):=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\max_{\begin{subarray}{c}\mathcal{K}\rightarrow\\{x_{k}\\}\\\
\mathrm{bijective}\end{subarray}}\max_{n\not\in\mathcal{K}}\mathrm{Pr}\big{[}T_{n}(y)\geq\tau\big{|}H_{0}(n)\big{]}.$
(1.17)

In words, the probability that an innocent user $n$ is found guilty is no
larger than $\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$,
regardless of the coalition $\mathcal{K}$ or how the coalition members assign
weights from $\\{x_{k}\\}_{k=1}^{K}$. The other error type is the false-
negative error, in which a guilty user $n\in\mathcal{K}$ is found innocent
($T_{n}(y)<\tau$). In this case, since the goal of our detection is to catch
at least one of the colluders, we define the _worst-case type II error
probability_ as follows:

$\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K}):=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\max_{\begin{subarray}{c}\mathcal{K}\rightarrow\\{x_{k}\\}\\\
\mathrm{bijective}\end{subarray}}\min_{n\in\mathcal{K}}\mathrm{Pr}\big{[}T_{n}(y)<\tau\big{|}H_{1}(n)\big{]}.$
(1.18)

This way, regardless of who the colluders are or how they assign the weights,
at least one of the colluders will have a false-negative probability less than
$\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$, meaning even in
the worst-case scenario, we can correctly identify one of the colluders with
probability $\geq 1-\mathrm{P}_{\mathrm{II}}$.

######  Theorem 11.

Take fingerprints as the columns of an $M\times N$ matrix
$\Phi=[\varphi_{1}\cdots\varphi_{N}]$, which, when normalized by the
fingerprints’ common norm $\gamma$, forms an equiangular tight frame. If the
noise $z$ included in the attack (1.7) has independent Gaussian entries of
mean zero and variance $\sigma^{2}$, then the worst-case type I and type II
error probabilities, (1.17) and (1.18), satisfy

$\displaystyle\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$
$\displaystyle\leq
Q\bigg{(}\frac{\gamma}{\sigma}\big{(}\tau-\mu\big{)}\bigg{)},$
$\displaystyle\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$
$\displaystyle\leq
Q\bigg{(}\frac{\gamma}{\sigma}\Big{(}(1+\mu)\max\\{x_{k}\\}_{k=1}^{K}-\mu-\tau\Big{)}\bigg{)},$

where $Q(x):=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-u^{2}/2}du$ and
$\mu=\sqrt{\frac{N-M}{M(N-1)}}$.

###### Proof.

To bound $\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$, assume a
given user $n$ is innocent, i.e., $H_{0}(n)$. Then the test statistic for our
detector (1.9) is given by

$T_{n}(y)=\frac{1}{\gamma^{2}}\bigg{\langle}\sum_{k\in\mathcal{K}}x_{k}\varphi_{k}+z,\varphi_{n}\bigg{\rangle}=\sum_{k\in\mathcal{K}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}+\frac{1}{\gamma}\bigg{\langle}z,\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}.$

By the symmetry of $z$’s Gaussian distribution, we know the projection
$\langle z,\frac{\varphi_{n}}{\|\varphi_{n}\|}\rangle$ also has Gaussian
distribution with mean zero and variance $\sigma^{2}$, meaning our test
statistic $T_{n}(y)$ has Gaussian distribution with mean
$\sum_{k\in\mathcal{K}}x_{k}\langle\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\rangle$
and variance $\frac{\sigma^{2}}{\gamma^{2}}$. Furthermore, since the
normalized fingerprints form an ETF with worst-case coherence $\mu$, we can
use the triangle inequality to bound the mean of $T_{n}(y)$:

$\sum_{k\in\mathcal{K}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}\leq\bigg{|}\sum_{k\in\mathcal{K}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}\bigg{|}\leq\sum_{k\in\mathcal{K}}x_{k}\bigg{|}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}\bigg{|}=\mu.$

We use this to bound the false-positive probability for user $n$:

$\mathrm{Pr}\big{[}T_{n}(y)\geq\tau\big{|}H_{0}(n)\big{]}=Q\bigg{(}\frac{\gamma}{\sigma}\Big{(}\tau-\mathbb{E}\big{[}T_{n}(y)|H_{0}(n)\big{]}\Big{)}\bigg{)}\leq
Q\bigg{(}\frac{\gamma}{\sigma}\big{(}\tau-\mu\big{)}\bigg{)}.$

Since this bound holds for all coalitions, weight assignments and innocent
users, this bound must also hold for
$\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$.

Next, to bound $\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$,
assume a given user $n$ is guilty, i.e., $H_{1}(n)$. In this case, the test
statistic for our detector (1.9) is given by

$T_{n}(y)=\frac{1}{\gamma^{2}}\bigg{\langle}\sum_{k\in\mathcal{K}}x_{k}\varphi_{k}+z,\varphi_{n}\bigg{\rangle}=x_{n}+\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\
k\neq
n\end{subarray}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}+\frac{1}{\gamma}\bigg{\langle}z,\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}.$

As before, $T_{n}(y)$ has Gaussian distribution with variance
$\frac{\sigma^{2}}{\gamma^{2}}$, but this time, the mean is

$x_{n}+\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\ k\neq
n\end{subarray}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}\geq
x_{n}-\bigg{|}\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\ k\neq
n\end{subarray}}x_{k}\bigg{\langle}\frac{\varphi_{k}}{\|\varphi_{k}\|},\frac{\varphi_{n}}{\|\varphi_{n}\|}\bigg{\rangle}\bigg{|}\geq
x_{n}-\mu\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\ k\neq
n\end{subarray}}x_{k}=(1+\mu)x_{n}-\mu.$

As such, the false-negative probability for user $n$ is

$\mathrm{Pr}\big{[}T_{n}(y)<\tau\big{|}H_{1}(n)\big{]}=Q\bigg{(}-\frac{\gamma}{\sigma}\Big{(}\tau-\mathbb{E}\big{[}T_{n}(y)|H_{1}(n)\big{]}\Big{)}\bigg{)}\leq
Q\bigg{(}\frac{\gamma}{\sigma}\Big{(}(1+\mu)x_{n}-\mu-\tau\Big{)}\bigg{)}.$

Applying the definition of
$\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$ therefore gives

$\displaystyle\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$
$\displaystyle=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\max_{\begin{subarray}{c}\mathcal{K}\rightarrow\\{x_{k}\\}\\\
\mathrm{bijective}\end{subarray}}\min_{n\in\mathcal{K}}\mathrm{Pr}\big{[}T_{n}(y)<\tau\big{|}H_{1}(n)\big{]}$
$\displaystyle\leq\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\max_{\begin{subarray}{c}\mathcal{K}\rightarrow\\{x_{k}\\}\\\
\mathrm{bijective}\end{subarray}}\min_{n\in\mathcal{K}}Q\bigg{(}\frac{\gamma}{\sigma}\Big{(}(1+\mu)x_{n}-\mu-\tau\Big{)}\bigg{)}$
$\displaystyle=Q\bigg{(}\frac{\gamma}{\sigma}\Big{(}(1+\mu)\max\\{x_{k}\\}_{k=1}^{K}-\mu-\tau\Big{)}\bigg{)}.\qed$

From Theorem 11, we can glean a few interesting insights about ETF
fingerprints. First, the upper bound on
$\mathrm{P}_{\mathrm{I}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$ is independent of
$\\{x_{k}\\}_{k=1}^{K}$, indicating that the coalition cannot pick weights in
a way that frames an innocent user. Additionally, the upper bound on
$\mathrm{P}_{\mathrm{II}}(\Phi,\tau,\\{x_{k}\\}_{k=1}^{K})$ is maximized when
the weights $x_{k}$ are equal, corresponding to our use of equal weights in
the geometric figure of merit. This confirms our intuition that the coalition
has the best chance of not being caught if no member is particularly
vulnerable.

##  Chapter 2 Full spark frames

In the previous chapter, we reviewed how to use the Gershgorin circle theorem
to demonstrate the restricted isometry property (RIP), and how identifying
small spark disproves RIP. We then showed that Steiner equiangular tight
frames (ETFs) are optimal in the Gershgorin sense, but have particularly small
spark. Among other things, this illustrates that the “square-root bottleneck”
with deterministic RIP matrices is not merely an artifact of the Gershgorin
analysis. That said, as an intermediate goal to constructing RIP matrices, we
seek deterministic matrices with large spark, understanding that RIP matrices
necessarily have this property. To this end, one is naturally led to consider
_full spark_ matrices, that is, $M\times N$ matrices $\Phi$ with the largest
spark possible: $\mathrm{Spark}(\Phi)=M+1$. Equivalently, $M\times N$ full
spark matrices have the property that every $M\times M$ submatrix is
invertible; as such, a full spark matrix is necessarily full rank, and
therefore a frame.

Interestingly, in sparse signal processing, the specific application of full
spark frames has already been studied for some time. In 1997, Gorodnitsky and
Rao [74] first considered full spark frames, referring to them as matrices
with the _unique representation property_. Since [74], the unique
representation property has been explicitly used to find a variety of
performance guarantees for sparse signal processing [30, 105, 144]. Tang and
Nehorai [133] also obtain performance guarantees using full spark frames, but
they refer to them as _non-degenerate measurement matrices_.

For another application of full spark frames, we consider the problem of
reconstructing a signal from distorted frame coefficients. Specifically, we
observe a scenario in which frame coefficients
$\\{(\Phi^{*}x)[n]\\}_{n=1}^{N}$ are transmitted over a noisy or lossy channel
before reconstructing the signal:

$y=\mathcal{D}(\Phi^{*}x),\qquad\tilde{x}=(\Phi\Phi^{*})^{-1}\Phi y,$ (2.1)

where $\mathcal{D}(\cdot)$ represents the channel’s random and not-
necessarily-linear deformation process. Using an additive white Gaussian noise
model, Goyal [75] established that, of all unit norm frames, unit norm tight
frames minimize mean squared error in reconstruction. For the case of a lossy
channel, Holmes and Paulsen [84] established that, of all tight frames, unit
norm tight frames minimize worst-case error in reconstruction after one
erasure, and that equiangular tight frames minimize this error after two
erasures. We note that the reconstruction process in (2.1), namely the
application of $(\Phi\Phi^{*})^{-1}\Phi$, is inherently blind to the effect of
the deformation process of the channel. This contrasts with Püschel and
Kovačević’s more recent work [113], which describes an adaptive process for
reconstruction after multitudes of erasures. In this context, they reconstruct
the signal after first identifying which frame coefficients were not erased;
with this information, the signal can be estimated provided the corresponding
frame elements span. In this sense, full spark frames are _maximally robust to
erasures_ , as coined in [113]. In particular, an $M\times N$ full spark frame
is robust to $N-M$ erasures since any $M$ of the frame coefficients will
uniquely determine the original signal.

Yet another application of full spark frames is phaseless reconstruction,
which can be viewed in terms of a channel, as in (2.1); in this case,
$\mathcal{D}(\cdot)$ is the entrywise absolute value function. Phaseless
reconstruction has a number of real-world applications including speech
processing [15], X-ray crystallography [37], and quantum state estimation
[116]. As such, there has been a lot of work to reconstruct an $M$-dimensional
vector (up to an overall phase factor) from the magnitudes of its frame
coefficients, most of which involves frames in operator space, which
inherently require $N=\Omega(M^{2})$ measurements [14, 116]. However, Balan et
al. [15] show that if an $M\times N$ real frame $\Phi$ is full spark with
$N\geq 2M-1$, then $\mathcal{D}\circ\Phi^{*}$ is injective, meaning an
inversion process is possible with only $N=\mathrm{O}(M)$ measurements. This
result prompted an ongoing search for efficient phaseless reconstruction
processes [13, 37], but no reconstruction process can succeed without a good
family of frames, such as full spark frames.

Despite the fact that full spark frames have a multitude of applications, to
date, there has not been much progress in constructing deterministic full
spark frames, let alone full spark frames with additional desirable
properties. A noteworthy exception is Püschel and Kovačević’s work [113], in
which real full spark tight frames are constructed using polynomial
transforms. In the present chapter, we start by investigating Vandermonde
frames, harmonic frames, and modifications thereof [2]. While the use of
certain Vandermonde and harmonic frames as full spark frames is not new [30,
36, 72], the fruits of our investigation are new: For instance, we demonstrate
that certain classes of ETFs are full spark, and we characterize the $M\times
N$ full spark harmonic frames for which $N$ is a prime power. Later, we prove
that verifying whether a matrix is full spark is hard for ${\mathsf{NP}}$
under randomized polynomial-time reductions [2]. In other words, assuming
${\mathsf{NP}}\not\subseteq{\mathsf{BPP}}$ (a computational complexity
assumption slightly stronger than ${\mathsf{P}}\neq{\mathsf{NP}}$ and nearly
as widely believed), then there is no method by which one can efficiently test
whether matrices are full spark. As such, the deterministic constructions we
provide are significant in that they guarantee a property which is otherwise
difficult to check. We conclude the chapter by introducing a new technique for
efficient phaseless recovery, which explicitly makes use of deterministic full
spark frames to design $N=\mathrm{O}(M)$ measurements.

###  2.1 Deterministic constructions of full spark frames

A square matrix is invertible if and only if its determinant is nonzero, and
in our quest for deterministic constructions of full spark frames, this
characterization will reign supreme. One class of matrices has a particularly
simple determinant formula: Vandermonde matrices. Specifically, Vandermonde
matrices have the following form:

$V=\begin{bmatrix}1&1&\cdots&1\\\ \alpha_{1}&\alpha_{2}&\cdots&\alpha_{N}\\\
\vdots&\vdots&\cdots&\vdots\\\
\alpha_{1}^{M-1}&\alpha_{2}^{M-1}&\cdots&\alpha_{N}^{M-1}\end{bmatrix},$ (2.2)

and square Vandermonde matrices, i.e., with $N=M$, have the following
determinant:

$\mathrm{det}(V)=\prod_{1\leq i<j\leq M}(\alpha_{j}-\alpha_{i}).$ (2.3)

Consider (2.2) in the case where $N\geq M$. Since every $M\times M$ submatrix
of $V$ is also Vandermonde, we can modify the indices in (2.3) to calculate
the determinant of the submatrices. These determinants are nonzero precisely
when the bases $\\{\alpha_{n}\\}_{n=1}^{N}$ are distinct, yielding the
following result:

######  Lemma 12.

A Vandermonde matrix is full spark if and only if its bases are distinct.

To be clear, this result is not new. In fact, the full spark of Vandermonde
matrices was first exploited by Fuchs [72] for sparse signal processing.
Later, Bourguignon et al. [30] specifically used the full spark of Vandermonde
matrices whose bases are sampled from the complex unit circle. Interestingly,
when viewed in terms of frame theory, Vandermonde matrices naturally point to
the discrete Fourier transform:

######  Theorem 13.

The only $M\times N$ Vandermonde matrices that are equal norm and tight have
bases in the complex unit circle. Among these, the frames with the smallest
worst-case coherence have bases that are equally spaced in the complex unit
circle, provided $N\geq 2M$.

###### Proof.

Suppose a Vandermonde matrix is equal norm and tight. Note that a zero base
will produce the zeroth identity basis element $\delta_{0}$. Letting
$\mathcal{P}$ denote the indices of the nonzero bases, the fact that the
matrix is full rank implies $|\mathcal{P}|\geq M-1$. Also, equal norm gives
that the frame element length

$\|\varphi_{n}\|^{2}=\sum_{m=0}^{M-1}|\varphi_{n}[m]|^{2}=\sum_{m=0}^{M-1}|\alpha_{n}^{m}|^{2}=\sum_{m=0}^{M-1}|\alpha_{n}|^{2m}$

is constant over $n\in\mathcal{P}$. Since $\sum_{m=0}^{M-1}x^{2m}$ is strictly
increasing over $0<x<\infty$, there exists $c>0$ such that
$|\alpha_{n}|^{2}=c$ for all $n\in\mathcal{P}$. Next, tightness gives that the
rows have equal norm, implying that the first two rows have equal norm, i.e.,
$|\mathcal{P}|c=|\mathcal{P}|c^{2}$. Thus $c=1$, and so the nonzero bases are
in the complex unit circle. Furthermore, since the zeroth and first rows have
equal norm by tightness, we have $|\mathcal{P}|=N$, and so every base is in
the complex unit circle.

Now consider the inner product between Vandermonde frame elements whose bases
$\\{e^{2\pi ix_{n}}\\}_{n=1}^{N}$ come from the complex unit circle:

$\langle\varphi_{n},\varphi_{n^{\prime}}\rangle=\sum_{m=0}^{M-1}(e^{2\pi
ix_{n}})^{m}\overline{(e^{2\pi ix_{n^{\prime}}})^{m}}=\sum_{m=0}^{M-1}e^{2\pi
i(x_{n}-x_{n^{\prime}})m}.$

We will show that the worst-case coherence comes from the two closest bases.
Consider the following function:

$g(x):=\bigg{|}\sum_{m=0}^{M-1}e^{2\pi ixm}\bigg{|}^{2}.$ (2.4)

Figure 2.1 gives a plot of this function in the case where $M=5$. We will
prove two things about this function:

  * (i)

$\tfrac{d}{dx}g(x)<0$ for every $x\in(0,\tfrac{1}{2M})$,

  * (ii)

$g(x)\leq g(\tfrac{1}{2M})$ for every $x\in(\tfrac{1}{2M},1-\tfrac{1}{2M})$.

Figure 2.1: Plot of $g$ defined by (2.4) in the case where $M=5$. Observe (i)
that $g$ is strictly decreasing on the interval $(0,\frac{1}{10})$, and (ii)
that $g(x)\leq g(\frac{1}{10})$ for every $x\in(\frac{1}{10},\frac{9}{10})$.
As established in the proof of Theorem 13, $g$ behaves in this manner for
general values of $M$.

First, we claim that (i) and (ii) are sufficient to prove our result. To
establish this, we first show that the two closest bases $e^{2\pi
ix_{n^{\prime}}}$ and $e^{2\pi ix_{n^{\prime\prime}}}$ satisfy
$|x_{n^{\prime}}-x_{n^{\prime\prime}}|\leq\frac{1}{2M}$. Without loss of
generality, the $n$’s are ordered in such a way that
$\\{x_{n}\\}_{n=0}^{N-1}\subseteq[0,1)$ are nondecreasing. Define

$d(x_{n},x_{n+1}):=\left\\{\begin{array}[]{ll}x_{n+1}-x_{n},&n=0,\ldots,N-2\\\
x_{0}-(x_{N-1}-1),&n=N-1,\end{array}\right.$

and let $n^{\prime}$ be the $n$ which minimizes $d(x_{n},x_{n+1})$. Since the
minimum is less than the average, we have

$d(x_{n^{\prime}},x_{n^{\prime}+1})\leq\frac{1}{N}\bigg{(}(x_{0}-(x_{N-1}-1))+\sum_{n=0}^{N-1}(x_{n+1}-x_{n})\bigg{)}=\frac{1}{N}\leq\frac{1}{2M},$
(2.5)

provided $N\geq 2M$. Note that if we view $\\{x_{n}\\}_{n\in\mathbb{Z}_{N}}$
as members of $\mathbb{R}/\mathbb{Z}$, then $d(x_{n},x_{n+1})=x_{n+1}-x_{n}$.
Since $g(x)$ is even, then (i) implies that
$|\langle\varphi_{n^{\prime}+1},\varphi_{n^{\prime}}\rangle|^{2}=g(x_{n^{\prime}+1}-x_{n^{\prime}})$
is larger than any other
$g(x_{p}-x_{p^{\prime}})=|\langle\varphi_{p},\varphi_{p^{\prime}}\rangle|^{2}$
in which $x_{p}-x_{p^{\prime}}\in[0,\tfrac{1}{2M}]\cup[1-\tfrac{1}{2M},1)$.
Next, (2.5) and (ii) together imply that
$|\langle\varphi_{n^{\prime}+1},\varphi_{n^{\prime}}\rangle|^{2}=g(x_{n^{\prime}+1}-x_{n^{\prime}})\geq
g(\tfrac{1}{2M})$ is larger than any other
$g(x_{p}-x_{p^{\prime}})=|\langle\varphi_{p},\varphi_{p^{\prime}}\rangle|^{2}$
in which $x_{p}-x_{p^{\prime}}\in(\tfrac{1}{2M},1-\tfrac{1}{2M})$, provided
$N\geq 2M$. Combined, (i) and (ii) give that
$|\langle\varphi_{n^{\prime}+1},\varphi_{n^{\prime}}\rangle|$ achieves the
worst-case coherence of $\\{\varphi_{n}\\}_{n\in\mathbb{Z}_{N}}$.
Additionally, (i) gives that the worst-case coherence
$|\langle\varphi_{n^{\prime}+1},\varphi_{n^{\prime}}\rangle|$ is minimized
when $x_{n^{\prime}+1}-x_{n^{\prime}}$ is maximized, i.e., when the $x_{n}$’s
are equally spaced in the unit interval.

To prove (i), note that the geometric sum formula gives

$g(x)=\bigg{|}\sum_{m=0}^{M-1}e^{2\pi ixm}\bigg{|}^{2}=\bigg{|}\frac{e^{2M\pi
ix}-1}{e^{2\pi ix}-1}\bigg{|}^{2}=\frac{2-2\cos(2M\pi x)}{2-2\cos(2\pi
x)}=\bigg{(}\frac{\sin(M\pi x)}{\sin(\pi x)}\bigg{)}^{2},$ (2.6)

where the final expression uses the identity $1-\cos(2z)=2\sin^{2}z$. To show
that $g$ is decreasing over $(0,\frac{1}{2M})$, note that the base of (2.6) is
positive on this interval, and performing the quotient rule to calculate its
derivative will produce a fraction whose denominator is nonnegative and whose
numerator is given by

$M\pi\sin(\pi x)\cos(M\pi x)-\pi\sin(M\pi x)\cos(\pi x).$ (2.7)

This factor is zero at $x=0$ and has derivative:

$-(M^{2}-1)\pi^{2}\sin(\pi x)\sin(M\pi x),$

which is strictly negative for all $x\in(0,\tfrac{1}{2M})$. Hence, (2.7) is
strictly negative whenever $x\in(0,\tfrac{1}{2M})$, and so $g^{\prime}(x)<0$
for every $x\in(0,\tfrac{1}{2M})$.

For (ii), note that for every $x\in(\frac{1}{2M},1-\frac{1}{2M})$, we can
individually bound the numerator and denominator of what the geometric sum
formula gives:

$g(x)=\bigg{|}\sum_{m=0}^{M-1}e^{2\pi ixm}\bigg{|}^{2}=\frac{|e^{2M\pi
ix}-1|^{2}}{|e^{2\pi ix}-1|^{2}}\leq\frac{|e^{\pi i}-1|^{2}}{|e^{\pi
i/M}-1|^{2}}=\bigg{|}\sum_{m=0}^{M-1}e^{\pi
im/M}\bigg{|}^{2}=g(\tfrac{1}{2M}).\qed$

Consider the $N\times N$ discrete Fourier transform (DFT) matrix, scaled to
have entries of unit modulus:

$\begin{bmatrix}1&1&1&\cdots&1\\\ 1&\omega&\omega^{2}&\cdots&\omega^{N-1}\\\
1&\omega^{2}&\omega^{4}&\cdots&\omega^{2(N-1)}\\\
\vdots&\vdots&\vdots&\cdots&\vdots\\\
1&\omega^{N-1}&\omega^{2(N-1)}&\cdots&\omega^{(N-1)(N-1)}\end{bmatrix},$

where $\omega=e^{-2\pi i/N}$. The first $M$ rows of the DFT form a Vandermonde
matrix of distinct bases $\\{\omega^{n}\\}_{n=0}^{N-1}$; as such, this matrix
is full spark by Lemma 12. In fact, the previous result says that this is in
some sense an optimal Vandermonde frame, but this might not be the best way to
pick rows from a DFT. Indeed, several choices of DFT rows could produce full
spark frames, some with smaller coherence or other desirable properties, and
so the remainder of this section focuses on full spark DFT submatrices. First,
we note that not every DFT submatrix is full spark. For example, consider the
$4\times 4$ DFT:

$\begin{bmatrix}1&1&1&1\\\ 1&-i&-1&i\\\ 1&-1&1&-1\\\ 1&i&-1&-i\end{bmatrix}.$

Certainly, the zeroth and second rows of this matrix are not full spark, since
the zeroth and second columns of this submatrix form the all-ones matrix,
which is not invertible. So what can be said about the set of permissible row
choices? The following result gives some necessary conditions on this set:

######  Theorem 14.

Take an $N\times N$ discrete Fourier transform matrix, and select the rows
indexed by $\mathcal{M}\subseteq\mathbb{Z}_{N}$ to build the matrix $\Phi$. If
$\Phi$ is full spark, then so is the matrix built from rows indexed by

  * (i)

any translation of $\mathcal{M}$,

  * (ii)

any $A\mathcal{M}$ with $A$ relatively prime to $N$,

  * (iii)

the complement of $\mathcal{M}$ in $\mathbb{Z}_{N}$.

###### Proof.

For (i), we first define $D$ to be the $N\times N$ diagonal matrix whose
diagonal entries are $\\{\omega^{n}\\}_{n=0}^{N-1}$. Note that, since
$\omega^{(m+1)n}=\omega^{n}\omega^{mn}$, translating the row indices
$\mathcal{M}$ by $1$ corresponds to multiplying $\Phi$ on the right by $D$.
For some set $\mathcal{K}\subseteq\mathbb{Z}_{N}$ of size $M:=|\mathcal{M}|$,
let $\Phi_{\mathcal{K}}$ denote the $M\times M$ submatrix of $\Phi$ whose
columns are indexed by $\mathcal{K}$, and let $D_{\mathcal{K}}$ denote the
$M\times M$ diagonal submatrix of $D$ whose diagonal entries are indexed by
$\mathcal{K}$. Then since $D_{\mathcal{K}}$ is unitary, we have

$|\mathrm{det}((\Phi
D)_{\mathcal{K}})|=|\mathrm{det}(\Phi_{\mathcal{K}}D_{\mathcal{K}})|=|\mathrm{det}(\Phi_{\mathcal{K}})||\mathrm{det}(D_{\mathcal{K}})|=|\mathrm{det}(\Phi_{\mathcal{K}})|.$

Thus, if $\Phi$ is full spark, $|\mathrm{det}((\Phi
D)_{\mathcal{K}})|=|\mathrm{det}(\Phi_{\mathcal{K}})|>0$, and so $\Phi D$ is
also full spark. Using this fact inductively proves (i) for all translations
of $\mathcal{M}$.

For (ii), let $\Psi$ denote the submatrix of rows indexed by $A\mathcal{M}$.
Then for any $\mathcal{K}\subseteq\mathbb{Z}_{N}$ of size $M$,

$\mathrm{det}(\Psi_{\mathcal{K}})=\mathrm{det}(\omega^{(Am)k})_{m\in\mathcal{M},k\in\mathcal{K}}=\mathrm{det}(\omega^{m(Ak)})_{m\in\mathcal{M},k\in\mathcal{K}}=\mathrm{det}(\Phi_{A\mathcal{K}}).$

Since $A$ is relatively prime to $N$, multiplication by $A$ permutes the
elements of $\mathbb{Z}_{N}$, and so $A\mathcal{K}$ has exactly $M$ distinct
elements. Thus, if $\Phi$ is full spark, then
$\mathrm{det}(\Psi_{\mathcal{K}})=\mathrm{det}(\Phi_{A\mathcal{K}})\neq 0$,
and so $\Psi$ is also full spark.

For (iii), we let $\Psi$ be the $(N-M)\times N$ submatrix of rows indexed by
$\mathcal{M}^{\mathrm{c}}$, so that

$NI_{N}=\begin{bmatrix}\Phi^{*}&\Psi^{*}\end{bmatrix}\begin{bmatrix}\Phi\\\
\Psi\end{bmatrix}=\Phi^{*}\Phi+\Psi^{*}\Psi.$ (2.8)

We will use contraposition to show that $\Phi$ being full spark implies that
$\Psi$ is also full spark. To this end, suppose $\Psi$ is not full spark. Then
$\Psi$ has a collection of $N-M$ linearly dependent columns
$\\{\psi_{i}\\}_{i\in\mathcal{K}}$, and so there exists a nontrivial sequence
$\\{\alpha_{i}\\}_{i\in\mathcal{K}}$ such that

$\sum_{i\in\mathcal{K}}\alpha_{i}\psi_{i}=0.$

Considering $\psi_{i}=\Psi\delta_{i}$, where $\delta_{i}$ is the $i$th
identity basis element, we can use (2.8) to express this linear dependence in
terms of $\Phi$:

$0=\Psi^{*}0=\Psi^{*}\sum_{i\in\mathcal{K}}\alpha_{i}\psi_{i}=\sum_{i\in\mathcal{K}}\alpha_{i}\Psi^{*}\Psi\delta_{i}=\sum_{i\in\mathcal{K}}\alpha_{i}(NI_{N}-\Phi^{*}\Phi)\delta_{i}.$

Rearranging then gives

$x:=N\sum_{i\in\mathcal{K}}\alpha_{i}\delta_{i}=\sum_{i\in\mathcal{K}}\alpha_{i}\Phi^{*}\Phi\delta_{i}.$
(2.9)

Here, we note that $x$ is nonzero since $\\{\alpha_{i}\\}_{i\in\mathcal{K}}$
is nontrivial, and that $x\in\mathrm{Range}(\Phi^{*}\Phi)$. Furthermore,
whenever $j\not\in\mathcal{K}$, we have from (2.9) that

$\langle x,\Phi^{*}\Phi\delta_{j}\rangle=\langle\Phi^{*}\Phi
x,\delta_{j}\rangle=N\bigg{\langle}\Phi^{*}\Phi\sum_{i\in\mathcal{K}}\alpha_{i}\delta_{i},\delta_{j}\bigg{\rangle}=N^{2}\bigg{\langle}\sum_{i\in\mathcal{K}}\alpha_{i}\delta_{i},\delta_{j}\bigg{\rangle}=0,$

and so
$x\perp\mathrm{Span}\\{\Phi^{*}\Phi\delta_{j}\\}_{j\in\mathcal{K}^{\mathrm{c}}}$.
Thus, the containment
$\mathrm{Span}\\{\Phi^{*}\Phi\delta_{j}\\}_{j\in\mathcal{K}^{\mathrm{c}}}\subseteq\mathrm{Range}(\Phi^{*}\Phi)$
is proper, and so

$M=\mathrm{Rank}(\Phi)=\mathrm{Rank}(\Phi^{*}\Phi)>\mathrm{Rank}(\Phi^{*}\Phi_{\mathcal{K}^{\mathrm{c}}})=\mathrm{Rank}(\Phi_{\mathcal{K}^{\mathrm{c}}}).$

Since the $M\times M$ submatrix $\Phi_{\mathcal{K}^{\mathrm{c}}}$ is rank-
deficient, it is not invertible, and therefore $\Phi$ is not full spark. ∎

We note that our proof of (iii) above uses techniques from Cahill et al. [32],
and can be easily generalized to prove that the Naimark complement of a full
spark tight frame is also full spark. Theorem 14 tells us quite a bit about
the set of permissible choices for DFT rows. For example, not only can we pick
the first $M$ rows of the DFT to produce a full spark Vandermonde frame, but
we can also pick any consecutive $M$ rows, by Theorem 14(i). We would like to
completely characterize the choices that produce full spark harmonic frames.
The following classical result does this in the case where $N$ is prime:

######  Theorem 15 (Chebotarëv, see [126]).

Let $N$ be prime. Then every square submatrix of the $N\times N$ discrete
Fourier transform matrix is invertible.

As an immediate consequence of Chebotarëv’s theorem, every choice of rows from
the DFT produces a full spark harmonic frame, provided $N$ is prime. This
application of Chebotarëv’s theorem was first used by Candès et al. [36] for
sparse signal processing. Note that each of these frames are equal-norm and
tight by construction. Harmonic frames can also be designed to have minimal
coherence; Xia et al. [146] produces harmonic equiangular tight frames by
selecting row indices which form a difference set in $\mathbb{Z}_{N}$.
Interestingly, most known families of difference sets in $\mathbb{Z}_{N}$
require $N$ to be prime [87], and so the corresponding harmonic equiangular
tight frames are guaranteed to be full spark by Chebotarëv’s theorem. In the
following, we use Chebotarëv’s theorem to demonstrate full spark for a class
of frames which contains harmonic frames, namely, frames which arise from
concatenating harmonic frames with any number of identity basis elements:

######  Theorem 16 (cf. [131, Theorem 1.1]).

Let $N$ be prime, and pick any $M\leq N$ rows of the $N\times N$ discrete
Fourier transform matrix to form the harmonic frame $H$. Next, pick any $K\leq
M$, and take $D$ to be the $M\times M$ diagonal matrix whose first $K$
diagonal entries are $\sqrt{\frac{N+K-M}{MN}}$, and whose remaining $M-K$
entries are $\sqrt{\frac{N+K}{MN}}$. Then concatenating $DH$ with the first
$K$ identity basis elements produces an $M\times(N+K)$ full spark unit norm
tight frame.

As an example, when $N=5$ and $K=1$, we can pick $M=3$ rows of the $5\times 5$
DFT which are indexed by $\\{0,1,4\\}$. In this case, $D$ makes the entries of
the first DFT row have size $\sqrt{\frac{1}{5}}$ and the entries of the
remaining rows have size $\sqrt{\frac{2}{5}}$. Concatenating with the first
identity basis element then produces an equiangular tight frame which is full
spark:

$\Phi=\left[\begin{array}[]{llllll}\sqrt{\frac{1}{5}}&\sqrt{\frac{1}{5}}&\sqrt{\frac{1}{5}}&\sqrt{\frac{1}{5}}&\sqrt{\frac{1}{5}}&1\\\
\sqrt{\frac{2}{5}}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}2/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}3/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}4/5}&0\\\
\sqrt{\frac{2}{5}}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}4/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}3/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}2/5}&\sqrt{\frac{2}{5}}e^{-2\pi\mathrm{i}/5}&0\\\
\end{array}\right].$ (2.10)

###### Proof of Theorem 16.

Let $\Phi$ denote the resulting $M\times(N+K)$ frame. We start by verifying
that $\Phi$ is unit norm. Certainly, the identity basis elements have unit
norm. For the remaining frame elements, the modulus of each entry is
determined by $D$, and so the norm squared of each frame element is

$K(\tfrac{N+K-M}{MN})+(M-K)(\tfrac{N+K}{MN})=1.$

To demonstrate that $\Phi$ is tight, it suffices to show that
$\Phi\Phi^{*}=\frac{N+K}{M}I_{M}$. The rows of $DH$ are orthogonal since they
are scaled rows of the DFT, while the rows of the identity portion are
orthogonal because they have disjoint support. Thus, $\Phi\Phi^{*}$ is
diagonal. Moreover, the norm squared of each of the first $K$ rows is
$N(\frac{N+K-M}{MN})+1=\frac{N+K}{M}$, while the norm squared of each of the
remaining rows is $N(\frac{N+K}{MN})=\frac{N+K}{M}$, and so
$\Phi\Phi^{*}=\frac{N+K}{M}I_{M}$.

To show that $\Phi$ is full spark, note that every $M\times M$ submatrix of
$DH$ is invertible since

$|\mathrm{det}((DH)_{\mathcal{K}})|=|\mathrm{det}(DH_{\mathcal{K}})|=|\mathrm{det}(D)||\mathrm{det}(H_{\mathcal{K}})|>0,$

by Chebotarëv’s theorem. Also, in the case where $K=M$, we note that the
$M\times M$ submatrix of $\Phi$ composed solely of identity basis elements is
trivially invertible. The only remaining case to check is when identity basis
elements and columns of $DH$ appear in the same $M\times M$ submatrix
$\Phi_{\mathcal{K}}$. In this case, we may shuffle the rows of
$\Phi_{\mathcal{K}}$ to have the form

$\begin{bmatrix}A&0\\\ B&I_{K}\end{bmatrix}.$

Since shuffling rows has no impact on the size of the determinant, we may
further use a determinant identity on block matrices to get

$|\mathrm{det}(\Phi_{\mathcal{K}})|=\left|\mathrm{det}\begin{bmatrix}A&0\\\
B&I_{K}\end{bmatrix}\right|=|\mathrm{det}(A)\mathrm{det}(I_{K})|=|\mathrm{det}(A)|.$

Since $A$ is a multiple of a square submatrix of the $N\times N$ DFT, we are
done by Chebotarëv’s theorem. ∎

As an example of Theorem 16, pick $N$ to be a prime congruent to $1\bmod 4$,
and select $\frac{N+1}{2}$ rows of the $N\times N$ DFT according to the index
set $\mathcal{M}:=\\{k^{2}:k\in\mathbb{Z}_{N}\\}$. If we take $K=1$, the
process in Theorem 16 produces an equiangular tight frame of redundancy $2$,
which we will verify in the next chapter using quadratic Gauss sums; in the
case where $N=5$, this construction produces (2.10). Note that this
corresponds to a special case of a construction in Zauner’s thesis [150],
which was later studied by Renes [115] and Strohmer [128]. Theorem 16 says
that this construction is full spark.

Maximally sparse frames have recently become a subject of active research [44,
70]. We note that when $K=M$, Theorem 16 produces a maximally sparse
$M\times(N+K)$ full spark frame, having a total of $M(M-1)$ zero entries. To
see that this sparsity level is maximal, we note that if the frame had any
more zero entries, then at least one of the rows would have $M$ zero entries,
meaning the corresponding $M\times M$ submatrix would have a row of all zeros
and hence a zero determinant. Similar ideas were studied previously by
Nakamura and Masson [107].

Another interesting case is where $K=M=N$, i.e., when the frame constructed in
Theorem 16 is a union of the unitary DFT and identity bases. Unions of
orthonormal bases have received considerable attention in the context of
sparse approximation [61, 136]. In fact, when $N$ is a perfect square,
concatenating the DFT with an identity basis forms the canonical example
$\Phi$ of a dictionary with small spark [61], and we used this example in the
previous chapter. Recall the Dirac comb of $\sqrt{N}$ spikes is an eigenvector
of the DFT, and so concatenating this comb with the negative of its Fourier
transform produces a $2\sqrt{N}$-sparse vector in the nullspace of $\Phi$. In
stark contrast, when $N$ is prime, Theorem 16 shows that $\Phi$ is full spark.

The vast implications of Chebotarëv’s theorem leads one to wonder whether the
result admits any interesting generalization. In this direction, Candès et al.
[36] note that any such generalization must somehow account for the nontrivial
subgroups of $\mathbb{Z}_{N}$ which are not present when $N$ is prime.
Certainly, if one could characterize the full spark submatrices of a general
DFT, this would provide ample freedom to optimize full spark frames for
additional considerations. While we do not have a characterization for the
general case, we do have one for the case where $N$ is a prime power. Before
stating the result, we require a definition:

######  Definition 17.

We say a subset $\mathcal{M}\subseteq\mathbb{Z}_{N}$ is _uniformly distributed
over the divisors of $N$_ if, for every divisor $d$ of $N$, the $d$ cosets of
$\langle d\rangle$ partition $\mathcal{M}$ into subsets, each of size
$\lfloor\frac{|\mathcal{M}|}{d}\rfloor$ or
$\lceil\frac{|\mathcal{M}|}{d}\rceil$.

At first glance, this definition may seem rather unnatural, but we will
discover some important properties of uniformly distributed rows from the DFT.
As an example, we briefly consider uniform distribution in the context of the
restricted isometry property (RIP). Recall that a matrix of random rows from a
DFT and normalized columns is RIP with high probability [118]. We will show
that harmonic frames satisfy RIP only if the selected row indices are nearly
uniformly distributed over sufficiently small divisors of $N$.

To this end, recall that for any divisor $d$ of $N$, the Fourier transform of
the $d$-sparse normalized Dirac comb
$\frac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}$ is the
$\frac{N}{d}$-sparse normalized Dirac comb $\sqrt{\frac{d}{N}}\chi_{\langle
d\rangle}$. Let $F$ be the $N\times N$ unitary DFT, and let $\Phi$ be the
harmonic frame which arises from selecting rows of $F$ indexed by
$\mathcal{M}$ and then normalizing the columns. In order for $\Phi$ to be
$(K,\delta)$-RIP, $\mathcal{M}$ must contain at least one member of $\langle
d\rangle$ for every divisor $d$ of $N$ which is $\leq K$, since otherwise

$\Phi\tfrac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}=\sqrt{\tfrac{N}{|\mathcal{M}|}}(F\tfrac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle})_{\mathcal{M}}=\sqrt{\tfrac{N}{|\mathcal{M}|}}\Big{(}\sqrt{\tfrac{d}{N}}\chi_{\langle
d\rangle}\Big{)}_{\mathcal{M}}=\sqrt{\tfrac{d}{|\mathcal{M}|}}\chi_{\mathcal{M}\cap\langle
d\rangle}=0,$

which violates the lower RIP bound at
$x=\frac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}$. In fact, the RIP
bounds indicate that

$\|\Phi
x\|^{2}=\|\Phi\tfrac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}\|^{2}=\Big{\|}\sqrt{\tfrac{d}{|\mathcal{M}|}}\chi_{\mathcal{M}\cap\langle
d\rangle}\Big{\|}^{2}=\tfrac{d}{|\mathcal{M}|}|\mathcal{M}\cap\langle
d\rangle|$

cannot be more than $\delta$ away from $\|x\|^{2}=1$. Similarly, taking $x$ to
be $\frac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}$ modulated by $a$,
i.e., $x[n]:=\frac{1}{\sqrt{d}}\chi_{\langle\frac{N}{d}\rangle}[n]e^{2\pi
ian/N}$ for every $n\in\mathbb{Z}_{N}$, gives that $\|\Phi
x\|^{2}=\frac{d}{|\mathcal{M}|}|\mathcal{M}\cap(a+\langle d\rangle)|$ is also
no more than $\delta$ away from $1$. This observation gives the following
result:

######  Theorem 18.

Select rows indexed by $\mathcal{M}\subseteq\mathbb{Z}_{N}$ from the $N\times
N$ discrete Fourier transform matrix and then normalize the columns to produce
the harmonic frame $\Phi$. Then $\Phi$ satisfies the $(K,\delta)$-restricted
isometry property only if

$\Big{|}\big{|}\mathcal{M}\cap(a+\langle
d\rangle)\big{|}-\tfrac{|\mathcal{M}|}{d}\Big{|}\leq\tfrac{|\mathcal{M}|}{d}\delta$

for every divisor $d$ of $N$ with $d\leq K$ and every $a=0,\ldots,d-1$.

Now that we have an intuition for uniform distribution in terms of modulated
Dirac combs and RIP, we take this condition to the extreme by considering
uniform distribution over all divisors. Doing so produces a complete
characterization of full spark harmonic frames when $N$ is a prime power:

######  Theorem 19.

Let $N$ be a prime power, and select rows indexed by
$\mathcal{M}\subseteq\mathbb{Z}_{N}$ from the $N\times N$ discrete Fourier
transform matrix to build the submatrix $\Phi$. Then $\Phi$ is full spark if
and only if $\mathcal{M}$ is uniformly distributed over the divisors of $N$.

Note that, perhaps surprisingly, an index set $\mathcal{M}$ can be uniformly
distributed over $p$ but not over $p^{2}$, and vice versa. For example,
$\mathcal{M}=\\{0,1,4\\}$ is uniformly distributed over $2$ but not $4$, while
$\mathcal{M}=\\{0,2\\}$ is uniformly distributed over $4$ but not $2$.

Since the first $M$ rows of a DFT form a full spark Vandermonde matrix, let’s
check that this index set is uniformly distributed over the divisors of $N$.
For each divisor $d$ of $N$, we partition the first $M$ indices into the $d$
cosets of $\langle d\rangle$. Write $M=qd+r$ with $0\leq r<d$. The first $qd$
of the $M$ indices are distributed equally amongst all $d$ cosets, and then
the remaining $r$ indices are distributed equally amongst the first $r$
cosets. Overall, the first $r$ cosets contain
$q+1=\lfloor\frac{M}{d}\rfloor+1$ indices, while the remaining $d-r$ cosets
have $q=\lfloor\frac{M}{d}\rfloor$ indices; thus, the first $M$ indices are
indeed uniformly distributed over the divisors of $N$. Also, when $N$ is
prime, _every_ subset of $\mathbb{Z}_{N}$ is uniformly distributed over the
divisors of $N$ in a trivial sense. In fact, Chebotarëv’s theorem follows
immediately from Theorem 19. In some ways, portions of our proof of Theorem 19
mirror recurring ideas in the existing proofs of Chebotarëv’s theorem [59, 67,
126, 131]. For the sake of completeness, we provide the full argument and save
the reader from having to parse portions of proofs from multiple references.
We start with the following lemmas, whose proofs are based on the proofs of
Lemmas 1.2 and 1.3 in [131].

######  Lemma 20.

Let $N$ be a power of some prime $p$, and let $P(z_{1},\ldots,z_{M})$ be a
polynomial with integer coefficients. Suppose there exists $N$th roots of
unity $\\{\omega_{m}\\}_{m=1}^{M}$ such that
$P(\omega_{1},\ldots,\omega_{M})=0$. Then $P(1,\ldots,1)$ is a multiple of
$p$.

###### Proof.

Denoting $\omega:=e^{-2\pi i/N}$, then for every $m=1,\ldots,M$, we have
$\omega_{m}=\omega^{k_{m}}$ for some $0\leq k_{m}<N$. Defining the polynomial
$Q(z):=P(z^{k_{1}},\ldots,z^{k_{M}})$, we have $Q(\omega)=0$ by assumption.
Also, $Q(z)$ is a polynomial with integer coefficients, and so it must be
divisible by the minimal polynomial of $\omega$, namely, the cyclotomic
polynomial $\Phi_{N}(z)$. Evaluating both polynomials at $z=1$ then gives that
$p=\Phi_{N}(1)$ divides $Q(1)=P(1,\ldots,1)$. ∎

######  Lemma 21.

Let $N$ be a power of some prime $p$, and pick
$\mathcal{M}=\\{m_{i}\\}_{i=1}^{M}\subseteq\mathbb{Z}_{N}$ such that

$\frac{\displaystyle{\prod_{1\leq i<j\leq
M}(m_{j}-m_{i})}}{\displaystyle{\prod_{m=0}^{M-1}m!}}$ (2.11)

is not a multiple of $p$. Then the rows indexed by $\mathcal{M}$ in the
$N\times N$ discrete Fourier transform form a full spark frame.

###### Proof.

We wish to show that $\mathrm{det}(\omega_{n}^{m})_{m\in\mathcal{M},1\leq
n\leq M}\neq 0$ for all $M$-tuples of distinct $N$th roots of unity
$\\{\omega_{n}\\}_{n=1}^{M}$. Define the polynomial
$D(z_{1},\ldots,z_{M}):=\mathrm{det}(z_{n}^{m})_{m\in\mathcal{M},1\leq n\leq
M}$. Since columns $i$ and $j$ of $(z_{n}^{m})_{m\in\mathcal{M},1\leq n\leq
M}$ are identical whenever $z_{i}=z_{j}$, we know that $D$ vanishes in each of
these instances, and so we can factor:

$D(z_{1},\ldots,z_{M})=P(z_{1},\ldots,z_{M})\prod_{1\leq i<j\leq
M}(z_{j}-z_{i})$

for some polynomial $P(z_{1},\ldots,z_{M})$ with integer coefficients. By
Lemma 20, it suffices to show that $P(1,\ldots,1)$ is not a multiple of $p$,
since this implies $D(\omega_{1},\ldots,\omega_{M})$ is nonzero for all
$M$-tuples of distinct $N$th roots of unity $\\{\omega_{n}\\}_{n=1}^{M}$.

To this end, we proceed by considering

$A:=\bigg{(}z_{1}\frac{\partial}{\partial
z_{1}}\bigg{)}^{0}\bigg{(}z_{2}\frac{\partial}{\partial
z_{2}}\bigg{)}^{1}\cdots\bigg{(}z_{M}\frac{\partial}{\partial
z_{M}}\bigg{)}^{M-1}D(z_{1},\ldots,z_{M})\bigg{|}_{z_{1}=\cdots=z_{M}=1}.$
(2.12)

To compute $A$, we note that each application of
$z_{j}\frac{\partial}{\partial z_{j}}$ produces terms according to the product
rule. For some terms, a linear factor of the form $z_{j}-z_{i}$ or
$z_{i}-z_{j}$ is replaced by $z_{j}$ or $-z_{j}$, respectively. For each the
other terms, these linear factors are untouched, while another factor, such as
$P(z_{1},\ldots,z_{M})$, is differentiated and multiplied by $z_{j}$. Note