# Two are better than one: Fundamental parameters of frame coherence

Waheed U. Bajwa  Robert Calderbank  Dustin G. Mixon  Department of Electrical
and Computer Engineering, Rutgers, The State University of New Jersey,
Piscataway, New Jersey 08854, USA  Department of Electrical and Computer
Engineering, Duke University, Durham, North Carolina 27708, USA  Program in
Applied and Computational Mathematics, Princeton University, Princeton, New
Jersey 08544, USA

###### Abstract

This paper investigates two parameters that measure the coherence of a frame:
worst-case and average coherence. We first use worst-case and average
coherence to derive near-optimal probabilistic guarantees on both sparse
signal detection and reconstruction in the presence of noise. Next, we provide
a catalog of nearly tight frames with small worst-case and average coherence.
Later, we find a new lower bound on worst-case coherence; we compare it to the
Welch bound and use it to interpret recently reported signal reconstruction
results. Finally, we give an algorithm that transforms frames in a way that
decreases average coherence without changing the spectral norm or worst-case
coherence.

###### keywords:

frames , worst-case coherence , average coherence , Welch bound , sparse
signal processing

††journal: Applied and Computational Harmonic Analysis

##  1 Introduction

Many classical applications, such as radar and error-correcting codes, make
use of over-complete spanning systems [46]. Oftentimes, we may view an over-
complete spanning system as a _frame_. Take $F=\\{f_{i}\\}_{i\in\mathcal{I}}$
to be a collection of vectors in some separable Hilbert space $\mathcal{H}$.
Then $F$ is a frame if there exist _frame bounds_ $A$ and $B$ with $0<A\leq
B<\infty$ such that $A\|x\|^{2}\leq\sum_{i\in\mathcal{I}}|\langle
x,f_{i}\rangle|^{2}\leq B\|x\|^{2}$ for every $x\in\mathcal{H}$. When $A=B$,
$F$ is called a _tight frame_. For finite-dimensional unit norm frames, where
$\mathcal{I}=\\{1,\ldots,N\\}$, the _worst-case coherence_ is a useful
parameter:

$\mu_{F}:=\max_{\begin{subarray}{c}i,j\in\\{1,\ldots,N\\}\\\ i\neq
j\end{subarray}}|\langle f_{i},f_{j}\rangle|.$ (1)

Note that orthonormal bases are tight frames with $A=B=1$ and have zero worst-
case coherence. In both ways, frames form a natural generalization of
orthonormal bases.

In this paper, we only consider finite-dimensional frames. Those not familiar
with frame theory can simply view a finite-dimensional frame as an $M\times N$
matrix of rank $M$ whose columns are the frame elements. With this view, the
tightness condition is equivalent to having the spectral norm be as small as
possible; for an $M\times N$ unit norm frame $F$, this equivalently means
$\|F\|_{2}^{2}=\frac{N}{M}$.

Throughout the literature, applications require finite-dimensional frames that
are nearly tight and have small worst-case coherence [11, 21, 31, 37, 46, 47,
50, 56]. Among these, a foremost application is sparse signal processing,
where frames of small spectral norm and/or small worst-case coherence are
commonly used to analyze sparse signals [11, 21, 47, 50, 56]. In general,
sparse signal processing deals with measurements of the form

$y=Fx+e,$

where $F$ is $M\times N$ with $M\ll N$, $x$ has at most $K$ nonzero entries,
and $e$ is some sort of noise. When given measurements $y$ of $x$, one might
be asked to reconstruct the original sparse vector $x$, or to find the
locations of its nonzero entries, or to simply determine whether $x$ is
nonzero—each of these is a sparse signal processing problem. In some
applications, the signal $x$ is sparse in the identity basis, in which case
$F$ represents the measurement process. In other applications, $x$ is sparse
in an orthonormal basis or an overcomplete dictionary $G$ [10]. In this case,
$F$ is a composition of $A$, the frame resulting from the measurement process,
and $G$, the sparsifying dictionary, i.e., $F=AG$. We do not make a
distinction between the two formulations in this paper, but our results are
most readily interpretable in a physical setting for the former case.

Recently, [5] introduced another notion of frame coherence called _average
coherence_ :

$\nu_{F}:=\tfrac{1}{N-1}\max_{i\in\\{1,\ldots,N\\}}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{N}\langle f_{i},f_{j}\rangle\bigg{|}.$ (2)

Note that, in addition to having zero worst-case coherence, orthonormal bases
also have zero average coherence. Intuitively, worst-case coherence is a
measure of dissimilarity between frame elements, whereas average coherence
measures how well the frame elements are distributed in the unit hypersphere.
In sparse signal processing, there are a number of performance guarantees that
depend only on worst-case coherence [20, 23, 25, 47]. These guarantees at best
allow for sparsity levels on the order of $\sqrt{M}$. Compressed sensing has
brought guarantees that depend on the Restricted Isometry Property, which is
much more difficult to check, but the guarantees allow for sparsity levels on
the order of $\smash{\frac{M}{\log N}}$ [6, 13, 14]. Recently, [5] used worst-
case and average coherence to produce _probabilistic_ guarantees that also
allow for sparsity levels on the order of $\smash{\frac{M}{\log N}}$; these
guarantees require that worst-case and average coherence together satisfy the
following property:

######  Definition 1.

We say an $M\times N$ unit norm frame $F$ satisfies the _Strong Coherence
Property_ if

$\mbox{(SCP-1)}~{}~{}~{}\mu_{F}\leq\tfrac{1}{164\log
N}\qquad\mbox{and}\qquad\mbox{(SCP-2)}~{}~{}~{}\nu_{F}\leq\tfrac{\mu_{F}}{\sqrt{M}},$

where $\mu_{F}$ and $\nu_{F}$ are given by (1) and (2), respectively.

The reader should know that the constant $164$ is not particularly essential
to the above definition; it is used in [5] to simplify some analysis and make
certain performance guarantees explicit, but the constant is by no means
optimal. This in mind, the requirement (SCP-1) can be interpreted more
generally as $\mu_{F}=O(\tfrac{1}{\log N})$. In the next section, we will use
the Strong Coherence Property to continue the work of [5]. Where [5] provided
guarantees for noiseless reconstruction, we will produce near-optimal
guarantees for signal detection and reconstruction from _noisy_ measurements
of sparse signals. These guarantees are related to those in [11, 21, 49, 50],
and we will also elaborate on this relationship.

The results given in [5] and Section 2, as well as the applications discussed
in [11, 21, 31, 37, 46, 47, 50, 56] demonstrate a pressing need for nearly
tight frames with small worst-case and average coherence, especially in the
area of sparse signal processing. This paper offers three additional
contributions in this regard. In Section 3, we provide a sizable catalog of
frames that exhibit small spectral norm, worst-case coherence, and average
coherence. With all three frame parameters provably small, these frames are
guaranteed to perform well in relevant applications. Next, performance in many
applications is dictated by worst-case coherence [11, 21, 31, 37, 46, 47, 50,
56]. It is therefore particularly important to understand which worst-case
coherence values are achievable. To this end, the Welch bound [46] is commonly
used in the literature. However, the Welch bound is only tight when the number
of frame elements $N$ is less than the square of the spatial dimension $M$
[46]. Another lower bound, given in [38, 54], beats the Welch bound when there
are more frame elements, but it is known to be loose for real frames [18].
Given this context, Section 4 gives a new lower bound on the worst-case
coherence of real frames. Our bound beats both the Welch bound and the bound
in [38, 54] when the number of frame elements far exceeds the spatial
dimension. Finally, since average coherence is so new, there is currently no
intuition as to when (SCP-2) is satisfied. In Section 5, we use ideas akin to
the switching equivalence of graphs to transform a frame that satisfies
(SCP-1) into another frame with the same spectral norm and worst-case
coherence that additionally satisfies (SCP-2).

Throughout the paper, we make use of certain notations that we address here.
Recall, with big-O notation, that $f(n)=O(g(n))$ if there exists positive $C$
and $n_{0}$ such that for all $n>n_{0}$, $f(n)\leq Cg(n)$. Also,
$f(n)=\Omega(g(n))$ if $g(n)=O(f(n))$, and $f(n)=\Theta(g(n))$ if
$f(n)=O(g(n))$ and $g(n)=O(f(n))$. Additionally, we use $F_{\mathcal{K}}$ to
denote the matrix whose columns are taken from the matrix $F$ according to the
index set $\mathcal{K}$. Similarly, we use $x_{\mathcal{K}}$ to denote the
column vector whose entries are taken from the column vector $x$ according to
the index set $\mathcal{K}$. The column vector of the $T$ largest entries in
column vector $x$ is denoted by $x_{T}$. We also use $\|x\|$ to denote the
$\ell^{2}$ norm of a vector $x$, while $\|F\|_{2}$ is the spectral norm of a
matrix $F$. Lastly, we use a star ($*$) to denote the matrix adjoint, a dagger
($\dagger$) to denote the matrix pseudoinverse, and $\mathrm{I}_{K}$ to denote
the $K\times K$ identity matrix.

##  2 Worst-case and average coherence: Applications to sparse signal
processing

Frames with small spectral norm, worst-case coherence, and/or average
coherence have found use in recent years with applications involving sparse
signals. Donoho et al. used the worst-case coherence in [21] to provide
uniform bounds on the signal and support recovery performance of combinatorial
and convex optimization methods and greedy algorithms. Later, Tropp [50] and
Candès and Plan [11] used both the spectral norm and worst-case coherence to
provide tighter bounds on the signal and support recovery performance of
convex optimization methods for most support sets under the additional
assumption that the sparse signals have independent nonzero entries with zero
median. Recently, Bajwa et al. [5] made use of the spectral norm and both
coherence parameters to report tighter bounds on the noisy model selection and
noiseless signal recovery performance of an incredibly fast greedy algorithm
called _one-step thresholding (OST)_ for most support sets and _arbitrary_
nonzero entries. In this section, we discuss further implications of the
spectral norm and worst-case and average coherence of frames in applications
involving sparse signals.

###  2.1 The Weak Restricted Isometry Property

A common task in signal processing applications is to test whether a
collection of measurements corresponds to mere noise [33]. For applications
involving sparse signals, one can test measurements $y\in\mathbb{C}^{M}$
against the null hypothsis $H_{0}:y=e$ and alternative hypothesis
$H_{1}:y=Fx+e$, where the entries of the noise vector $e\in\mathbb{C}^{M}$ are
independent, identical zero-mean complex-Gaussian random variables and the
signal $x\in\mathbb{C}^{N}$ is $K$-sparse. The performance of such signal
detection problems is directly proportional to the energy in $Fx$ [19, 27,
33]. In particular, existing literature on the detection of sparse signals
[19, 27] leverages the fact that $\|Fx\|^{2}\approx\|x\|^{2}$ when $F$
satisfies the Restricted Isometry Property (RIP) of order $K$. In contrast, we
now show that the Strong Coherence Property also guarantees
$\|Fx\|^{2}\approx\|x\|^{2}$ for most $K$-sparse vectors. We start with a
definition:

######  Definition 2.

We say an $M\times N$ frame $F$ satisfies the _$(K,\delta,p)$ -Weak Restricted
Isometry Property (Weak RIP)_ if for every $K$-sparse vector
$y\in\mathbb{C}^{N}$, a random permutation $x$ of $y$’s entries satisfies

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

with probability exceeding $1-p$.

At first glance, it may seem odd that we introduce a random permutation when
we might as well define Weak RIP in terms of a $K$-sparse vector whose support
is drawn randomly from all $\smash{\binom{N}{K}}$ possible choices. In fact,
both versions would be equivalent in distribution, but we stress that in the
present definition, the values of the nonzero entries of $x$ are _not_ random;
rather, the only randomness we have is in the locations of the nonzero
entries. We wish to distinguish our results from those in [11], which
explicitly require randomness in the values of the nonzero entries. We also
note the distinction between RIP and Weak RIP—Weak RIP requires that $F$
preserves the energy of _most_ sparse vectors. Moreover, the manner in which
we quantify “most” is important. For each sparse vector, $F$ preserves the
energy of most permutations of that vector, but for different sparse vectors,
$F$ might not preserve the energy of permutations with the same support. That
is, unlike RIP, Weak RIP is _not_ a statement about the singular values of
submatrices of $F$. Certainly, matrices for which most submatrices are well-
conditioned, such as those discussed in [49, 50], will satisfy Weak RIP, but
Weak RIP does not require this. That said, the following theorem shows, in
part, the significance of the Strong Coherence Property.

######  Theorem 3.

Any $M\times N$ unit norm frame $F$ that satisfies the Strong Coherence
Property also satisfies the $(K,\delta,\frac{4K}{N^{2}})$-Weak Restricted
Isometry Property provided $N\geq 128$ and
$\smash{2K\log{N}\leq\min\\{\frac{\delta^{2}}{100\mu_{F}^{2}},M\\}}$.

###### Proof.

Let $x$ be as in Definition 2. Note that (3) is equivalent to
$\smash{\big{|}\|Fx\|^{2}-\|x\|^{2}\big{|}\leq\delta\|x\|^{2}}$. Defining
$\mathcal{K}:=\\{n:|x_{n}|>0\\}$, then the Cauchy-Schwarz inequality gives

$\big{|}\|Fx\|^{2}-\|x\|^{2}\big{|}=|x_{\mathcal{K}}^{*}(F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K})x_{\mathcal{K}}|\leq\|x_{\mathcal{K}}\|~{}\|(F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K})x_{\mathcal{K}}\|\leq\sqrt{K}~{}\|x_{\mathcal{K}}\|~{}\|(F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K})x_{\mathcal{K}}\|_{\infty},$
(4)

where the last inequality uses the fact that
$\|\cdot\|\leq\sqrt{K}~{}\|\cdot\|_{\infty}$ in $\mathbb{C}^{K}$. We now
consider [5, Lemma 3], which states that for any $\epsilon\in[0,1)$ and $a\geq
1$,
$\|(F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K})x_{\mathcal{K}}\|_{\infty}\leq\epsilon\|x_{\mathcal{K}}\|$
with probability exceeding
$\smash{1-4K\mathrm{e}^{-(\epsilon-\sqrt{K}\nu_{F})^{2}/16(2+a^{-1})^{2}\mu_{F}^{2}}}$
provided $\smash{K\leq\min\\{\epsilon^{2}\nu_{F}^{-2},(1+a)^{-1}N\\}}$. We
claim that (4) together with [5, Lemma 3] guarantee
$\smash{\big{|}\|Fx\|^{2}-\|x\|^{2}\big{|}\leq\delta\|x\|^{2}}$ with
probability exceeding $\smash{1-\frac{4K}{N^{2}}}$. In order to establish this
claim, we fix $\epsilon=10\mu\sqrt{2\log{N}}$ and $a=2\log{128}-1$. It is then
easy to see that (SCP-1) gives $\epsilon<1$, and also that (SCP-2) and
$2K\log{N}\leq M$ give $K\leq\epsilon^{2}\nu_{F}^{-2}/9$. Therefore, since the
assumption that $N\geq 128$ together with $2K\log{N}\leq M$ implies
$K\leq(1+a)^{-1}N$, we obtain
$\smash{\mathrm{e}^{-(\epsilon-\sqrt{K}\nu_{F})^{2}/16(2+a^{-1})^{2}\mu_{F}^{2}}\leq\frac{1}{N^{2}}}$.
The result now follows from the observation that
$\smash{2K\log{N}\leq\frac{\delta^{2}}{100\mu_{F}^{2}}}$ implies
$\sqrt{K}\epsilon\leq\delta$. ∎

This theorem shows that having small worst-case and average coherence is
enough to guarantee Weak RIP. This contrasts with related results by Tropp
[49, 50] that require $F$ to be nearly tight. In fact, the proof of Theorem 3
does not even use the full power of the Strong Coherence Property; instead of
(SCP-1), it suffices to have $\smash{\mu_{F}\leq 1/(15\\!\sqrt{\log N})}$,
part of what [5] calls the Coherence Property. Also, if $F$ has worst-case
coherence $\smash{\mu_{F}=O(1/\\!\sqrt{M})}$ and average coherence
$\nu_{F}=O(1/M)$, then even if $F$ has large spectral norm, Theorem 3 states
that $F$ preserves the energy of most $K$-sparse vectors with $K=O(M/\log N)$,
i.e., the sparsity regime which is linear in the number of measurements.

###  2.2 Reconstruction of sparse signals from noisy measurements

Another common task in signal processing applications is to reconstruct a
$K$-sparse signal $x\in\mathbb{C}^{N}$ from a small collection of linear
measurements $y\in\mathbb{C}^{M}$. Recently, Tropp [50] used both the worst-
case coherence and spectral norm of frames to find bounds on the
reconstruction performance of _basis pursuit (BP)_ [17] for most support sets
under the assumption that the nonzero entries of $x$ are independent with zero
median. In contrast, [5] used the spectral norm and worst-case and average
coherence of frames to find bounds on the reconstruction performance of OST
for most support sets and _arbitrary_ nonzero entries. However, both [5] and
[50] limit themselves to recovering $x$ in the absence of noise, corresponding
to $y=Fx$, a rather ideal scenario.

Our goal in this section is to provide guarantees for the reconstruction of
sparse signals from noisy measurements $y=Fx+e$, where the entries of the
noise vector $e\in\mathbb{C}^{M}$ are independent, identical complex-Gaussian
random variables with mean zero and variance $\sigma^{2}$. In particular, and
in contrast with [21], our guarantees will hold for arbitrary unit norm frames
$F$ without requiring the signal’s sparsity level to satisfy
$K=O(\mu_{F}^{-1})$. The reconstruction algorithm that we analyze here is the
OST algorithm of [5], which is described in Algorithm 1. The following theorem
extends the analysis of [5] and shows that the OST algorithm leads to near-
optimal reconstruction error for certain important classes of sparse signals.

Before proceeding further, we first define some notation. We use
$\textsf{{snr}}:=\|x\|^{2}/\mathbb{E}[\|e\|^{2}]$ to denote the _signal-to-
noise ratio_ associated with the signal reconstruction problem. Also, we use
$\smash{\mathcal{T}_{\sigma}(t):=\\{n:|x_{n}|>\frac{2\sqrt{2}}{1-t}\sqrt{2\sigma^{2}\log{N}}\\}}$
for any $t\in(0,1)$ to denote the locations of all the entries of $x$ that,
roughly speaking, lie above the _noise floor_ $\sigma$. Finally, we use
$\smash{\mathcal{T}_{\mu}(t):=\\{n:|x_{n}|>\frac{20}{t}\mu_{F}\|x\|\sqrt{2\log{N}}\\}}$
to denote the locations of entries of $x$ that, roughly speaking, lie above
the _self-interference floor_ $\mu_{F}\|x\|$.

Algorithm 1 One-Step Thresholding (OST) for sparse signal reconstruction [5]

Input: An $M\times N$ unit norm frame $F$, a vector $y=Fx+e$, and a threshold
$\lambda>0$
Output: An estimate $\hat{x}\in\mathbb{C}^{N}$ of the true sparse signal $x$

$\hat{x}\leftarrow 0$ {Initialize}

$z\leftarrow F^{*}y$ {Form signal proxy}

$\hat{\mathcal{K}}\leftarrow\\{n:|z_{n}|>\lambda\\}$ {Select indices via OST}

$\hat{x}_{\hat{\mathcal{K}}}\leftarrow(F_{\hat{\mathcal{K}}})^{\dagger}y$
{Reconstruct signal via least-squares}

######  Theorem 4 (Reconstruction of sparse signals).

Take an $M\times N$ unit norm frame $F$ which satisfies the Strong Coherence
Property, pick $t\in(0,1)$, and choose
$\smash{\lambda=\sqrt{2\sigma^{2}\log{N}}~{}\max\\{\frac{10}{t}\mu_{F}\sqrt{M~{}\textsf{{snr}}},\frac{\sqrt{2}}{1-t}\\}}$.
Further, suppose $x\in\mathbb{C}^{N}$ has support $\mathcal{K}$ drawn
uniformly at random from all possible $K$-subsets of $\\{1,\ldots,N\\}$. Then
provided

$K\leq\tfrac{N}{c_{1}^{2}\|F\|_{2}^{2}\log{N}},$ (5)

Algorithm 1 produces $\hat{\mathcal{K}}$ such that
$\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t)\subseteq\hat{\mathcal{K}}\subseteq\mathcal{K}$
and $\hat{x}$ such that

$\|x-\hat{x}\|\leq
c_{2}\sqrt{\sigma^{2}|\hat{\mathcal{K}}|\log{N}}+c_{3}\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|$
(6)

with probability exceeding $1-10N^{-1}$. Finally, defining
$T:=|\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t)|$, we further have

$\|x-\hat{x}\|\leq c_{2}\sqrt{\sigma^{2}K\log{N}}+c_{3}\|x-x_{T}\|$ (7)

in the same probability event. Here, $c_{1}=37\mathrm{e}$,
$c_{2}=\frac{2}{1-\mathrm{e}^{-1/2}}$, and
$c_{3}=1+\frac{\mathrm{e}^{-1/2}}{1-\mathrm{e}^{-1/2}}$ are numerical
constants.

###### Proof.

To begin, note that since $\smash{\|F\|_{2}^{2}\geq\frac{N}{M}}$, we have from
(5) that $K\leq M/(2\log{N})$. It is then easy to conclude from [5, Theorem 5]
that $\smash{\hat{\mathcal{K}}}$ satisfies
$\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t)\subseteq\hat{\mathcal{K}}\subseteq\mathcal{K}$
with probability exceeding $1-6N^{-1}$. Therefore, conditioned on the event
$\smash{\mathcal{E}_{1}:=\\{\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t)\subseteq\hat{\mathcal{K}}\subseteq\mathcal{K}\\}}$,
we can make use of the triangle inequality to write

$\|x-\hat{x}\|\leq\|x_{\hat{\mathcal{K}}}-\hat{x}_{\hat{\mathcal{K}}}\|+\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|.$
(8)

Next, we may use (5) and the fact that $F$ satisfies the Strong Coherence
Property to conclude from [49] (see, e.g., [5, Proposition 3]) that
$\|F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K}\|_{2}<\mathrm{e}^{-1/2}$
with probability exceeding $1-2N^{-1}$. Hence, conditioning on
$\mathcal{E}_{1}$ and
$\smash{\mathcal{E}_{2}:=\\{\|F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K}\|_{2}<\mathrm{e}^{-1/2}\\}}$,
we have that
$\smash{(F_{\hat{\mathcal{K}}})^{\dagger}=(F_{\hat{\mathcal{K}}}^{*}F_{\hat{\mathcal{K}}})^{-1}F_{\hat{\mathcal{K}}}^{*}}$
since $F_{\hat{\mathcal{K}}}$ is a submatrix of a full column rank matrix
$F_{\mathcal{K}}$. Therefore, given $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$,
we may write

$\hat{x}_{\hat{\mathcal{K}}}=(F_{\hat{\mathcal{K}}})^{\dagger}(Fx+e)=x_{\hat{\mathcal{K}}}+(F_{\hat{\mathcal{K}}})^{\dagger}F_{\mathcal{K}\setminus\hat{\mathcal{K}}}x_{\mathcal{K}\setminus\hat{\mathcal{K}}}+(F_{\hat{\mathcal{K}}})^{\dagger}e,$
(9)

and so substituting (9) into (8) and applying the triangle inequality gives

$\displaystyle\|x-\hat{x}\|$
$\displaystyle\leq\|(F_{\hat{\mathcal{K}}})^{\dagger}F_{\mathcal{K}\setminus\hat{\mathcal{K}}}x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|+\|(F_{\hat{\mathcal{K}}})^{\dagger}e\|+\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|$
$\displaystyle\leq\Big{(}1+\|(F_{\hat{\mathcal{K}}}^{*}F_{\hat{\mathcal{K}}})^{-1}\|_{2}\|F_{\hat{\mathcal{K}}}^{*}F_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|_{2}\Big{)}\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|+\|(F_{\hat{\mathcal{K}}}^{*}F_{\hat{\mathcal{K}}})^{-1}\|_{2}\|F_{\hat{\mathcal{K}}}^{*}e\|.$
(10)

Since, given $\mathcal{E}_{1}$, we have that
$\smash{F_{\hat{\mathcal{K}}}^{*}F_{\hat{\mathcal{K}}}-\mathrm{I}_{K}}$ and
$\smash{F_{\hat{\mathcal{K}}}^{*}F_{\mathcal{K}\setminus\hat{\mathcal{K}}}}$
are submatrices of
$\smash{F_{\mathcal{K}}^{*}F_{\mathcal{K}}-\mathrm{I}_{K}}$, and since the
spectral norm of a matrix provides an upper bound for the spectral norms of
its submatrices, we have the following given $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$:
$\smash{\|F_{\hat{\mathcal{K}}}^{*}F_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|_{2}\leq\mathrm{e}^{-1/2}}$
and
$\smash{\|(F_{\hat{\mathcal{K}}}^{*}F_{\hat{\mathcal{K}}})^{-1}\|_{2}\leq\tfrac{1}{1-\mathrm{e}^{-1/2}}}$.
We can now substitute these bounds into (10) and make use of the fact that
$\smash{\|F_{\hat{\mathcal{K}}}^{*}e\|\leq|\hat{\mathcal{K}}|^{1/2}\|F_{\hat{\mathcal{K}}}^{*}e\|_{\infty}}$
to conclude that

$\|x-\hat{x}\|\leq\tfrac{|\hat{\mathcal{K}}|^{1/2}}{1-\mathrm{e}^{-1/2}}\|F_{\hat{\mathcal{K}}}^{*}e\|_{\infty}+\Big{(}1+\tfrac{\mathrm{e}^{-1/2}}{1-\mathrm{e}^{-1/2}}\Big{)}\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|,$

given $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. At this point, define the event
$\smash{\mathcal{E}_{3}=\\{\|F_{\hat{\mathcal{K}}}^{*}e\|_{\infty}\leq
2\sqrt{\sigma^{2}\log{N}}\\}}$ and note from [5, Lemma 6] that
$\smash{\Pr(\mathcal{E}_{3}^{\mathrm{c}})\leq
2(\sqrt{2\pi\log{N}}~{}N)^{-1}}$. A union bound therefore gives (6) with
probability exceeding $1-10N^{-1}$. For (7), note that
$\hat{\mathcal{K}}\subseteq\mathcal{K}$ implies $|\hat{\mathcal{K}}|\leq K$,
and so
$\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t)\subseteq\hat{\mathcal{K}}$
implies that
$\|x_{\mathcal{K}\setminus\hat{\mathcal{K}}}\|\leq\|x_{\mathcal{K}\setminus(\mathcal{T}_{\sigma}(t)\cap\mathcal{T}_{\mu}(t))}\|=\|x-x_{T}\|$.
∎

A few remarks are in order now for Theorem 4. First, if $F$ satisfies the
Strong Coherence Property _and_ $F$ is nearly tight, then OST handles sparsity
that is almost linear in $M$: $K=O(M/\log{N})$ from (5). Second, we do not
impose any control over the size of $T$, but rather we state the result in
generality in terms of $T$; its size is determined by the signal class $x$
belongs to, the worst-case coherence of the frame $F$ we use to measure $x$,
and the magnitude of the noise that perturbs $Fx$. Third, the $\ell_{2}$ error
associated with the OST algorithm is the near-optimal (modulo the $\log$
factor) error of $\smash{\sqrt{\sigma^{2}K\log{N}}}$ _plus_ the best $T$-term
approximation error caused by the inability of the OST algorithm to recover
signal entries that are smaller than $\smash{O(\mu_{F}\|x\|\sqrt{2\log{N}})}$.
In particular, if the $K$-sparse signal $x$, the worst-case coherence
$\mu_{F}$, and the noise $e$ together satisfy
$\|x-x_{T}\|=O(\smash{\sqrt{\sigma^{2}K\log{N}}})$, then the OST algorithm
succeeds with a near-optimal $\ell_{2}$ error of
$\smash{\|x-\hat{x}\|=O(\sqrt{\sigma^{2}K\log{N}})}$. To see why this error is
near-optimal, note that a $K$-dimension vector of random entries with mean
zero and variance $\sigma^{2}$ has expected squared norm $\sigma^{2}K$; in our
case, we pay an additional log factor to find the locations of the $K$ nonzero
entries among the entire $N$-dimensional signal. It is important to recognize
that the optimality condition
$\|x-x_{T}\|=O(\smash{\sqrt{\sigma^{2}K\log{N}}})$ depends on the signal
class, the noise variance, and the worst-case coherence of the frame; in
particular, the condition is satisfied whenever
$\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|=O(\smash{\sqrt{\sigma^{2}K\log{N}}})$,
since

$\|x-x_{T}\|\leq\|x_{\mathcal{K}\setminus\mathcal{T}_{\sigma}(t)}\|+\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|=O\Big{(}\sqrt{\sigma^{2}K\log{N}}\Big{)}+\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|.$

The following lemma provides classes of sparse signals that satisfy
$\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|=O(\smash{\sqrt{\sigma^{2}K\log{N}}})$
given sufficiently small noise variance and worst-case coherence, and
consequently the OST algorithm is near-optimal for the reconstruction of such
signal classes.

######  Lemma 5.

Take an $M\times N$ unit norm frame $F$ with worst-case coherence
$\smash{\mu_{F}\leq\frac{c_{0}}{\sqrt{M}}}$ for some $c_{0}>0$, and suppose
that $\smash{K\leq\frac{N}{c_{1}^{2}\|F\|_{2}^{2}\log N}}$ for some $c_{1}>0$.
Fix a constant $\beta\in(0,1]$, and suppose the magnitudes of $\beta K$
nonzero entries of $x$ are some $\alpha=\Omega(\sqrt{\sigma^{2}\log{N}})$,
while the magnitudes of the remaining $(1-\beta)K$ nonzero entries are not
necessarily same, but are smaller than $\alpha$ and scale as
$\smash{O(\sqrt{\sigma^{2}\log{N}})}$. Then
$\smash{\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|=O(\sqrt{\sigma^{2}K\log{N}})}$,
provided $\smash{c_{0}\leq\frac{tc_{1}}{20\sqrt{2}}}$.

###### Proof.

Let $\mathcal{K}$ be the support of $x$, and define
$\mathcal{I}:=\\{n:|x_{n}|=\alpha\\}$. We wish to show that
$\mathcal{I}\subseteq\mathcal{T}_{\mu}(t)$, since this implies
$\smash{\|x_{\mathcal{K}\setminus\mathcal{T}_{\mu}(t)}\|\leq\|x_{\mathcal{K}\setminus\mathcal{I}}\|=O(\sqrt{\sigma^{2}K\log{N}})}$.
In order to prove $\mathcal{I}\subseteq\mathcal{T}_{\mu}(t)$, notice that

$\|x\|^{2}=\|x_{\mathcal{I}}\|^{2}+\|x_{\mathcal{K}\setminus\mathcal{I}}\|^{2}<\beta
K\alpha^{2}+(1-\beta)K\alpha^{2}=K\alpha^{2},$

and so combining this with the fact that $\|F\|_{2}^{2}\geq\frac{N}{M}$ gives

$\mu_{F}\|x\|\sqrt{\log{N}}<\tfrac{c_{0}}{\sqrt{M}}\sqrt{K}\alpha\sqrt{\log{N}}\leq\tfrac{c_{0}}{\sqrt{M}}\sqrt{\tfrac{N}{c_{1}^{2}\|F\|_{2}^{2}\log
N}}~{}\alpha\sqrt{\log{N}}\leq\tfrac{c_{0}}{c_{1}}\alpha.$

Therefore, provided $\smash{c_{0}\leq\frac{tc_{1}}{20\sqrt{2}}}$, we have that
$\mathcal{I}\subseteq\mathcal{T}_{\mu}(t)$. ∎

In words, Lemma 5 implies that OST is near-optimal for those $K$-sparse
signals whose entries above the noise floor have roughly the same magnitude.
This subsumes a very important class of signals that appears in applications
such as multi-label prediction [32], in which all the nonzero entries take
values $\pm\alpha$. To the best of our knowledge, Theorem 4 is the first
result in the sparse signal processing literature that does not require RIP
and still provides near-optimal reconstruction guarantees for such signals
from noisy measurements, while using either random or deterministic frames,
even when $K=O(M/\log{N})$.

We note that our techniques can be extended to reconstruct noisy signals, that
is, we may consider measurements of the form $y=F(x+n)+e$, where
$n\in\mathbb{C}^{N}$ is also a noise vector of independent, identical zero-
mean complex-Gaussian random variables. In particular, if the frame $F$ is
tight, then our measurements will not color the noise, and so noise in the
signal may be viewed as noise in the measurements: $y=Fx+(Fn+e)$; if the frame
is not tight, then the noise will become correlated in the measurements, and
performance would be depend nontrivially on the frame’s Gram matrix. Also, the
authors have had some success with generalizing Theorem 4 to approximately
sparse signals; the analysis follows similiar lines, but is rather cumbersome,
and it appears as though the end result is only strong enough in the case of
very nearly sparse signals. As such, we omit this result.

##  3 Frame constructions

In this section, we consider a range of nearly tight frames with small worst-
case and average coherence. We investigate various ways of selecting frames at
random from different libraries, and we show that for each of these frames,
the spectral norm, worst-case coherence, and average coherence are all small
with high probability. Later, we will consider deterministic constructions
that use Gabor and chirp systems, spherical designs, equiangular tight frames,
and error-correcting codes. For the reader’s convenience, all of these
constructions are summarized in Table 1. Before we go any further, recall the
following lower bound on worst-case coherence:

######  Theorem 6 (Welch bound [46]).

Every $M\times N$ unit norm frame $F$ has worst-case coherence
$\mu_{F}\geq\sqrt{\tfrac{N-M}{M(N-1)}}$.

We will use the Welch bound in the proof of the following lemma, which gives
three different sufficient conditions for a frame to satisfy (SCP-2). These
conditions will prove quite useful in this section and throughout the paper.

######  Lemma 7.

For any $M\times N$ unit norm frame $F$, each of the following conditions
implies $\nu_{F}\leq\frac{\mu_{F}}{\sqrt{M}}$:

  1. (i)

$\langle f_{k},\sum_{n=1}^{N}f_{n}\rangle=\frac{N}{M}$ for every
$k=1,\ldots,N$,

  2. (ii)

$N\geq 2M$ and $\sum_{n=1}^{N}f_{n}=0$,

  3. (iii)

$N\geq M^{2}+3M+3$ and $\|\sum_{n=1}^{N}f_{n}\|^{2}\leq N$.

###### Proof.

For condition (i), we have

$\nu_{F}=\tfrac{1}{N-1}\max_{i}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\langle
f_{i},f_{j}\rangle\bigg{|}=\tfrac{1}{N-1}\max_{i}\bigg{|}\bigg{\langle}f_{i},\sum_{j=1}^{N}f_{j}\bigg{\rangle}-1\bigg{|}=\tfrac{1}{N-1}\big{(}\tfrac{N}{M}-1\big{)}.$

The Welch bound therefore gives
$\nu_{F}=\tfrac{1}{N-1}\big{(}\tfrac{N}{M}-1\big{)}=\tfrac{N-M}{M(N-1)}\leq\mu_{F}\sqrt{\tfrac{N-M}{M(N-1)}}\leq\tfrac{\mu_{F}}{\sqrt{M}}$.
For condition (ii), we have

$\nu_{F}=\tfrac{1}{N-1}\max_{i}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\langle
f_{i},f_{j}\rangle\bigg{|}=\tfrac{1}{N-1}\max_{i}\bigg{|}\bigg{\langle}f_{i},\sum_{j=1}^{N}f_{j}\bigg{\rangle}-1\bigg{|}=\tfrac{1}{N-1}.$

Considering the Welch bound, it suffices to show
$\frac{1}{N-1}\leq\frac{1}{\sqrt{M}}\sqrt{\frac{N-M}{M(N-1)}}$. Rearranging
equivalently gives

$N^{2}-(M+1)N-M(M-1)\geq 0.$ (11)

When $N=2M$, the left-hand side of (11) becomes $(M-1)^{2}$, which is
trivially nonnegative. Otherwise, we have

$N\geq 2M+1\geq
M+1+\sqrt{M(M-1)}\geq\tfrac{M+1}{2}+\sqrt{\big{(}\tfrac{M+1}{2}\big{)}^{2}+M(M-1)}.$

In this case, by the quadratic formula and the fact that the left-hand side of
(11) is concave up in $N$, we have that (11) is indeed satisfied. For
condition (iii), we use the triangle and Cauchy-Schwarz inequalities to get

$\nu_{F}=\tfrac{1}{N-1}\max_{i}\bigg{|}\bigg{\langle}f_{i},\sum_{j=1}^{N}f_{j}\bigg{\rangle}-1\bigg{|}\leq\tfrac{1}{N-1}\bigg{(}\max_{i}\bigg{|}\bigg{\langle}f_{i},\sum_{j=1}^{N}f_{j}\bigg{\rangle}\bigg{|}+1\bigg{)}\leq\tfrac{\sqrt{N}+1}{N-1}.$

Considering the Welch bound, it suffices to show
$\smash{\frac{\sqrt{N}+1}{N-1}\leq\frac{1}{\sqrt{M}}\sqrt{\frac{N-M}{M(N-1)}}}$.
Taking $x:=\sqrt{N}$ and rearranging gives a polynomial:
$x^{4}-(M^{2}+M+1)x^{2}-2M^{2}x-M(M-1)\geq 0$. By convexity and monotonicity
of the polynomial in $[M+\frac{3}{2},\infty)$, it can be shown that the
largest real root of this polynomial is always smaller than
$\smash{M+\frac{3}{2}}$. Also, considering it is concave up in $x$, it
suffices that $\smash{\sqrt{N}=x\geq M+\frac{3}{2}}$, which we have since
$N\geq M^{2}+3M+3\geq(M+\frac{3}{2})^{2}$. ∎

###  3.1 Normalized Gaussian frames

Construct a matrix with independent, Gaussian-distributed entries that have
zero mean and unit variance. By normalizing the columns, we get a matrix
called a _normalized Gaussian frame_. This is perhaps the most widely studied
type of frame in the signal processing and statistics literature. To be clear,
the term “normalized” is intended to distinguish the results presented here
from results reported in earlier works, such as [5, 6, 13, 52], which only
ensure that Gaussian frame elements have unit norm in expectation. In other
words, normalized Gaussian frame elements are independently and uniformly
distributed on the unit hypersphere in $\mathbb{R}^{M}$. That said, the
following theorem characterizes the spectral norm and the worst-case and
average coherence of normalized Gaussian frames.

######  Theorem 8 (Geometry of normalized Gaussian frames).

Build a real $M\times N$ frame $G$ by drawing entries independently at random
from a Gaussian distribution of zero mean and unit variance. Next, construct a
normalized Gaussian frame $F$ by taking
$\smash{f_{n}:=\frac{g_{n}}{\|g_{n}\|}}$ for every $n=1,\ldots,N$. Provided
$\smash{60\log{N}\leq M\leq\frac{N-1}{4\log{N}}}$, then the following
inequalities simultaneously hold with probability exceeding $1-11N^{-1}$:

  1. (i)

$\mu_{F}\leq\frac{\sqrt{15\log{N}}}{\sqrt{M}-\sqrt{12\log{N}}}$,

  2. (ii)

$\nu_{F}\leq\frac{\sqrt{15\log{N}}}{M-\sqrt{12M\log{N}}}$,

  3. (iii)

$\|F\|_{2}\leq\frac{\sqrt{M}+\sqrt{N}+\sqrt{2\log{N}}}{\sqrt{M-\sqrt{8M\log{N}}}}$.

###### Proof.

Theorem 8(i) can be shown to hold with probability exceeding $1-2N^{-1}$ by
using a bound on the norm of a Gaussian random vector in [34, Lemma 1] and a
bound on the magnitude of the inner product of two independent Gaussian random
vectors in [26, Lemma 6]. Specifically, pick any two distinct indices
$i,j\in\\{1,\dots,N\\}$, and define probability events
$\mathcal{E}_{1}:=\\{|\langle g_{i},g_{j}\rangle|\leq\delta_{1}\\}$,
$\mathcal{E}_{2}:=\\{\|g_{i}\|^{2}\geq M(1-\delta_{2})\\}$, and
$\mathcal{E}_{3}:=\\{\|g_{j}\|^{2}\geq M(1-\delta_{2})\\}$ for
$\smash{\delta_{1}=\sqrt{15M\log{N}}}$ and
$\smash{\delta_{2}=\sqrt{(12\log{N})/M}}$. Then it follows from the union
bound that

$\Pr\bigg{(}|\langle
f_{i},f_{j}\rangle|>\tfrac{\delta_{1}}{M(1-\delta_{2})}\bigg{)}=\Pr\bigg{(}\tfrac{|\langle
g_{i},g_{j}\rangle|}{\|g_{i}\|~{}\|g_{j}\|}>\tfrac{\delta_{1}}{M(1-\delta_{2})}\bigg{)}\leq\Pr(\mathcal{E}_{1}^{\mathrm{c}})+\Pr(\mathcal{E}_{2}^{\mathrm{c}})+\Pr(\mathcal{E}_{3}^{\mathrm{c}}).$

One can verify that
$\Pr(\mathcal{E}_{2}^{\mathrm{c}})=\Pr(\mathcal{E}_{3}^{\mathrm{c}})\leq
N^{-3}$ because of [34, Lemma 1], and we further have
$\Pr(\mathcal{E}_{1}^{\mathrm{c}})\leq 2N^{-3}$ because of [26, Lemma 6] and
the fact that $M\geq 60\log{N}$. Thus, for any fixed $i$ and $j$,
$\smash{|\langle
f_{i},f_{j}\rangle|\leq\\!\sqrt{15\log{N}}/(\\!\sqrt{M}-\\!\sqrt{12\log{N}})}$
with probability exceeding $1-4N^{-3}$. It therefore follows by taking a union
bound over all $\smash{\binom{N}{2}}$ choices for $i$ and $j$ that Theorem
8(i) holds with probability exceeding $1-2N^{-1}$.

Theorem 8(ii) can be shown to hold with probability exceeding $1-6N^{-1}$ by
appealing to the preceding analysis and Hoeffding’s inequality for a sum of
independent, bounded random variables [30]. Specifically, fix any index
$i\in\\{1,\dots,N\\}$, and define random variables
$Z^{i}_{j}:=\frac{1}{N-1}\langle f_{i},f_{j}\rangle$. Next, define the
probability event

$\mathcal{E}_{4}:=\bigcap_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\bigg{\\{}|Z^{i}_{j}|\leq\tfrac{1}{N-1}~{}\tfrac{\sqrt{15\log{N}}}{\sqrt{M}-\sqrt{12\log{N}}}\bigg{\\}}.$

Using the analysis for the worst-case coherence of $F$ and taking a union
bound over the $N-1$ possible $j$’s gives
$\Pr(\mathcal{E}_{4}^{\mathrm{c}})\leq 4N^{-2}$. Furthermore, taking
$\delta_{3}:=\sqrt{15\log{N}}/(M-\sqrt{12M\log{N}})$, then elementary
probability analysis gives

$\Pr\bigg{(}\Big{|}\sum_{j\not=i}Z^{i}_{j}\Big{|}>\delta_{3}\bigg{)}\leq\Pr\Bigg{(}\Big{|}\sum_{j\not=i}Z^{i}_{j}\Big{|}>\delta_{3}~{}\Bigg{|}~{}\mathcal{E}_{4}\Bigg{)}+\Pr(\mathcal{E}_{4}^{\mathrm{c}})\leq\int_{S^{M-1}}\\!\\!\\!\Pr\Bigg{(}\Big{|}\sum_{j\not=i}Z^{i}_{j}\Big{|}>\delta_{3}~{}\Bigg{|}~{}\mathcal{E}_{4},f_{i}=x\Bigg{)}~{}p_{f_{i}}(x)~{}\mathrm{dH}^{M-1}(x)+4N^{-2},$
(12)

where $S^{M-1}$ denotes the unit hypersphere in $\mathbb{R}^{M}$,
$\mathrm{H}^{M-1}$ denotes the $(M-1)$-dimensional Hausdorff measure on
$S^{M-1}$, and $p_{f_{i}}(x)$ denotes the probability density function for the
random vector $f_{i}$. The first thing to note here is that the random
variables $\\{Z^{i}_{j}:j\not=i\\}$ are bounded and jointly independent when
conditioned on $\mathcal{E}_{4}$ and $f_{i}$. This assertion mainly follows
from Bayes’ rule and the fact that $\\{f_{j}:j\not=i\\}$ are jointly
independent when conditioned on $f_{i}$. The second thing to note is that
$\smash{\mathbb{E}[Z^{i}_{j}~{}|~{}\mathcal{E}_{4},f_{i}]=0}$ for every $j\neq
i$. This comes from the fact that the random vectors
$\smash{\\{f_{n}\\}_{n=1}^{N}}$ are independent and have a uniform
distribution over $\smash{S^{M-1}}$, which in turn guarantees that the random
variables $\\{Z^{i}_{j}:j\not=i\\}$ have a symmetric distribution around zero
when conditioned on $\mathcal{E}_{4}$ and $f_{i}$. We can therefore make use
of Hoeffding’s inequality [30] to bound the probability expression inside the
integral in (12) as

$\Pr\Bigg{(}\Big{|}\sum_{j\not=i}Z^{i}_{j}\Big{|}>\delta_{3}~{}\Bigg{|}~{}\mathcal{E}_{4},f_{i}=x\Bigg{)}\leq
2\mathrm{e}^{-(N-1)/2M},$ (13)

which is bounded above by $2N^{-2}$ provided
$\smash{M\leq\frac{N-1}{4\log{N}}}$. We can now substitute (13) into (12) and
take the union bound over the $N$ possible choices for $i$ to conclude that
Theorem 8(ii) holds with probability exceeding $1-6N^{-1}$.

Lastly, Theorem 8(iii) can be shown to hold with probability exceeding
$1-3N^{-1}$ by using a bound on the spectral norm of standard Gaussian random
matrices reported in [41] along with [34, Lemma 1]. Specifically, define an
$N\times N$ diagonal matrix
$D:=\mathrm{diag}(\|g_{1}\|^{-1},\dots,\|g_{N}\|^{-1})$, and note that the
entries of $G:=FD^{-1}$ are independently and normally distributed with zero
mean and unit variance. We therefore have from (2.3) in [41] that

$\Pr\Big{(}\|G\|_{2}>\sqrt{M}+\sqrt{N}+\sqrt{2\log{N}}\Big{)}\leq 2N^{-1}.$
(14)

In addition, we can appeal to the preceding analysis for the probability bound
on Theorem 8(i) and conclude using [34, Lemma 1] and a union bound over the
$N$ possible choices for $i$ that

$\Pr\Big{(}\|D\|_{2}>\Big{(}M-\sqrt{8M\log{N}}\Big{)}^{-1/2}\Big{)}\leq
N^{-1}.$ (15)

Finally, since $\|F\|_{2}\leq\|G\|_{2}\|D\|_{2}$, we can take a union bound
over (14) and (15) to argue that Theorem 8(iii) holds with probability
exceeding $1-3N^{-1}$.

The complete result now follows by taking a union bound over the failure
probabilities for the conditions (i)-(iii) in Theorem 8. ∎

######  Example 9.

To illustrate the bounds in Theorem 8, we ran simulations in MATLAB. Picking
$N=50000$, we observed $30$ realizations of normalized Gaussian frames for
each $M=700,900,1100$. The distributions of $\mu_{F}$, $\nu_{F}$, and
$\|F\|_{2}$ were rather tight, so we only report the ranges of values
attained, along with the bounds given in Theorem 8:

$\begin{array}[]{rrcll}M=700:&\qquad\mu_{F}&\in&[0.1849,0.2072]&\qquad\leq
0.8458\\\ &\qquad\nu_{F}&\in&[0.5643,0.6613]\times 10^{-3}&\qquad\leq
0.0320\\\ &\qquad\|F\|_{2}&\in&[8.0521,8.0835]&\qquad\leq 11.9565\\\ \\\
M=900:&\qquad\mu_{F}&\in&[0.1946,0.2206]&\qquad\leq 0.6848\\\
&\qquad\nu_{F}&\in&[0.5800,0.7501]\times 10^{-3}&\qquad\leq 0.0229\\\
&\qquad\|F\|_{2}&\in&[8.4352,8.4617]&\qquad\leq 10.3645\\\ \\\
M=1100:&\qquad\mu_{F}&\in&[0.1807,0.1988]&\qquad\leq 0.5852\\\
&\qquad\nu_{F}&\in&[0.5260,0.6713]\times 10^{-3}&\qquad\leq 0.0177\\\
&\qquad\|F\|_{2}&\in&[7.7262,7.7492]&\qquad\leq 9.2927\end{array}$

These simulations seem to indicate that our bounds on $\mu_{F}$ and
$\|F\|_{2}$ reflect real-world behavior, at least within an order of
magnitude, whereas the bound on $\nu_{F}$ is rather loose.

###  3.2 Random harmonic frames

Random harmonic frames, constructed by randomly selecting rows of a discrete
Fourier transform (DFT) matrix and normalizing the resulting columns, have
received considerable attention lately in the compressed sensing literature
[12, 14, 42]. However, to the best of our knowledge, there is no result in the
literature that shows that random harmonic frames have small worst-case
coherence. To fill this gap, the following theorem characterizes the spectral
norm and the worst-case and average coherence of random harmonic frames.

######  Theorem 10 (Geometry of random harmonic frames).

Let $U$ be an $N\times N$ non-normalized discrete Fourier transform matrix,
explicitly, $U_{k\ell}:=\mathrm{e}^{2\pi\mathrm{i}k\ell/N}$ for each
$k,\ell=0,\ldots,N-1$. Next, let $\\{B_{i}\\}_{i=0}^{N-1}$ be a collection of
independent Bernoulli random variables with mean $\smash{\frac{M}{N}}$, and
take $\mathcal{M}:=\\{i:B_{i}=1\\}$. Finally, construct an
$|\mathcal{M}|\times N$ harmonic frame $F$ by collecting rows of $U$ which
correspond to indices in $\mathcal{M}$ and normalize the columns. Then $F$ is
a unit norm tight frame: $\smash{\|F\|_{2}^{2}=\frac{N}{|\mathcal{M}|}}$.
Furthermore, provided $\smash{16\log{N}\leq M\leq\frac{N}{3}}$, the following
inequalities simultaneously hold with probability exceeding
$1-4N^{-1}-N^{-2}$:

  1. (i)

$\frac{1}{2}M\leq|\mathcal{M}|\leq\frac{3}{2}M$,

  2. (ii)

$\nu_{F}\leq\frac{\mu_{F}}{\sqrt{|\mathcal{M}|}}$,

  3. (iii)

$\mu_{F}\leq\sqrt{\frac{118(N-M)\log{N}}{MN}}$.

###### Proof.

The claim that $F$ is tight follows trivially from the fact that the rows of
$U$ are orthogonal and that the rows of $F$ correspond to a subset of the rows
of $U$. Next, we define the probability events
$\smash{\mathcal{E}_{1}:=\\{|\mathcal{M}|\leq\tfrac{3}{2}M\\}}$ and
$\smash{\mathcal{E}_{2}:=\\{|\mathcal{M}|\geq\tfrac{1}{2}M\\}}$, and claim
that
$\smash{\Pr(\mathcal{E}_{1}^{\mathrm{c}}\cup\mathcal{E}_{2}^{\mathrm{c}})\leq
N^{-1}+N^{-2}}$. The proof of this claim follows from a Bernstein-like large
deviation inequality. Specifically, note that
$\smash{|\mathcal{M}|=\sum_{i=0}^{N-1}B_{i}}$ with
$\mathbb{E}[|\mathcal{M}|]=M$, and so we have from [3, Theorem A.1.12, Theorem
A.1.13] and [42, pp. 4] that for any $\delta_{1}\in[0,1)$,

$\Pr\Big{(}|\mathcal{M}|>(1+\delta_{1})M\Big{)}\leq\mathrm{e}^{-M\delta_{1}^{2}(1-\delta_{1})/2}\qquad\mbox{and}\qquad\Pr\Big{(}|\mathcal{M}|<(1-\delta_{1})M\Big{)}\leq\mathrm{e}^{-M\delta_{1}^{2}/2}.$
(16)

Taking $\delta_{1}:=\tfrac{1}{2}$, then a union bound gives
$\Pr(\mathcal{E}_{1}^{\mathrm{c}}\cup\mathcal{E}_{2}^{\mathrm{c}})\leq
N^{-1}+N^{-2}$ provided $M\geq 16\log{N}$. Conditioning on
$\mathcal{E}_{1}\cap\mathcal{E}_{2}$, we have that Theorem 10(i) holds
trivially, while Theorem 10(ii) follows from Lemma 7. Specifically, we have
that $\frac{N}{3}\geq M$ guarantees $N\geq 2|\mathcal{M}|$ because of the
conditioning on $\mathcal{E}_{1}\cap\mathcal{E}_{2}$, which in turn implies
that $F$ satisfies either condition (i) or (ii) of Lemma 7, depending on
whether $0\in\mathcal{M}$. This therefore establishes that Theorem 10(i)-(ii)
simultaneously hold with probability exceeding $1-N^{-1}-N^{-2}$.

The only remaining claim is that
$\mu_{X}\leq\delta_{2}:=\sqrt{(118(N-M)\log{N})/MN}$ with high probability. To
this end, define $p:=\frac{M}{N}$, and pick any two distinct indices
$i,j\in\\{0,\dots,N-1\\}$. Note that

$\langle
f_{i},f_{j}\rangle=\tfrac{1}{|\mathcal{M}|}\sum_{k=0}^{N-1}B_{k}U_{ki}\overline{U_{kj}}=\tfrac{1}{|\mathcal{M}|}\sum_{k=0}^{N-1}(B_{k}-p)U_{ki}\overline{U_{kj}},$
(17)

where the last equality follows from the fact that $U$ has orthogonal columns.
Next, we write
$\smash{U_{ki}\overline{U_{kj}}=\cos(\theta_{k})+\mathrm{i}\sin(\theta_{k})}$
for some $\theta_{k}\in[0,2\pi)$. Then applying the union bound to (17) and to
the real and imaginary parts of $\smash{U_{ki}\overline{U_{kj}}}$ gives

$\displaystyle\Pr\Big{(}|\langle f_{i},f_{j}\rangle|>\delta_{2}\Big{)}$
$\displaystyle\leq\Pr\bigg{(}\Big{|}\sum_{k=0}^{N-1}(B_{k}-p)U_{ki}\overline{U_{kj}}\Big{|}>\tfrac{M\delta_{2}}{2\sqrt{2}}\bigg{)}+\Pr\Big{(}|\mathcal{M}|<\tfrac{M}{2\sqrt{2}}\Big{)}$
$\displaystyle\leq\Pr\bigg{(}\Big{|}\sum_{k=0}^{N-1}(B_{k}-p)\cos(\theta_{k})\Big{|}>\tfrac{M\delta_{2}}{4}\bigg{)}+\Pr\bigg{(}\Big{|}\sum_{k=0}^{N-1}(B_{k}-p)\sin(\theta_{k})\Big{|}>\tfrac{M\delta_{2}}{4}\bigg{)}+N^{-3},$
(18)

where the last term follows from (16) and the fact that $M\geq 16\log{N}$.
Define random variables $Z_{k}:=(B_{k}-p)\cos(\theta_{k})$. Note that the
$Z_{k}$’s have zero mean and are jointly independent. Also, the $Z_{k}$’s are
bounded by $1-p$ almost surely since
$|(B_{k}-p)\cos(\theta_{k})|\leq\max\\{p,1-p\\}$ and $N\geq 2M$. Moreover, the
variance of each $Z_{k}$ is bounded: $\mathrm{var}(Z_{\ell})\leq p(1-p)$.
Therefore, we may use the Bernstein inequality for a sum of independent,
bounded random variables [8] to bound the probability that
$|\sum_{k=0}^{N-1}Z_{k}|$ deviates from $\delta_{3}:=\frac{M\delta_{2}}{4}$:

$\Pr\bigg{(}\Big{|}\sum_{k=0}^{N-1}(B_{k}-p)\cos(\theta_{k})\Big{|}>\delta_{3}\bigg{)}\leq
2\mathrm{e}^{-\delta_{3}^{2}/(2Np(1-p)+2(1-p)\delta_{3}/3)}\leq 2N^{-3}.$

Similarly, the probability that
$|\sum_{k=0}^{N-1}(B_{k}-p)\sin(\theta_{k})|>\delta_{3}$ is also bounded above
by $2N^{-3}$. Substituting these probability bounds into (18) gives $|\langle
f_{i},f_{j}\rangle|>\delta_{2}$ with probability at most $5N^{-3}$ provided
$M\geq 16\log{N}$. Finally, we take a union bound over the
$\smash{\binom{N}{2}}$ possible choices for $i$ and $j$ to get that Theorem
10(iii) holds with probability exceeding $1-3N^{-1}$.

The result now follows by taking a final union bound over
$\mathcal{E}_{1}^{\mathrm{c}}\cup\mathcal{E}_{2}^{\mathrm{c}}$ and
$\\{\mu_{X}>\delta_{2}\\}$. ∎

As stated earlier, random harmonic frames are not new to sparse signal
processing. Interestingly, for the application of compressed sensing, [13, 42]
provides performance guarantees for both random harmonic and Gaussian frames,
but requires more rows in a random harmonic frame to accommodate the same
level of sparsity. This suggests that random harmonic frames may be inferior
to Gaussian frames as compressed sensing matrices, but practice suggests
otherwise [22]. In a sense, Theorem 10 helps to resolve this gap in
understanding; there exist compressed sensing algorithms whose performance is
dictated by worst-case coherence [5, 21, 47, 50], and Theorem 10 states that
random harmonic frames have near-optimal worst-case coherence, being on the
order of the Welch bound with an additional $\sqrt{\log N}$ factor.

######  Example 11.

To illustrate the bounds in Theorem 10, we ran simulations in MATLAB. Picking
$N=5000$, we observed $30$ realizations of random harmonic frames for each
$M=1000,1250,1500$. The distributions of $|\mathcal{M}|$, $\nu_{F}$, and
$\mu_{F}$ were rather tight, so we only report the ranges of values attained,
along with the bounds given in Theorem 10. Notice that Theorem 10 gives a
bound on $\nu_{F}$ in terms of both $|\mathcal{M}|$ and $\mu_{F}$. To simplify
matters, we show that
$\smash{\nu_{F}\leq\frac{\min\mu_{F}}{\sqrt{\max|\mathcal{M}|}}\leq\frac{\mu_{F}}{\sqrt{|\mathcal{M}|}}}$,
where the minimum and maximum are taken over all realizations in the sample:

$\begin{array}[]{rrcll}M=1000:&\qquad|\mathcal{M}|&\in&[961,1052]&\qquad\subseteq[500,1500]\\\
&\qquad\nu_{F}&\in&[0.2000,0.8082]\times 10^{-3}&\qquad\leq
0.0023\approx\tfrac{0.0746}{\sqrt{1052}}\\\
&\qquad\mu_{F}&\in&[0.0746,0.0890]&\qquad\leq 0.8967\\\ \\\
M=1250:&\qquad|\mathcal{M}|&\in&[1207,1305]&\qquad\subseteq[625,1875]\\\
&\qquad\nu_{F}&\in&[0.2000,0.6273]\times 10^{-3}&\qquad\leq
0.0018\approx\tfrac{0.0623}{\sqrt{1305}}\\\
&\qquad\mu_{F}&\in&[0.0623,0.0774]&\qquad\leq 0.7766\\\ \\\
M=1500:&\qquad|\mathcal{M}|&\in&[1454,1590]&\qquad\subseteq[750,2250]\\\
&\qquad\nu_{F}&\in&[0.2000,0.4841]\times 10^{-3}&\qquad\leq
0.0015\approx\tfrac{0.0571}{\sqrt{1590}}\\\
&\qquad\mu_{F}&\in&[0.0571,0.0743]&\qquad\leq 0.6849\end{array}$

The reader may have noticed how consistently the average coherence value of
$\nu_{F}\approx 0.2000\times 10^{-3}$ was realized. This occurs precisely when
the zeroth row of the DFT is not selected, as the frame elements sum to zero
in this case:

$\nu_{F}:=\tfrac{1}{N-1}\max_{i\in\\{1,\ldots,N\\}}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{N}\langle
f_{i},f_{j}\rangle\bigg{|}=\tfrac{1}{N-1}\max_{i\in\\{1,\ldots,N\\}}\bigg{|}\bigg{\langle}f_{i},\sum_{j=1}^{N}f_{j}\bigg{\rangle}-\|f_{i}\|^{2}\bigg{|}=\tfrac{1}{N-1}.$

These simulations seem to indicate that our bounds on $|\mathcal{M}|$,
$\nu_{F}$, and $\mu_{F}$ leave room for improvement. The only bound that lies
within an order of magnitude of real-world behavior is our bound on
$|\mathcal{M}|$.

###  3.3 Gabor and chirp frames

Gabor frames constitute an important class of frames, as they appear in a
variety of applications such as radar [29], speech processing [53], and
quantum information theory [43]. Given a nonzero seed function
$f:\mathbb{Z}_{M}\rightarrow\mathbb{C}$, we produce all time- and frequency-
shifted versions: $f_{xy}(t):=f(t-x)\mathrm{e}^{2\pi\mathrm{i}yt/M}$,
$t\in\mathbb{Z}_{M}$. Viewing these shifted functions as vectors in
$\mathbb{C}^{M}$ gives an $M\times M^{2}$ Gabor frame. The following theorem
characterizes the spectral norm and the worst-case and average coherence of
Gabor frames generated from either a deterministic Alltop vector [1] or a
random Steinhaus vector.

######  Theorem 12 (Geometry of Gabor frames).

Take an Alltop function defined by
$\smash{f(t):=\frac{1}{\sqrt{M}}\mathrm{e}^{2\pi\mathrm{i}t^{3}/M}}$,
$t\in\mathbb{Z}_{M}$. Also, take a random Steinhaus function defined by
$\smash{g(t):=\frac{1}{\sqrt{M}}\mathrm{e}^{2\pi\mathrm{i}\theta_{t}}}$,
$t\in\mathbb{Z}_{M}$, where the $\theta_{t}$’s are independent random
variables distributed uniformly on the unit interval. Then the $M\times M^{2}$
Gabor frames $F$ and $G$ generated by $f$ and $g$, respectively, are unit norm
and tight, that is, $\|F\|_{2}=\|G\|_{2}=\sqrt{M}$, and both frames have
average coherence $\smash{\leq\frac{1}{M+1}}$. Furthermore, if $M\geq 5$ is
prime, then $\smash{\mu_{F}=\frac{1}{\sqrt{M}}}$, while if $M\geq 13$, then
$\mu_{G}\leq\sqrt{(13\log{M})/M}$ with probability exceeding $1-4M^{-1}$.

###### Proof.

The tightness claim follows from [35], in which it was shown that Gabor frames
generated by nonzero seed vectors are tight. The bound on average coherence is
a consequence of [5, Theorem 7] concerning arbitrary Gabor frames. The claim
concerning $\mu_{F}$ follows directly from [46], while the claim concerning
$\mu_{G}$ is a simple consequence of [40, Theorem 5.1]. ∎

Instead of taking all translates and modulates of a seed function, [16]
constructs _chirp frames_ by taking all powers and modulates of a chirp
function. Picking $M$ to be prime, we start with a chirp function
$h_{M}:\mathbb{Z}_{M}\rightarrow\mathbb{C}$ defined by
$\smash{h_{M}(t):=\mathrm{e}^{\pi\mathrm{i}t(t-M)/M}}$, $t\in\mathbb{Z}_{M}$.
The $M^{2}$ frame elements are then defined entrywise by
$\smash{h_{ab}(t):=\frac{1}{\sqrt{M}}h_{M}(t)^{a}\mathrm{e}^{2\pi\mathrm{i}bt/M}}$,
$t\in\mathbb{Z}_{M}$. Certainly, chirp frames are, at the very least, similar
in spirit to Gabor frames. As a matter of fact, the chirp frame is in some
sense equivalent to the Gabor frame generated by the Alltop function: it is
easy to verify that
$h_{(-6x,y-3x^{2})}(t)=\mathrm{e}^{2\pi\mathrm{i}(t^{3}+x^{3})/M}f_{xy}(t)$,
and when $M\geq 5$, the map $(x,y)\mapsto(-6x,y-3x^{2})$ is a permutation over
$\mathbb{Z}_{M}^{2}$. Using terminology from Definition 28, we say the chirp
frame is _wiggling equivalent_ to a unitary rotation of permuted Alltop Gabor
frame elements. As such, by Lemma 29, the chirp frame has the same spectral
norm and worst-case coherence as the Alltop Gabor frame, but the average
coherence may be different. In this case, the average coherence still
satisfies (SCP-2). Indeed, adding the frame elements gives

$\sum_{a=0}^{M-1}\sum_{b=0}^{M-1}h_{ab}(t)=\tfrac{1}{\sqrt{M}}\sum_{a=0}^{M-1}h_{M}(t)^{a}\sum_{b=0}^{M-1}\mathrm{e}^{2\pi\mathrm{i}bt/M}=\tfrac{1}{\sqrt{M}}\sum_{a=0}^{M-1}h_{M}(t)^{a}M\delta_{0}(t)=\sqrt{M}\bigg{(}\sum_{a=0}^{M-1}h_{M}(0)^{a}\bigg{)}~{}\delta_{0}(t)=M^{3/2}\delta_{0}(t),$

and so $\langle
h_{a^{\prime}b^{\prime}},\sum_{a=0}^{M-1}\sum_{b=0}^{M-1}h_{ab}\rangle=\langle
h_{a^{\prime}b^{\prime}},M^{3/2}\delta_{0}\rangle=M^{3/2}h_{a^{\prime}b^{\prime}}(0)=M=\frac{M^{2}}{M}$.
Therefore, Lemma 7(i) gives the result:

######  Theorem 13 (Geometry of chirp frames).

Pick $M$ prime, and let $H$ be the $M\times M^{2}$ frame of all powers and
modulates of the chirp function $f_{M}$. Then $H$ is a unit norm tight frame
with $\|H\|_{2}=\sqrt{M}$, and has worst case coherence
$\smash{\mu_{H}=\frac{1}{\sqrt{M}}}$ and average coherence
$\smash{\nu_{H}\leq\frac{\mu_{H}}{\sqrt{M}}}$.

######  Example 14.

To illustrate the bounds in Theorems 12 and 13, we consider the examples of an
Alltop Gabor frame and a chirp frame, each with $M=5$. In this case, the Gabor
frame has $\smash{\nu_{F}\approx 0.1348\leq 0.1667\approx\frac{1}{M+1}}$,
while the chirp frame has
$\smash{\nu_{H}=\frac{1}{6}\leq\frac{1}{5}=\frac{\mu_{H}}{\sqrt{M}}}$. Note
the Gabor and chirp frames have different average coherences despite being
equivalent in some sense. For the random Steinhaus Gabor frame, we ran
simulations in MATLAB and observed $30$ realizations for each $M=60,70,80$.
The distributions of $\nu_{G}$ and $\mu_{G}$ were rather tight, so we only
report the ranges of values attained, along with the bounds given in Theorem
12:

$\begin{array}[]{rrcll}M=60:&\qquad\nu_{G}&\in&[0.3916,0.5958]\times
10^{-2}&\qquad\leq 0.0164\\\ &\qquad\mu_{G}&\in&[0.3242,0.4216]&\qquad\leq
0.9419\\\ \\\ M=70:&\qquad\nu_{G}&\in&[0.3151,0.4532]\times 10^{-2}&\qquad\leq
0.0141\\\ &\qquad\mu_{G}&\in&[0.2989,0.3814]&\qquad\leq 0.8883\\\ \\\
M=80:&\qquad\nu_{G}&\in&[0.2413,0.3758]\times 10^{-2}&\qquad\leq 0.0124\\\
&\qquad\mu_{G}&\in&[0.2711,0.3796]&\qquad\leq 0.8439\end{array}$

These simulations seem to indicate that bound on $\nu_{G}$ is conservative by
an order of magnitude.

###  3.4 Spherical 2-designs

Lemma 7(ii) leads one to consider frames of vectors that sum to zero. In [31],
it is proved that real unit norm tight frames with this property make up
another well-studied class of vector packings: spherical 2-designs. To be
clear, a collection of unit-norm vectors $F\subseteq\mathbb{R}^{M}$ is called
a spherical $t$-design if, for every polynomial $g(x_{1},\ldots,x_{M})$ of
degree at most $t$, we have

$\tfrac{1}{\mathrm{H}^{M-1}(S^{M-1})}\int_{S^{M-1}}g(x)~{}\mathrm{d}\mathrm{H}^{M-1}(x)=\tfrac{1}{|F|}\sum_{f\in
F}g(f),$

where $S^{M-1}$ is the unit hypersphere in $\mathbb{R}^{M}$ and
$\mathrm{H}^{M-1}$ denotes the $(M-1)$-dimensional Hausdorff measure on
$S^{M-1}$. In words, vectors that form a spherical $t$-design serve as good
representatives when calculating the average value of a degree-$t$ polynomial
over the unit hypersphere. Today, such designs find application in quantum
state estimation [28].

Since real unit norm tight frames always exist for $N\geq M+1$, one might
suspect that spherical 2-designs are equally common, but this intuition is
faulty—the sum-to-zero condition introduces certain issues. For example, there
is no spherical 2-design when $M$ is odd and $N=M+2$. In [36], spherical
2-designs are explicitly characterized by construction. The following theorem
gives a construction based on harmonic frames:

######  Theorem 15 (Geometry of spherical 2-designs).

Pick $M$ even and $N\geq 2M$. Take an $\frac{M}{2}\times N$ harmonic frame $G$
by collecting rows from a discrete Fourier transform matrix according to a set
of nonzero indices $\mathcal{M}$ and normalize the columns. Let $m(n)$ denote
$n$th largest index in $\mathcal{M}$, and define a real $M\times N$ frame $F$
by

$F_{k\ell}:=\left\\{\begin{array}[]{ll}\sqrt{\frac{2}{M}}\cos(\frac{2\pi
m((k+1)/2)\ell}{N}),&k\mbox{ odd}\\\ \sqrt{\frac{2}{M}}\sin(\frac{2\pi
m(k/2)\ell}{N}),&k\mbox{ even}\end{array}\right.,\qquad
k=1,\ldots,M,~{}\ell=0,\ldots,N-1.$

Then $F$ is unit norm and tight, i.e., $\|F\|_{2}^{2}=\frac{N}{M}$, with
worst-case coherence $\mu_{F}\leq\mu_{G}$ and average coherence
$\nu_{F}\leq\frac{\mu_{F}}{\sqrt{M}}$.

###### Proof.

It is easy to verify that $F$ is a unit norm tight frame using the geometric
sum formula. Also, since the frame elements sum to zero and $N\geq 2M$, the
claim regarding average coherence follows from Lemma 7(ii). It remains to
prove $\mu_{F}\leq\mu_{G}$. For each distinct pair of indices
$i,j\in\\{1,\ldots,N\\}$, we have

$\langle
f_{i},f_{j}\rangle=\tfrac{2}{M}\sum_{m\in\mathcal{M}}\Big{(}\cos(\tfrac{2\pi
mi}{N})\cos(\tfrac{2\pi mj}{N})+\sin(\tfrac{2\pi mi}{N})\sin(\tfrac{2\pi
mj}{N})\Big{)}=\tfrac{2}{M}\sum_{m\in\mathcal{M}}\cos(\tfrac{2\pi
m(i-j)}{N})=\mathrm{Re}\langle g_{i},g_{j}\rangle,$

and so $|\langle f_{i},f_{j}\rangle|=|\mathrm{Re}\langle
g_{i},g_{j}\rangle|\leq|\langle g_{i},g_{j}\rangle|$. This gives the result. ∎

######  Example 16.

To illustrate the bounds in Theorem 15, we consider the spherical 2-design
constructed from a $9\times 37$ harmonic equiangular tight frame [54].
Specifically, we take a $37\times 37$ DFT matrix, choose nonzero row indices

$\mathcal{M}=\\{1,7,9,10,12,16,26,33,34\\},$

and normalize the columns to get a harmonic frame $G$ whose worst-case
coherence achieves the Welch bound:
$\smash{\mu_{G}=\sqrt{\frac{37-9}{9(37-1)}}\approx 0.2940}$. Following Theorem
15, we produce a spherical 2-design $F$ with $\mu_{F}\approx
0.1967\leq\mu_{G}$ and $\smash{\nu_{F}\approx 0.0278\leq
0.0464\approx\frac{\mu_{F}}{\sqrt{M}}}$.

###  3.5 Steiner equiangular tight frames

We now consider a construction that dates back to Seidel with [44], and was
recently developed further in [24]. Here, a special type of block design is
used to build an equiangular tight frame (ETF), that is, a tight frame in
which the modulus of every inner product between frame elements achieves the
Welch bound. Let’s start with a definition:

######  Definition 17.

A $(t,k,v)$-_Steiner system_ is a $v$-element set $V$ with a collection of
$k$-element subsets of $V$, called _blocks_ , with the property that any
$t$-element subset of $V$ is contained in exactly one block. The
$\\{0,1\\}$-_incidence matrix_ $A$ of a Steiner system has entries $A_{ij}$,
where $A_{ij}=1$ if the $i$th block contains the $j$th element, and otherwise
$A_{ij}=0$.

One example of a Steiner system is a set with all possible two-element blocks.
This forms a $(2,2,v)$-Steiner system because every pair of elements is
contained in exactly one block. The following theorem details how [24]
constructs ETFs using Steiner systems.

######  Theorem 18 (Constructing Steiner equiangular tight frames [24]).

Every $(2,k,v)$-Steiner system can be used to build a
$\smash{\frac{v(v-1)}{k(k-1)}\times v(1+\frac{v-1}{k-1})}$ equiangular tight
frame $F$ according the following procedure:

  1. (i)

Let $A$ be the $\frac{v(v-1)}{k(k-1)}\times v$ incidence matrix of a
$(2,k,v)$-Steiner system.

  2. (ii)

Let $H$ be the $(1+\frac{v-1}{k-1})\times(1+\frac{v-1}{k-1})$ discrete Fourier
transform matrix.

  3. (iii)

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

  4. (iv)

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

As an example, we build an ETF from a (2,2,3)-Steiner system. In this case,
the incidence matrix is

$A=\left[\begin{array}[]{ccc}+&+&\\\ +&&+\\\ &+&+\end{array}\right].$

For this matrix, each row represents a block. Since each block contains two
elements, each row of the matrix has two ones. Also, any two elements
determines a unique common row, and so any two columns have a single one in
common. To form the corresponding $3\times 9$ ETF $F$, we use the $3\times 3$
DFT matrix. Letting $\omega=\mathrm{e}^{2\pi\mathrm{i}/3}$, we have

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

Finally, we replace the two ones in each column of $A$ with the second and
third rows of $H$. Normalizing the columns gives $3\times 9$ ETF:

$F=\tfrac{1}{\sqrt{2}}\left[\begin{array}[]{lllllllll}1&\omega&\omega^{2}&1&\omega&\omega^{2}&&&\\\
1&\omega^{2}&\omega&&&&1&\omega&\omega^{2}\\\
&&&1&\omega^{2}&\omega&1&\omega^{2}&\omega\end{array}\right].$ (19)

Several infinite families of $(2,k,v)$-Steiner systems are already known, and
Theorem 18 says that each one can be used to build an ETF. See [24] for a
complete discussion of this construction and how it relates to each known
family of Steiner systems. Interestingly, every Steiner ETF satisfies $N\geq
2M$. If, in step (iii) of Theorem 18, we choose the distinct rows to be the
$\frac{v-1}{k-1}$ rows of the DFT $H$ that are not all-ones, then the sum of
columns of each $F_{j}$ is zero, meaning the sum of columns of $F$ is also
zero. This was done in the example above, and the columns sum to zero,
accordingly. Therefore, by Lemma 7(ii), Steiner ETFs satisfy (SCP-2). This
gives the following theorem:

######  Theorem 19 (Geometry of Steiner equiangular tight frames).

Build an $M\times N$ matrix $F$ according to Theorem 18, and in step (iii),
choose rows from the discrete Fourier transform matrix $H$ that are not all-
ones. Then $F$ is an equiangular tight frame, meaning
$\|F\|_{2}^{2}=\frac{N}{M}$ and $\mu_{F}^{2}=\frac{N-M}{M(N-1)}$, and has
average coherence $\nu_{F}\leq\frac{\mu_{F}}{\sqrt{M}}$.

######  Example 20.

To illustrate the bound in Theorem 19, we note that the example given in (19)
has
$\smash{\nu_{F}=\frac{1}{8}\leq\frac{1}{2\sqrt{3}}=\frac{\mu_{F}}{\sqrt{M}}}$.

###  3.6 Code-based frames

Many structures in coding theory are also useful in frame theory. In this
section, we build frames from a code that originally emerged with Berlekamp in
[9], and found recent reincarnation with [55]. We build a $2^{m}\times
2^{(t+1)m}$ frame, indexing rows by elements of $\mathbb{F}_{2^{m}}$ and
indexing columns by $(t+1)$-tuples of elements from $\mathbb{F}_{2^{m}}$. For
$x\in\mathbb{F}_{2^{m}}$ and $\alpha\in\mathbb{F}_{2^{m}}^{t+1}$, the
corresponding entry of the matrix $F$ is given by

$F_{x\alpha}=\tfrac{1}{\sqrt{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}x+\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}},$
(20)

where $\mathrm{Tr}:\mathbb{F}_{2^{m}}\rightarrow\mathbb{F}_{2}$ denotes the
trace map, defined by $\mathrm{Tr}(z)=\sum_{i=0}^{m-1}z^{2^{i}}$. The
following theorem gives the spectral norm and the worst-case and average
coherence of this frame.

Name | $\mathbb{R}/\mathbb{C}$ | Size | $\mu_{F}$ | $\nu_{F}$ | Restrictions | Probability
---|---|---|---|---|---|---
Normalized Gaussian | $\mathbb{R}$ | $M\times N$ | $\leq\frac{\sqrt{15\log{N}}}{\sqrt{M}-\sqrt{12\log{N}}}$ | $\leq\frac{\sqrt{15\log{N}}}{M-\sqrt{12M\log{N}}}$ | $60\log N\leq M\leq\frac{N-1}{4\log N}$ | $\geq 1-\frac{11}{N}$
Random harmonic | $\mathbb{C}$ |  $|\mathcal{M}|\times N$, $\frac{1}{2}M\leq|\mathcal{M}|\leq\frac{3}{2}M$ | $\leq\sqrt{\frac{118(N-M)\log{N}}{MN}}$ | $\leq\frac{\mu_{F}}{\sqrt{|\mathcal{M}|}}$ | $16\log{N}\leq M\leq\frac{N}{3}$ | $\geq 1-\frac{4}{N}-\frac{1}{N^{2}}$
Alltop Gabor | $\mathbb{C}$ | $M\times M^{2}$ | $=\frac{1}{\sqrt{M}}$ | $\leq\frac{1}{M+1}$ |  $M\geq 5$ prime | Deterministic
Steinhaus Gabor | $\mathbb{C}$ | $M\times M^{2}$ | $\leq\sqrt{\frac{13\log M}{M}}$ | $\leq\frac{1}{M+1}$ | $M\geq 13$ | $\geq 1-\frac{4}{M}$
Chirp | $\mathbb{C}$ | $M\times M^{2}$ | $=\frac{1}{\sqrt{M}}$ | $\leq\frac{\mu_{F}}{\sqrt{M}}$ |  $M$ prime | Deterministic
$\overset{\mbox{Spherical 2-design}}{\mbox{from harmonic }G}$ | $\mathbb{R}$ | $M\times N$ | $\leq\mu_{G}$ | $\leq\frac{\mu_{F}}{\sqrt{M}}$ |  $M$ even, $N\geq 2M$ | Deterministic
Steiner | $\mathbb{C}$ |  $M\times N$, $M=\frac{v(v-1)}{k(k-1)}$, $N=v(1+\frac{v-1}{k-1})$ | $=\sqrt{\frac{N-M}{M(N-1)}}$ | $\leq\frac{\mu_{F}}{\sqrt{M}}$ |  $\exists(2,k,v)$-Steiner system | Deterministic
Code-based | $\mathbb{R}$ | $2^{m}\times 2^{(t+1)m}$ | $\leq\frac{1}{\sqrt{2^{m-2t-1}}}$ | $\leq\frac{\mu_{F}}{\sqrt{2^{m}}}$ | None | Deterministic
Table 1:  Eight constructions detailed in this paper. All of these are unit
norm tight frames except for the normalized Gaussian frame, which has squared
spectral norm
$\|F\|_{2}^{2}\leq(\\!\sqrt{M}+\\!\sqrt{N}+\\!\sqrt{2\log{N}})^{2}/(M-\\!\sqrt{8M\log{N}})$
in the same probability event as is measured above.

######  Theorem 21 (Geometry of code-based frames).

The $2^{m}\times 2^{(t+1)m}$ frame defined by (20) is unit norm and tight,
i.e., $\|F\|_{2}^{2}=2^{tm}$, with worst-case coherence
$\mu_{F}\leq\frac{1}{\sqrt{2^{m-2t-1}}}$ and average coherence
$\smash{\nu_{F}\leq\frac{\mu_{F}}{\sqrt{2^{m}}}}$.

###### Proof.

For the tightness claim, we use the linearity of the trace map to write the
inner product of rows $x$ and $y$:

$\sum_{\alpha\in\mathbb{F}_{2^{m}}^{t+1}}\\!\\!\tfrac{1}{\sqrt{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}x+\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}}\tfrac{1}{\sqrt{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}y+\sum_{i=1}^{t}\alpha_{i}y^{2^{i}+1}\big{]}}=\tfrac{1}{2^{m}}\bigg{(}\\!\sum_{\alpha_{0}\in\mathbb{F}_{2^{m}}}(-1)^{\mathrm{Tr}[\alpha_{0}(x+y)]}\bigg{)}\\!\\!\sum_{\alpha_{1}\in\mathbb{F}_{2^{m}}}\\!\\!\cdots\\!\\!\sum_{\alpha_{t}\in\mathbb{F}_{2^{m}}}\\!\\!(-1)^{\mathrm{Tr}\big{[}\sum_{i=1}^{t}\alpha_{i}(x^{2^{i}+1}+y^{2^{i}+1})\big{]}}.$

This expression is $2^{tm}$ when $x=y$. Otherwise, note that
$\alpha_{0}\mapsto(-1)^{\mathrm{Tr}[\alpha_{0}(x+y)]}\in\\{\pm 1\\}$ defines a
homomorphism on $\mathbb{F}_{2^{m}}$. Since $(x+y)^{-1}\mapsto-1$, the inverse
images of $\pm 1$ under this homomorphism must form two cosets of equal size,
and so
$\sum_{\alpha_{0}\in\mathbb{F}_{2^{m}}}(-1)^{\mathrm{Tr}[\alpha_{0}(x+y)]}=0$,
meaning distinct rows in $F$ are orthogonal. Thus, $F$ is a unit norm tight
frame.

For the worst-case coherence claim, we first note that the linearity of the
trace map gives

$(-1)^{\mathrm{Tr}\big{[}\alpha_{0}x+\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}}(-1)^{\mathrm{Tr}\big{[}\alpha^{\prime}_{0}x+\sum_{i=1}^{t}\alpha^{\prime}_{i}x^{2^{i}+1}\big{]}}=(-1)^{\mathrm{Tr}\big{[}(\alpha_{0}+\alpha^{\prime}_{0})x+\sum_{i=1}^{t}(\alpha_{i}+\alpha^{\prime}_{i})x^{2^{i}+1}\big{]}},$

i.e., every inner product between columns of $F$ is a sum over another column.
Thus, there exists $\alpha\in\mathbb{F}_{2^{m}}^{t+1}$ such that

$2^{2m}\mu_{F}^{2}=\bigg{(}\sum_{x\in\mathbb{F}_{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}x+\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}}\bigg{)}^{2}=2^{m}+\sum_{x\in\mathbb{F}_{2^{m}}}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2^{m}}\\\
y\neq
x\end{subarray}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}(x+y)+\sum_{i=1}^{t}\alpha_{i}\big{(}(x+y)^{2^{i}+1}+\sum_{j=0}^{i-1}(xy)^{2^{j}}(x+y)^{2^{i}-2^{j+1}+1}\big{)}\big{]}},$

where the last equality is by the identity
$(x+y)^{2^{i}+1}=x^{2^{i}+1}+y^{2^{i}+1}+\sum_{j=0}^{i-1}(xy)^{2^{j}}(x+y)^{2^{i}-2^{j+1}+1}$,
whose proof is a simple exercise of induction. From here, we perform a change
of variables: $u:=x+y$ and $v:=xy$. Notice that $(u,v)$ corresponds to $(x,y)$
for some $x\neq y$ whenever $(z+x)(z+y)=z^{2}+uz+v$ has two solutions, that
is, whenever $\smash{\mathrm{Tr}(\frac{v}{u^{2}})=0}$. Since $(u,v)$
corresponds to both $(x,y)$ and $(y,x)$, we must correct for under-counting:

$\displaystyle 2^{2m}\mu_{F}^{2}$
$\displaystyle=2^{m}+2\sum_{\begin{subarray}{c}u\in\mathbb{F}_{2^{m}}\\\ u\neq
0\end{subarray}}\sum_{\begin{subarray}{c}v\in\mathbb{F}_{2^{m}}\\\
\mathrm{Tr}(v/u^{2})=0\end{subarray}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}u+\sum_{i=1}^{t}\alpha_{i}\big{(}u^{2^{i}+1}+\sum_{j=0}^{i-1}v^{2^{j}}u^{2^{i}-2^{j+1}+1}\big{)}\big{]}}$
$\displaystyle=2^{m}+2\sum_{\begin{subarray}{c}u\in\mathbb{F}_{2^{m}}\\\ u\neq
0\end{subarray}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}u+\sum_{i=1}^{t}\alpha_{i}u^{2^{i}+1}\big{]}}\sum_{\begin{subarray}{c}v\in\mathbb{F}_{2^{m}}\\\
\mathrm{Tr}(v/u^{2})=0\end{subarray}}(-1)^{\mathrm{Tr}\big{[}\big{(}\sum_{i=1}^{t}\sum_{j=0}^{i-1}\alpha_{i}^{2^{-j}}u^{2^{i-j}-2+2^{-j}}\big{)}v\big{]}}$
$\displaystyle\leq 2^{m}+2\sum_{\begin{subarray}{c}u\in\mathbb{F}_{2^{m}}\\\
u\neq
0\end{subarray}}~{}\bigg{|}\\!\\!\\!\sum_{\begin{subarray}{c}v\in\mathbb{F}_{2^{m}}\\\
\mathrm{Tr}(v/u^{2})=0\end{subarray}}\\!\\!\\!(-1)^{\mathrm{Tr}[p(u)v]}~{}\bigg{|},$
(21)

where the second equality is by repeated application of
$\mathrm{Tr}(z)=\mathrm{Tr}(z^{2})$, and
$\smash{p(u):=\sum_{i=1}^{t}\sum_{j=0}^{i-1}\alpha_{i}^{2^{-j}}u^{2^{i-j}-2+2^{-j}}}$.
To bound $\mu_{F}$, we will count the $u$’s that produce nonzero summands in
(21).

For each $u\neq 0,$ we have a homomorphism
$\smash{\chi_{u}:\\{v\in\mathbb{F}_{2^{m}}:\mathrm{Tr}(\frac{v}{u^{2}})=0\\}\rightarrow\\{\pm
1\\}}$ defined by $\chi_{u}(v):=(-1)^{\mathrm{Tr}[p(u)v]}$. Pick $u\neq 0$ for
which there exists a $v$ such that both
$\smash{\mathrm{Tr}(\frac{v}{u^{2}})=0}$ and $\mathrm{Tr}[p(u)v]=1$. Then
$\chi_{u}(v)=-1$, and so the kernel of $\chi_{u}$ is the same size as the
coset
$\smash{\\{v\in\mathbb{F}_{2^{m}}:\mathrm{Tr}(\frac{v}{u^{2}})=0,\chi_{u}(v)=-1\\}}$,
meaning the summand associated with $u$ in (21) is zero. Hence, the nonzero
summands in (21) require $\smash{\mathrm{Tr}(\frac{v}{u^{2}})=0}$ and
$\mathrm{Tr}[p(u)v]=0$. This is certainly possible whenever $p(u)=0$.
Exponentiation gives

$p(u)^{2^{t-1}}=\sum_{i=1}^{t}\sum_{j=0}^{i-1}\alpha_{i}^{2^{t-j-1}}u^{2^{t+i-j-1}-2^{t}+2^{t-j-1}},$

which has degree $2^{2t-1}-2^{t-1}$. Thus, $p(u)=0$ has at most
$2^{2t-1}-2^{t-1}$ solutions, and each such $u$ produces a summand in (21) of
size $2^{m-1}$. Next, we consider the $u$’s for which
$\smash{\mathrm{Tr}(\frac{v}{u^{2}})=0}$, $\mathrm{Tr}[p(u)v]=0$, and
$p(u)\neq 0$. In this case, the hyperplanes defined by
$\smash{\mathrm{Tr}(\frac{v}{u^{2}})=0}$ and $\mathrm{Tr}[p(u)v]=0$ are
parallel, and so $\smash{p(u)=\frac{1}{u^{2}}}$. Here,

$1=(u^{2}p(u))^{2^{t-1}}=\sum_{i=1}^{t}\sum_{j=0}^{i-1}\alpha_{i}^{2^{t-j-1}}u^{2^{t+i-j-1}+2^{t-j-1}},$

which has degree $2^{2t-1}+2^{t-1}$. Thus, $\smash{p(u)=\frac{1}{u^{2}}}$ has
at most $2^{2t-1}+2^{t-1}$ solutions, and each such $u$ produces a summand in
(21) of size $2^{m-1}$. We can now continue the bound from (21):
$2^{2m}\mu_{F}^{2}\leq 2^{m}+2(2^{2t-1}-2^{t-1}+2^{2t-1}+2^{t-1})2^{m-1}\leq
2^{m+2t+1}$. From here, isolating $\mu_{F}$ gives the claim.

Lastly, for the average coherence, pick some $x\in\mathbb{F}_{2^{m}}$. Then
summing the entries in the $x$th row gives

$\sum_{\alpha\in\mathbb{F}_{2^{m}}^{t+1}}\tfrac{1}{\sqrt{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\alpha_{0}x+\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}}=\tfrac{1}{\sqrt{2^{m}}}\bigg{(}\sum_{\alpha_{0}\in\mathbb{F}_{2^{m}}}(-1)^{\mathrm{Tr}(\alpha_{0}x)}\bigg{)}\sum_{\alpha_{1}\in\mathbb{F}_{2^{m}}}\cdots\sum_{\alpha_{t}\in\mathbb{F}_{2^{m}}}(-1)^{\mathrm{Tr}\big{[}\sum_{i=1}^{t}\alpha_{i}x^{2^{i}+1}\big{]}}=\left\\{\begin{array}[]{lc}2^{(t+1/2)m},&x=0\\\
0,&x\neq 0\end{array}\right..$

That is, the frame elements sum to a multiple of an identity basis element:
$\smash{\sum_{\alpha\in\mathbb{F}_{2^{m}}^{t+1}}f_{\alpha}=2^{(t+1/2)m}\delta_{0}}$.
Since every entry in row $x=0$ is $\smash{\frac{1}{\sqrt{2^{m}}}}$, we have
$\smash{\langle
f_{\alpha^{\prime}},\sum_{\alpha\in\mathbb{F}_{2^{m}}^{t+1}}f_{\alpha}\rangle=\frac{2^{(t+1)m}}{2^{m}}}$
for every $\alpha^{\prime}\in\mathbb{F}_{2^{m}}^{t+1}$, and so by Lemma 7(i),
we are done. ∎

######  Example 22.

To illustrate the bounds in Theorem 21, we consider the example where $m=4$
and $t=1$. This is a $16\times 256$ code-based frame $F$ with
$\smash{\mu_{F}=\frac{1}{2}\leq\frac{1}{\sqrt{2}}=\frac{1}{\sqrt{2^{m-2t-1}}}}$
and
$\smash{\nu_{F}=\frac{1}{17}\leq\frac{1}{8}=\frac{\mu_{F}}{\sqrt{2^{m}}}}$.

##  4 Fundamental limits on worst-case coherence

In many applications of frames, performance is dictated by worst-case
coherence [5, 11, 21, 31, 37, 46, 47, 50, 56]. It is therefore particularly
important to understand which worst-case coherence values are achievable. To
this end, the Welch bound is commonly used in the literature. When worst-case
coherence achieves the Welch bound, the frame is equiangular and tight [46];
one of the biggest open problems in frame theory concerns equiangular tight
frames [43]. However, equiangular tight frames cannot have more vectors than
the square of the spatial dimension [46], meaning the Welch bound is not tight
whenever $N>M^{2}$. When the number of vectors $N$ is exceedingly large, the
following theorem gives a better bound:

######  Theorem 23 ([2, 39]).

Every sufficiently large $M\times N$ unit norm frame $F$ with $N\geq 2M$ and
worst-case coherence $\mu_{F}<\frac{1}{2}$ satisfies

$\mu_{F}^{2}\log\big{(}\tfrac{1}{\mu_{F}}\big{)}\geq\tfrac{C\log N}{M}$ (22)

for some constant $C>0$.

For a fixed worst-case coherence $\mu_{F}<\frac{1}{2}$, this bound indicates
that the number of vectors $N$ cannot exceed some exponential in the spatial
dimension $M$, that is, $N\leq a^{M}$ for some $a>0$. However, since the
constant $C$ is not established in this theorem, it is unclear which base $a$
is appropriate for each $\mu_{F}$. The following theorem is a little more
explicit in this regard:

######  Theorem 24 ([38, 54]).

Every $M\times N$ unit norm frame $F$ has worst-case coherence $\mu_{F}\geq
1-2N^{-1/(M-1)}$. Furthermore, taking $N=\Theta(a^{M})$, this lower bound goes
to $1-\frac{2}{a}$ as $M\rightarrow\infty$.

For many applications, it does not make sense to use a complex frame, but the
bound in Theorem 24 is known to be loose for real frames [18]. We therefore
improve Theorems 23 and 24 for the case of real unit norm frames:

######  Theorem 25.

Every real $M\times N$ unit norm frame $F$ has worst-case coherence

$\mu_{F}\geq\cos\bigg{[}\pi\Big{(}\tfrac{M-1}{N\pi^{1/2}}~{}\tfrac{\Gamma(\frac{M-1}{2})}{\Gamma(\frac{M}{2})}\Big{)}^{\frac{1}{M-1}}\bigg{]}.$
(23)

Furthermore, taking $N=\Theta(a^{M})$, this lower bound goes to
$\cos(\frac{\pi}{a})$ as $M\rightarrow\infty$.

Before proving this theorem, we first consider the special case where the
spatial dimension is $M=3$:

######  Lemma 26.

Given $N$ points on the unit sphere $S^{2}\subseteq\mathbb{R}^{3}$, the
smallest angle between points is $\leq 2\cos^{-1}\big{(}1-\frac{2}{N}\big{)}$.

###### Proof.

We first claim there exists a closed spherical cap in $S^{2}$ with area
$\smash{\frac{4\pi}{N}}$ that contains two of the $N$ points. Suppose
otherwise, and take $\gamma$ to be the angular radius of a spherical cap with
area $\smash{\frac{4\pi}{N}}$. That is, $\gamma$ is the angle between the
center of the cap and every point on the boundary. Since the cap is closed, we
must have that the smallest angle $\alpha$ between any two of our $N$ points
satisfies $\alpha>2\gamma$. Let $C(p,\theta)$ denote the closed spherical cap
centered at $p\in S^{2}$ of angular radius $\theta$, and let $P$ denote our
set of $N$ points. Then we know for $p\in P$, the $C(p,\gamma)$’s are
disjoint, $\frac{\alpha}{2}>\gamma$, and $\bigcup_{p\in
P}C(p,\tfrac{\alpha}{2})\subseteq S^{2}$, and so taking 2-dimensional
Hausdorff measures on the sphere gives

$\mathrm{H}^{2}(S^{2})=4\pi=\mathrm{H}^{2}\bigg{(}\bigcup_{p\in
P}C(p,\gamma)\bigg{)}<\mathrm{H}^{2}\bigg{(}\bigcup_{p\in
P}C(p,\tfrac{\alpha}{2})\bigg{)}\leq\mathrm{H}^{2}(S^{2}),$

a contradiction.

Since two of the points reside in a spherical cap of area
$\smash{\frac{4\pi}{N}}$, we know $\alpha$ is no more than twice the radius of
this cap. We use spherical coordinates to relate the cap’s area to the radius:
$\smash{\mathrm{H}^{2}(C(\cdot,\gamma))=2\pi\int_{0}^{\gamma}\sin\phi~{}\mathrm{d}\phi=2\pi(1-\cos\gamma)}$.
Therefore, when $\smash{\mathrm{H}^{2}(C(\cdot,\gamma))=\frac{4\pi}{N}}$, we
have $\gamma=\cos^{-1}(1-\frac{2}{N})$, and so $\alpha\leq 2\gamma$ gives the
result. ∎

######  Theorem 27.

Every real $3\times N$ unit norm frame $F$ has worst-case coherence
$\mu_{F}\geq 1-\frac{4}{N}+\frac{2}{N^{2}}$.

###### Proof.

Packing $N$ unit vectors in $\mathbb{R}^{3}$ corresponds to packing $2N$
antipodal points in $S^{2}$, and so Lemma 26 gives $\alpha\leq
2\cos^{-1}(1-\frac{1}{N})$. Applying the double angle formula to
$\mu_{F}=\cos\alpha\geq\cos[2\cos^{-1}(1-\frac{1}{N})]$ gives the result. ∎

$N$$\mu_{F}$Numerically optimalWelch boundTheorem 24Theorem 25Theorem 27
Figure 1: Different bounds on worst-case coherence for $M=3$, $N=3,\ldots,55$.
Stars give numerically determined optimal worst-case coherence of $N$ real
unit vectors, found in [18]. Dotted curve gives Welch bound, dash-dotted curve
gives bound from Theorem 24, dashed curve gives bound from Theorem 25, and
solid curve gives bound from Theorem 27.

Now that we understand the special case where $M=3$, we tackle the general
case:

###### Proof of Theorem 25.

As in the proof of Theorem 27, we relate packing $N$ unit vectors to packing
$2N$ points in the hypersphere $S^{M-1}\subseteq\mathbb{R}^{M}$. The argument
in the proof of Lemma 26 generalizes so that two of the $2N$ points must
reside in some closed hyperspherical cap of hypersurface area
$\frac{1}{2N}\mathrm{H}^{M-1}(S^{M-1})$. Therefore, the smallest angle
$\alpha$ between these points is no more than twice the radius of this cap.
Let $C(\gamma)$ denote a hyperspherical cap of angular radius $\gamma$. Then
we use hyperspherical coordinates to get

$\displaystyle\mathrm{H}^{M-1}(C(\gamma))$
$\displaystyle=\int_{\phi_{1}=0}^{\gamma}\int_{\phi_{2}=0}^{\pi}\cdots\int_{\phi_{M-2}=0}^{\pi}\int_{\phi_{M-1}=0}^{2\pi}\sin^{M-2}(\phi_{1})\cdots\sin^{1}(\phi_{M-2})~{}\mathrm{d}\phi_{M-1}\cdots\mathrm{d}\phi_{1}$
$\displaystyle=2\pi\bigg{(}\prod_{j=1}^{M-3}\pi^{1/2}\tfrac{\Gamma(\frac{j+1}{2})}{\Gamma(\frac{j}{2}+1)}\bigg{)}\int_{0}^{\gamma}\sin^{M-2}\phi~{}\mathrm{d}\phi$
$\displaystyle=\tfrac{2\pi^{(M-1)/2}}{\Gamma(\frac{M-1}{2})}\int_{0}^{\gamma}\sin^{M-2}\phi~{}\mathrm{d}\phi.$
(24)

We wish to solve for $\gamma$, but analytically inverting
$\int_{0}^{\gamma}\sin^{M-2}\phi~{}\mathrm{d}\phi$ is difficult. Instead, we
use $\sin\phi\geq\frac{2\phi}{\pi}$ for $\phi\in[0,\frac{\pi}{2}]$. Note that
we do not lose generality by forcing $\gamma\leq\frac{\pi}{2}$, since this is
guaranteed with $N\geq 2$. Continuing (24) gives

$\mathrm{H}^{M-1}(C(\gamma))\geq\tfrac{2\pi^{(M-1)/2}}{\Gamma(\frac{M-1}{2})}\int_{0}^{\gamma}\big{(}\tfrac{2\phi}{\pi}\big{)}^{M-2}\mathrm{d}\phi=\tfrac{(2\gamma)^{M-1}}{(M-1)\pi^{(M-3)/2}\Gamma(\frac{M-1}{2})}.$
(25)

Using the formula for a hypersphere’s hypersurface area, we can express the
left-hand side of (25):

$\tfrac{(2\gamma)^{M-1}}{(M-1)\pi^{(M-3)/2}\Gamma(\frac{M-1}{2})}\leq\mathrm{H}^{M-1}(C(\gamma))=\tfrac{1}{2N}\mathrm{H}^{M-1}(S^{M-1})=\tfrac{\pi^{M/2}}{N\Gamma(\frac{d}{2})}.$

Isolating $2\gamma$ above and using $\alpha\leq 2\gamma$ and $\mu=\cos\alpha$
gives (23). The second part of the result comes from a simple application of
Stirling’s approximation. ∎

In [18], numerical results are given for $M=3$, and we compare these results
to Theorems 24 and 25 in Figure 1. Considering this figure, we note that the
bound in Theorem 24 is inferior to the maximum of the Welch bound and the
bound in Theorem 25, at least when $M=3$. This illustrates the degree to which
Theorem 25 improves the bound in Theorem 24 for real frames. In fact, since
$\cos(\frac{\pi}{a})\geq 1-\frac{2}{a}$ for all $a\geq 2$, the bound for real
frames in Theorem 25 is asymptotically better than the bound for complex
frames in Theorem 24. Moreover, for $M=2$, Theorem 25 says
$\mu\geq\cos(\frac{\pi}{N})$, and [7] proved this bound to be tight for every
$N\geq 2$. Lastly, Figure 1 illustrates that Theorem 27 improves the bound in
Theorem 25 for the case $M=3$.

In many applications, large dictionaries are built to obtain sparse
reconstruction, but the known guarantees on sparse reconstruction place
certain requirements on worst-case coherence. Asymptotically, the bounds in
Theorems 24 and 25 indicate that certain exponentially large dictionaries will
not satisfy these requirements. For example, if $N=\Theta(3^{M})$, then
$\mu_{F}=\Omega(\frac{1}{3})$ by Theorem 24, and if the frame is real, we have
$\mu_{F}=\Omega(\frac{1}{2})$ by Theorem 25. Such a dictionary will only work
for sparse reconstruction if the sparsity level $K$ is sufficiently small;
deterministic guarantees require $K<\mu_{F}^{-1}$ [21, 48], while
probabilistic guarantees require $K<\mu_{F}^{-2}$ [5, 49], and so in this
example, the dictionary can, at best, only accommodate sparsity levels that
are smaller than 10. Unfortunately, in real-world applications, we can expect
the sparsity level to scale with the signal dimension. This in mind, Theorems
24 and 25 tell us that dictionaries can only be used for sparse reconstruction
if $N=O((2+\epsilon)^{M})$ for some sufficiently small $\epsilon>0$. To
summarize, the Welch bound is known to be tight only if $N\leq M^{2}$, and
Theorems 24 and 25 give bounds which are asympotically better than the Welch
bound whenever $N=\Omega(2^{M})$. When $N$ is between $M^{2}$ and $2^{M}$, the
best bound to date is the (loose) Welch bound, and so more work needs to be
done to bound worst-case coherence in this parameter region.

##  5 Reducing average coherence

In [5], average coherence is used to derive a number of guarantees on sparse
signal processing. Since average coherence is so new to the frame theory
literature, this section will investigate how average coherence relates to
worst-case coherence and the spectral norm. We start with a definition:

######  Definition 28 (Wiggling and flipping equivalent frames).

We say the frames $F$ and $G$ are _wiggling equivalent_ if there exists a
diagonal matrix $D$ of unimodular entries such that $G=FD$. Furthermore, they
are _flipping equivalent_ if $D$ is real, having only $\pm 1$’s on the
diagonal.

The terms “wiggling” and “flipping” are inspired by the fact that individual
frame elements of such equivalent frames are related by simple unitary
operations. Note that every frame with $N$ nonzero frame elements belongs to a
flipping equivalence class of size $2^{N}$, while being wiggling equivalent to
uncountably many frames. The importance of this type of frame equivalence is,
in part, due to the following lemma, which characterizes the shared geometry
of wiggling equivalent frames:

######  Lemma 29 (Geometry of wiggling equivalent frames).

Wiggling equivalence preserves the norms of frame elements, the worst-case
coherence, and the spectral norm.

###### Proof.

Take two frames $F$ and $G$ such that $G=FD$. The first claim is immediate.
Next, the Gram matrices are related by $G^{*}G=D^{*}F^{*}FD$. Since
corresponding off-diagonal entries are equal in modulus, we know the worst-
case coherences are equal. Finally,
$\|G\|_{2}^{2}=\|GG^{*}\|_{2}^{2}=\|FDD^{*}F^{*}\|_{2}=\|FF^{*}\|_{2}=\|F\|_{2}^{2}$,
and so we are done. ∎

Wiggling and flipping equivalence are not entirely new to frame theory. For a
real equiangular tight frame $F$, the Gram matrix $F^{*}F$ is completely
determined by the sign pattern of the off-diagonal entries, which can in turn
be interpreted as the Seidel adjacency matrix of a graph $G_{F}$. As such,
flipping a frame element $f\in F$ has the effect of negating the corresponding
row and column in the Gram matrix, which further corresponds to _switching_
the adjacency rule for that vertex $v_{f}\in V(G_{F})$ in the graph—vertices
are adjacent to $v_{f}$ after switching precisely when they were not adjacent
before switching. Graphs are called _switching equivalent_ if there is a
sequence of switching operations that produces one graph from the other; this
equivalence was introduced in [51] and was later extensively studied by Seidel
in [44, 45]. Since flipping equivalent real equiangular tight frames
correspond to switching equivalent graphs, the terms have become
interchangeable. For example, [15] uses switching (i.e., wiggling and
flipping) equivalence to make progress on an important problem in frame theory
called the _Paulsen problem_ , which asks how close a nearly unit norm, nearly
tight frame must be to a unit norm tight frame.

Now that we understand wiggling and flipping equivalence, we are ready for the
main idea behind this section. Suppose we are given a unit norm frame with
acceptable spectral norm and worst-case coherence, but we also want the
average coherence to satisfy (SCP-2). Then by Lemma 29, all of the wiggling
equivalent frames will also have acceptable spectral norm and worst-case
coherence, and so it is reasonable to check these frames for good average
coherence. In fact, the following theorem guarantees that at least one of the
flipping equivalent frames will have good average coherence, with only modest
requirements on the original frame’s redundancy.

######  Theorem 30 (Constructing frames with low average coherence).

Let $F$ be an $M\times N$ unit norm frame with $\smash{M<\frac{N-1}{4\log
4N}}$. Then there exists a frame $G$ that is flipping equivalent to $F$ and
satisfies $\smash{\nu_{G}\leq\frac{\mu_{G}}{\sqrt{M}}}$.

###### Proof.

Take $\\{R_{n}\\}_{n=1}^{N}$ to be a Rademacher sequence that independently
takes values $\pm 1$, each with probability $\frac{1}{2}$. We use this
sequence to randomly flip $F$; define
$Z:=F~{}\mathrm{diag}\\{R_{n}\\}_{n=1}^{N}$. Note that if
$\smash{\Pr(\nu_{Z}\leq\frac{\mu_{F}}{\sqrt{M}})>0}$, we are done. Fix some
$i\in\\{1,\ldots,N\\}$. Then

$\Pr\Bigg{(}\tfrac{1}{N-1}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\langle
z_{i},z_{j}\rangle\bigg{|}>\tfrac{\mu_{F}}{\sqrt{M}}\Bigg{)}=\Pr\Bigg{(}\bigg{|}\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{N}R_{j}\langle
f_{i},f_{j}\rangle\bigg{|}>\tfrac{(N-1)\mu_{F}}{\sqrt{M}}\Bigg{)}.$ (26)

We can view $\sum_{j\neq i}R_{j}\langle f_{i},f_{j}\rangle$ as a sum of $N-1$
independent zero-mean complex random variables that are bounded by $\mu_{F}$.
We can therefore use a complex version of Hoeffding’s inequality [30] (see,
e.g., [4, Lemma 3.8]) to bound the probability expression in (26) as $\leq
4\mathrm{e}^{-(N-1)/4M}$. From here, a union bound over all $N$ choices for
$i$ gives $\Pr(\nu_{Z}\leq\frac{\mu_{F}}{\sqrt{M}})\geq
1-4N\mathrm{e}^{-(N-1)/4M}$, and so $M<\frac{N-1}{4\log 4N}$ implies
$\Pr(\nu_{Z}\leq\frac{\mu_{F}}{\sqrt{M}})>0$, as desired. ∎

While Theorem 30 guarantees the existence of a flipping equivalent frame with
good average coherence, the result does not describe how to find it.
Certainly, one could check all $2^{N}$ frames in the flipping equivalence
class, but such a procedure is computationally slow. As an alternative, we
propose a linear-time flipping algorithm (Algorithm 2). The following theorem
guarantees that linear-time flipping will produce a frame with good average
coherence, but it requires the original frame’s redundancy to be higher than
what suffices in Theorem 30.

Algorithm 2 Linear-time flipping

Input: An $M\times N$ unit norm frame $F$
Output: An $M\times N$ unit norm frame $G$ that is flipping equivalent to $F$

$g_{1}\leftarrow f_{1}$ {Keep first frame element}

for $n=2$ to $N$ do

if $\|\sum_{i=1}^{n-1}g_{i}+f_{n}\|\leq\|\sum_{i=1}^{n-1}g_{i}-f_{n}\|$ then

$g_{n}\leftarrow f_{n}$ {Keep frame element to make sum length shorter}

else

$g_{n}\leftarrow-f_{n}$ {Flip frame element to make sum length shorter}

end if

end for

######  Theorem 31.

Suppose $N\geq M^{2}+3M+3$. Then Algorithm 2 outputs an $M\times N$ frame $G$
that is flipping equivalent to $F$ and satisfies
$\nu_{G}\leq\frac{\mu_{G}}{\sqrt{M}}$.

###### Proof.

Considering Lemma 7(iii), it suffices to have $\|\sum_{n=1}^{N}g_{n}\|^{2}\leq
N$. We will use induction to show $\|\sum_{n=1}^{k}g_{n}\|^{2}\leq k$ for
$k=1,\ldots,N$. Clearly, $\|\sum_{n=1}^{1}g_{n}\|^{2}=\|f_{n}\|^{2}=1\leq 1$.
Now assume $\|\sum_{n=1}^{k}g_{n}\|^{2}\leq k$. Then by our choice for
$g_{k+1}$ in Algorithm 2, we know that
$\|\sum_{n=1}^{k}g_{n}+g_{k+1}\|^{2}\leq\|\sum_{n=1}^{k}g_{n}-g_{k+1}\|^{2}$.
Expanding both sides of this inequality gives

$\bigg{\|}\sum_{n=1}^{k}g_{n}\bigg{\|}^{2}+2\mathrm{Re}\bigg{\langle}\sum_{n=1}^{k}g_{n},g_{k+1}\bigg{\rangle}+\|g_{k+1}\|^{2}\leq\bigg{\|}\sum_{n=1}^{k}g_{n}\bigg{\|}^{2}-2\mathrm{Re}\bigg{\langle}\sum_{n=1}^{k}g_{n},g_{k+1}\bigg{\rangle}+\|g_{k+1}\|^{2},$

and so $\mathrm{Re}\langle\sum_{n=1}^{k}g_{n},g_{k+1}\rangle\leq 0$.
Therefore,

$\bigg{\|}\sum_{n=1}^{k+1}g_{n}\bigg{\|}^{2}=\bigg{\|}\sum_{n=1}^{k}g_{n}\bigg{\|}^{2}+2\mathrm{Re}\bigg{\langle}\sum_{n=1}^{k}g_{n},g_{k+1}\bigg{\rangle}+\|g_{k+1}\|^{2}\leq\bigg{\|}\sum_{n=1}^{k}g_{n}\bigg{\|}^{2}+\|g_{k+1}\|^{2}\leq
k+1,$

where the last inequality uses the inductive hypothesis. ∎

######  Example 32.

As an example of how linear-time flipping reduces average coherence, consider
the following matrix:

$F:=\frac{1}{\sqrt{5}}\left[\begin{array}[]{cccccccccc}+&+&+&+&-&+&+&+&+&-\\\
+&-&+&+&+&-&-&-&+&-\\\ +&+&+&+&+&+&+&+&-&+\\\ -&-&-&+&-&+&+&-&-&-\\\
-&+&+&-&-&+&-&-&-&-\end{array}\right].$

Here, $\smash{\nu_{F}\approx 0.3778>0.2683\approx\frac{\mu_{F}}{\sqrt{M}}}$.
Even though $N<M^{2}+3M+3$, we run linear-time flipping to get the flipping
pattern $D:=\mathrm{diag}(+-+--++-++)$. Then $FD$ has average coherence
$\smash{\nu_{FD}\approx
0.1556<\frac{\mu_{F}}{\sqrt{M}}=\frac{\mu_{FD}}{\sqrt{M}}}$. This example
illustrates that the condition $N\geq M^{2}+3M+3$ in Theorem 31 is sufficient
but not necessary.

## Acknowledgments

The authors thank the anonymous referees for their helpful suggestions,
Matthew Fickus for his insightful comments on chirp frames, and Samuel Feng
and Michael A. Schwemmer for their help with using the computer clusters in
Princeton’s mathematics department. This work was supported by the Office of
Naval Research under grant N00014-08-1-1110, by the Air Force Office of
Scientific Research under grants FA9550-09-1-0551 and FA 9550-09-1-0643, and
by NSF under grant DMS-0914892. Mixon was supported by the A.B. Krongard
Fellowship. The views expressed in this article are those of the authors and
do not reflect the official policy or position of the United States Air Force,
Department of Defense, or the U.S. Government.

## References

## References

  * [1] W. Alltop, Complex sequences with low periodic correlations, IEEE Trans. Inform. Theory 26 (1980) 350–354.
  * [2] N. Alon, Problems and results in extremal combinatorics—I, Discrete Math. 273 (2003) 31–53.
  * [3] N. Alon, J. H. Spencer, The Probabilistic Method, second ed., Wiley, New York, 2000.
  * [4] W.U. Bajwa, New information processing theory and methods for exploiting sparsity in wireless systems, Ph.D. thesis, University of Wisconsin-Madison, 2009.
  * [5] W.U. Bajwa, R. Calderbank, S. Jafarpour, Why Gabor frames? Two fundamental measures of coherence and their role in model selection, J. Commun. Netw. 12 (2010) 289–307.
  * [6] R. Baraniuk, M. Davenport, R.A. DeVore, M.B. Wakin, A simple proof of the restricted isometry property for random matrices, Constructive Approximation 28 (2008) 253–263.
  * [7] J.J. Benedetto, J.D. Kolesar, Geometric properties of Grassmannian frames for $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$, EURASIP J. on Appl. Signal Processing (2006) 17 pages.
  * [8] G. Bennett, Probability inequalities for the sum of independent random variables, J. Amer. Statist. Assoc. 57 (1962) 33–45.
  * [9] E.R. Berlekamp, The weight enumerators for certain subcodes of the second order binary Reed-Muller codes, Inform. Control 17 (1970) 485–500.
  * [10] E.J. Candès, Y. Eldar, D. Needell, P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal. 31 (2010) 59–73.
  * [11] E.J. Candès, Y. Plan, Near-ideal model selection by $\ell_{1}$ minimization, Ann. Statist. 37 (2009) 2145–2177.
  * [12] E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006) 489–509.
  * [13] E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005) 4203–4215.
  * [14] E.J. Candès, T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006) 5406–5425.
  * [15] B.G. Bodmann, P.G. Casazza, The road to equal-norm Parseval frames, J. Funct. Anal., 258 (2010), 397–420.
  * [16] P.G. Casazza, M. Fickus, Fourier transforms of finite chirps, EURASIP J. Appl. Signal Processing (2006) 7 pages.
  * [17] S.S. Chen, D.L. Donoho, M.A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Scientific Comput. 20 (1998) 33–61.
  * [18] J.H. Conway, R.H. Hardin, N.J.A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Experiment. Math. 5 (1996) 139–159.
  * [19] M.A. Davenport, P.T. Boufounos, M.B. Wakin, R.G. Baraniuk, Signal processing with compressive measurements, IEEE J. Select. Topics Signal Processing 4 (2010) 445–460.
  * [20] D.L. Donoho, M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell_{1}$ minimization, Proc. Natl. Acad. Sci. 100 (2003) 2197–2202.
  * [21] D.L. Donoho, M. Elad, V.N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory 52 (2006) 6–18.
  * [22] D.L. Donoho, J. Tanner, Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Phil. Trans. R. Soc. A 367 (2009) 4273–4293.
  * [23] M. Elad, A.M. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inform. Theory 48 (2002) 2558–2567.
  * [24] M. Fickus, D.G. Mixon, J.C. Tremain, Steiner equiangular tight frames, arXiv:1009.5730v1.
  * [25] R. Gribonval, M. Nielsen, Sparse representations in unions of bases, Technical Report 1499, Institut de Recherche en Informatique et Systèmes Aléatoires (2002) 15 pages.
  * [26] J. Haupt, W.U. Bajwa, G. Raz, R. Nowak, Toeplitz compressed sensing matrices with applications to sparse channel estimation, IEEE Trans. Inform. Theory 56 (2010) 5862–5875.
  * [27] J. Haupt, R. Nowak, Compressive sampling for signal detection, Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (2007) 1509–1512.
  * [28] A. Hayashi, T. Hashimoto, M. Horibe, Reexamination of optimal quantum state estimation of pure states, Phys. Rev. A 72 (2005) 5 pages.
  * [29] M.A. Herman, T. Strohmer, High-resolution radar via compressed sensing, IEEE Trans. Signal Processing 57 (2009) 2275–2284.
  * [30] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963) 13–30.
  * [31] R.B. Holmes, V.I. Paulsen, Optimal frames for erasures, Linear Algebra Appl. 377 (2004) 31–51.
  * [32] D. Hsu, S. Kakade, J. Langford, T. Zhang, Multi-label prediction via compressed sensing, Proc. Advances in Neural Information Processing Systems (2009) 772–780.
  * [33] S.M. Kay, Fundamentals of Statistical Signal Processing: Detection Theory, Upper Saddle River, Prentice Hall, 1998.
  * [34] B. Laurent, P. Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Statist. 28 (2000) 1302–1338.
  * [35] J. Lawrence, G.E. Pfander, D. Walnut, Linear independence of Gabor systems in finite dimensional vector spaces, J. Fourier Anal. Appl. 11 (2005) 715–726.
  * [36] Y. Mimura, A construction of spherical 2-designs, Graphs Combin. 6 (1990) 369–372.
  * [37] D.G. Mixon, C. Quinn, N. Kiyavash, M. Fickus, Equiangular tight frame fingerprinting codes, to appear in: Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (2011) 4 pages.
  * [38] K. Mukkavilli, A. Sabharwal, E. Erkip, B.A. Aazhang, On beam-forming with finite rate feedback in multiple antenna systems, IEEE Trans. Inform. Theory 49 (2003) 2562–2579.
  * [39] J. Nelson, V.N. Temlyakov, On the size of incoherent systems, J. Approx. Theory 163 (2011) 1238–1245.
  * [40] G.E. Pfander, H. Rauhut, J. Tanner, Identification of matrices having a sparse representation, IEEE Trans. Signal Processing 56 (2008) 5376–5388.
  * [41] M. Rudelson, R. Vershynin, Non-asymptotic theory of random matrices: Extreme singular values, Proc. Int. Congr. of Mathematicians (2010) 25 pages.
  * [42] M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math. 61 (2008) 1025–1045.
  * [43] A.J. Scott, M. Grassl, Symmetric informationally complete positive-operator-valued measures: A new computer study, J. Math. Phys. 51 (2010) 16 pages.
  * [44] J.J. Seidel, A survey of two-graphs, Proc. Intern. Coll. Teorie Combinatorie (1973) 481–511.
  * [45] J.J. Seidel, Strongly Regular Graphs with $(-1,1,0)$ Adjacency Matrix Having Eigenvalue 3, Linear Algebra Appl. 1 (1968) 281–298.
  * [46] T. Strohmer, R.W. Heath, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal. 14 (2003) 257–275.
  * [47] J.A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004) 2231–2242.
  * [48] J.A. Tropp, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006) 1030–1051.
  * [49] J.A. Tropp, Norms of random submatrices and sparse approximation, C. R. Acad. Sci. 346 (2008) 1271–1274.
  * [50] J.A. Tropp, On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal. 25 (2008) 1–24.
  * [51] J.H. van Lint, J.J. Seidel, Equilateral point sets in elliptic geometry, Indagationes Mathematicae 28 (1966) 335–348.
  * [52] M.J. Wainwright, Sharp thresholds for high-dimensional and noisy sparsity recovery using $\ell_{1}$-constrained quadratic programming (lasso), IEEE Trans. Inform. Theory 55 (2009) 2183–2202.
  * [53] P.J. Wolfe, M. Dörfler, S.J. Godsill, Multi-Gabor dictionaries for audio time-frequency analysis, Proc. IEEE Workshop Signal Process. Audio Acoust. (2001) 43–46.
  * [54] P. Xia, S. Zhou, G.B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory 51 (2005) 1900–1907.
  * [55] N.Y. Yu, G. Gong, A new binary sequence family with low correlation and large size, IEEE Trans. Inform. Theory 52 (2006) 1624–1636.
  * [56] R. Zahedi, A. Pezeshki, E.K.P. Chong, Robust measurement design for detecting sparse signals: Equiangular uniform tight frames and Grassmannian packings, American Control Conference (2010) 6 pages.