# The road to deterministic matrices with the restricted isometry property

Afonso S. Bandeira  Program in Applied and Computational Mathematics,
Princeton University, Princeton, New Jersey 08544, USA; E-mail:
<EMAIL_ADDRESS>,  Matthew Fickus  Department of Mathematics and
Statistics, Air Force Institute of Technology, Wright-Patterson Air Force
Base, OH 45433, USA<EMAIL_ADDRESS>,  Dustin G. Mixon  Program in
Applied and Computational Mathematics, Princeton University, Princeton, New
Jersey 08544, USA; E-mail<EMAIL_ADDRESS>and  Percy Wong  Program in
Applied and Computational Mathematics, Princeton University, Princeton, New
Jersey 08544, USA; E-mail<EMAIL_ADDRESS>
###### Abstract.

The restricted isometry property (RIP) is a well-known matrix condition that
provides state-of-the-art reconstruction guarantees for compressed sensing.
While random matrices are known to satisfy this property with high
probability, deterministic constructions have found less success. In this
paper, we consider various techniques for demonstrating RIP deterministically,
some popular and some novel, and we evaluate their performance. In evaluating
some techniques, we apply random matrix theory and inadvertently find a simple
alternative proof that certain random matrices are RIP. Later, we propose a
particular class of matrices as candidates for being RIP, namely, equiangular
tight frames (ETFs). Using the known correspondence between real ETFs and
strongly regular graphs, we investigate certain combinatorial implications of
a real ETF being RIP. Specifically, we give probabilistic intuition for a new
bound on the clique number of Paley graphs of prime order, and we conjecture
that the corresponding ETFs are RIP in a manner similar to random matrices.

###### Key words and phrases:

restricted isometry property, compressed sensing, equiangular tight frames

###### 2000 Mathematics Subject Classification:

Primary: 15A42. Secondary: 05E30, 15B52, 60F10, 94A12

The authors thank Prof. Peter Sarnak and Joel Moreira for insightful
discussions and helpful suggestions. ASB was supported by NSF Grant No.
DMS-0914892, MF was supported by NSF Grant No. DMS-1042701 and AFOSR Grant
Nos. F1ATA01103J001 and F1ATA00183G003, and DGM 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.

##  1\. Introduction

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

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

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

To get around the NP-hardness of sparse approximation, we need more structure
in the matrix $\Phi$. Instead of considering linear independence of all
subcollections of $2K$ columns, it has become common to impose a much stronger
requirement: that every submatrix of $2K$ columns of $\Phi$ be well-
conditioned. To be explicit, we have the following definition:

######  Definition 1.

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

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

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

In words, matrices which satisfy RIP act as a near-isometry on sufficiently
sparse vectors. Note that a $(2K,\delta)$-RIP matrix with $\delta<1$
necessarily has that all subcollections of $2K$ columns are linearly
independent. Also, the well-conditioning requirement of RIP forces
dissimilarity in the columns of $\Phi$ to provide stability in reconstruction.
Most importantly, the additional structure of RIP allows for the possibility
of getting around the NP-hardness of sparse approximation. Indeed, a
significant result in compressed sensing is that RIP sensing matrices enable
efficient reconstruction:

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

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

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

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

The fact that RIP sensing matrices convert an NP-hard reconstruction problem
into an $\ell_{1}$-minimization problem has prompted many in the community to
construct RIP matrices. Among these constructions, the most successful have
been random matrices, such as matrices with independent Gaussian or Bernoulli
entries [4], or matrices whose rows were randomly selected from the discrete
Fourier transform matrix [25]. With high probability, these random
constructions support sparsity levels $K$ on the order of
$\smash{\frac{M}{\log^{\alpha}N}}$ for some $\alpha\geq 1$. Intuitively, this
level of sparsity is near-optimal because $K$ cannot exceed
$\smash{\frac{M}{2}}$ by the linear independence condition. Unfortunately, it
is difficult to check whether a particular instance of a random matrix is
$(K,\delta)$-RIP, as this involves the calculation of singular values for all
$\smash{\binom{N}{K}}$ submatrices of $K$ columns of the matrix. For this
reason, and for the sake of reliable sensing standards, many have become
interested in finding deterministic RIP matrix constructions.

In the next section, we review the well-understood techniques that are
commonly used to analyze the restricted isometry of deterministic
constructions: the Gershgorin circle theorem, and the _spark_ of a matrix.
Unfortunately, neither technique demonstrates RIP for sparsity levels as large
as what random constructions are known to support; rather, with these
techniques, a deterministic $M\times N$ matrix $\Phi$ can only be shown to
have RIP for sparity levels on the order of $\sqrt{M}$. This limitation has
become known as the “square-root bottleneck,” and it poses an important
problem in matrix design [30].

To date, the only deterministic construction that manages to go beyond this
bottleneck is given by Bourgain et al. [7]; in Section 3, we discuss what they
call _flat RIP_ , which is the technique they use to demonstrate RIP. It is
important to stress the significance of their contribution: Before [7], it was
unclear how deterministic analysis might break the bottleneck, and as such,
their result is a major theoretical achievement. On the other hand, their
improvement over the square-root bottleneck is notably slight compared to what
random matrices provide. However, by our Theorem 14, their technique can
actually be used to demonstrate RIP for sparsity levels much larger than
$\sqrt{M}$, meaning one could very well demonstrate random-like performance
given the proper construction. Our result applies their technique to random
matrices, and it inadvertently serves as a simple alternative proof that
certain random matrices are RIP. In Section 4, we introduce an alternate
technique, which by our Theorem 17, can also demonstrate RIP for large
sparsity levels.

After considering the efficacy of these techniques to demonstrate RIP, it
remains to find a deterministic construction that is amenable to analysis. To
this end, we discuss various properties of a particularly nice matrix which
comes from _frame theory_ , called an _equiangular tight frame (ETF)_.
Specifically, real ETFs can be characterized in terms of their Gram matrices
using strongly regular graphs [32]. By applying the techniques of Sections 3
and 4 to real ETFs, we derive equivalent combinatorial statements in graph
theory. By focussing on the ETFs which correspond to Paley graphs of prime
order, we are able to make important statements about their clique numbers and
provide some intuition for an open problem in number theory. We conclude by
conjecturing that the Paley ETFs are RIP in a manner similar to random
matrices.

##  2\. Well-understood techniques

###  2.1. Applying Gershgorin’s circle thoerem

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

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

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

######  Theorem 3 (Gershgorin circle theorem [17]).

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

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

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

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

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

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

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

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

######  Theorem 4 (Welch bound [33]).

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

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

To use this result, we consider matrices whose worst-case coherence achieves
equality in the Welch bound. These are known as equiangular tight frames [29],
which can be defined as follows:

######  Definition 5.

A matrix is said to be an _equiangular tight frame (ETF)_ if

  * (i)

the columns have unit norm,

  * (ii)

the rows are orthogonal with equal norm, and

  * (iii)

the inner products between distinct columns are equal in modulus.

To date, there are three general constructions that build several families of
ETFs [16, 32, 34]. Since ETFs achieve equality in the Welch bound, we can
further analyze what it means for an $M\times N$ ETF $\Phi$ to be
$(K,(K-1)\mu)$-RIP. In particular, since Theorem 2 requires that $\Phi$ be
$(2K,\delta)$-RIP for $\delta<\sqrt{2}-1$, it suffices to have
$\smash{\frac{2K}{\sqrt{M}}<\sqrt{2}-1}$, since this implies

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

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

###  2.2. Spark considerations

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

######  Definition 6.

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

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

This definition was introduced by Dohono and Elad [15] to help build a theory
of sparse representation that later gave birth to modern compressed sensing.
The concept of spark is also found in matroid theory, where it goes by the
name _girth_ [1]. The condition that every subcollection of $2K$ columns of
$\Phi$ is linearly independent is equivalent to $\mathrm{Spark}(\Phi)>2K$.
Relating spark to RIP, suppose $\Phi$ is $(K,\delta)$-RIP with
$\mathrm{Spark}(\Phi)\leq K$. Then there exists a nonzero $K$-sparse vector
$x$ such that

$(1-\delta)\|x\|^{2}\leq\|\Phi x\|^{2}=0,$

and so $\delta\geq 1$. The reason behind this stems from our necessary linear
independence condition: RIP implies linear independence, and so small spark
implies linear dependence, which in turn implies not RIP.

As an example of using spark to analyze RIP, we now consider a construction
that dates back to Seidel [27], and was recently developed further in [16].
Here, a special type of block design is used to build an ETF. Let’s start with
a definition:

######  Definition 7.

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[i,j]$,
where $A[i,j]=1$ if the $i$th block contains the $j$th element, and otherwise
$A[i,j]=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 to construct
ETFs using Steiner systems.

######  Theorem 8 (Theorem 1 in [16]).

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 $\Phi$ according the following procedure:

  * (i)

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

  * (ii)

Let $H$ be a $(1+\frac{v-1}{k-1})\times(1+\frac{v-1}{k-1})$ (possibly complex)
Hadamard matrix.

  * (iii)

For each $j=1,\ldots,v$, let $\Phi_{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.

  * (iv)

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

As an example, we build an ETF from a (2,2,4)-Steiner system. In this case, we
make use of the corresponding incidence matrix $A$ along with a $4\times 4$
Hadamard matrix $H$:

$A=\left[\begin{array}[]{cccc}+&+&&\\\ +&&+&\\\ +&&&+\\\ &+&+&\\\ &+&&+\\\
&&+&+\end{array}\right],\qquad H=\left[\begin{array}[]{cccc}+&+&+&+\\\
+&-&+&-\\\ +&+&-&-\\\ +&-&-&+\end{array}\right].$

In both of these matrices, pluses represent $1$’s, minuses represent $-1$’s,
and blank spaces represent $0$’s. For the matrix $A$, 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 $6\times 16$
ETF $\Phi$, we replace the three ones in each column of $A$ with the second,
third, and fourth rows of $H$. Normalizing the columns gives the following
$6\times 16$ ETF:

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

It is easy to verify that $\Phi$ satisfies Definition 5. Several infinite
families of $(2,k,v)$-Steiner systems are already known, and Theorem 8 says
that each one can be used to build a different ETF. Recall from the previous
subsection that Steiner ETFs, being ETFs, are optimal constructions in terms
of the Gershgorin demonstration of RIP. We now use the notion of spark to
further analyze Steiner ETFs. Specifically, note that the first four columns
in (5) are linearly dependent. As such, $\mathrm{Spark}(\Phi)\leq 4$. In
general, the spark of a Steiner ETF is
$\smash{\leq\frac{v-1}{k-1}\leq\sqrt{2M}}$ (see Theorem 3 of [16] and
discussion thereafter), and so having $K$ on the order of $\sqrt{M}$ is
_necessary_ for a Steiner ETF to be $(K,\delta)$-RIP for some $\delta<1$. This
answers the closing question of the previous subsection: in general, ETFs are
not RIP for sparsity levels larger than the order of $\sqrt{M}$. This
contrasts with random constructions, which support sparsity levels as large as
the order of $\smash{\frac{M}{\log^{\alpha}N}}$ for some $\alpha\geq 1$. That
said, are there techniques to demonstrate that certain deterministic matrices
are RIP for sparsity levels larger than the order of $\sqrt{M}$?

##  3\. Flat restricted orthogonality

In [7], Bourgain et al. provided a deterministic construction of $M\times N$
RIP matrices that support sparsity levels $K$ on the order of
$M^{1/2+\varepsilon}$ for some small value of $\varepsilon$. To date, this is
the only known deterministic RIP construction that breaks the so-called
“square-root bottleneck.” In this section, we analyze their technique for
demonstrating RIP, but first, we provide some historical context. We begin
with a definition:

######  Definition 9.

The matrix $\Phi$ has _$(K,\theta)$ -restricted orthogonality (RO)_ if

$|\langle\Phi x,\Phi y\rangle|\leq\theta\|x\|\|y\|$

for every pair of $K$-sparse vectors $x,y$ with disjoint support. The smallest
$\theta$ for which $\Phi$ has $(K,\theta)$-RO is the _restricted orthogonality
constant (ROC)_ $\theta_{K}$.

In the past, restricted orthogonality was studied to produce reconstruction
performance guarantees for both $\ell_{1}$-minimization and the Dantzig
selector [9, 10]. Intuitively, restricted orthogonality is important to
compressed sensing because any stable inversion process for (1) would require
$\Phi$ to map vectors of disjoint support to particularly dissimilar
measurements. For the present paper, we are interested in upper bounds on
RICs; in this spirit, the following result illustrates some sort of
equivalence between RICs and ROCs:

######  Lemma 10 (Lemma 1.2 in [9]).

$\theta_{K}\leq\delta_{2K}\leq\theta_{K}+\delta_{K}$.

To be fair, the above upper bound on $\delta_{2K}$ does not immediately help
in estimating $\delta_{2K}$, as it requires one to estimate $\delta_{K}$.
Certainly, we may iteratively apply this bound to get

$\delta_{2K}\leq\theta_{K}+\theta_{\lceil K/2\rceil}+\theta_{\lceil
K/4\rceil}+\cdots+\theta_{1}+\delta_{1}\leq(1+\lceil\log_{2}K\rceil)\theta_{K}+\delta_{1}.$
(6)

Note that $\delta_{1}$ is particularly easy to calculate:

$\delta_{1}=\max_{n\in\\{1,\ldots,N\\}}\Big{|}\|\varphi_{n}\|^{2}-1\Big{|},$

which is zero when the columns of $\Phi$ have unit norm. In pursuit of a
better upper bound on $\delta_{2K}$, we use techniques from [7] to remove the
log factor from (6):

######  Lemma 11.

$\delta_{2K}\leq 2\theta_{K}+\delta_{1}$.

###### Proof.

Given a matrix $\Phi=[\varphi_{1}\cdots\varphi_{N}]$, we want to upper-bound
the smallest $\delta$ for which $(1-\delta)\|x\|^{2}\leq\|\Phi
x\|^{2}\leq(1+\delta)\|x\|^{2}$, or equivalently:

$\delta\geq\Big{|}\|\Phi\tfrac{x}{\|x\|}\|^{2}-1\Big{|}$ (7)

for every nonzero $2K$-sparse vector $x$. We observe from (7) that we may take
$x$ to have unit norm without loss of generality. Letting $\mathcal{K}$ denote
a size-$2K$ set that contains the support of $x$, and letting
$\\{x_{k}\\}_{k\in\mathcal{K}}$ denote the corresponding entries of $x$, the
triangle inequality gives

$\displaystyle\Big{|}\|\Phi x\|^{2}-1\Big{|}$
$\displaystyle=\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{K}}x_{i}\varphi_{i},\sum_{j\in\mathcal{K}}x_{j}\varphi_{j}\bigg{\rangle}-1\bigg{|}$
$\displaystyle=\bigg{|}\sum_{i\in\mathcal{K}}\sum_{\begin{subarray}{c}j\in\mathcal{K}\\\
j\neq i\end{subarray}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle+\sum_{i\in\mathcal{K}}\|x_{i}\varphi_{i}\|^{2}-1\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{i\in\mathcal{K}}\sum_{\begin{subarray}{c}j\in\mathcal{K}\\\
j\neq i\end{subarray}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle\bigg{|}+\bigg{|}\sum_{i\in\mathcal{K}}\|x_{i}\varphi_{i}\|^{2}-1\bigg{|}.$
(8)

Since $\sum_{i\in\mathcal{K}}|x_{i}|^{2}=1$, the second term of (8) satisfies

$\bigg{|}\sum_{i\in\mathcal{K}}\|x_{i}\varphi_{i}\|^{2}-1\bigg{|}\leq\sum_{i\in\mathcal{K}}|x_{i}|^{2}\Big{|}\|\varphi_{i}\|^{2}-1\Big{|}\leq\sum_{i\in\mathcal{K}}|x_{i}|^{2}\delta_{1}=\delta_{1},$
(9)

and so it remains to bound the first term of (8). To this end, we note that
for each $i,j\in\mathcal{K}$ with $j\neq i$, the term $\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle$ appears in

$\sum_{\begin{subarray}{c}\mathcal{I}\subseteq\mathcal{K}\\\
|\mathcal{I}|=K\end{subarray}}\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{K}\setminus\mathcal{I}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle$

as many times as there are size-$K$ subsets of $\mathcal{K}$ which contain $i$
but not $j$, i.e., $\binom{2K-2}{K-1}$ times. Thus, we use the triangle
inequality and the definition of restricted orthogonality to get

$\displaystyle\bigg{|}\sum_{i\in\mathcal{K}}\sum_{\begin{subarray}{c}j\in\mathcal{K}\\\
j\neq i\end{subarray}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle\bigg{|}$
$\displaystyle=\bigg{|}\frac{1}{\binom{2K-2}{K-1}}\sum_{\begin{subarray}{c}\mathcal{I}\subseteq\mathcal{K}\\\
|\mathcal{I}|=K\end{subarray}}\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{K}\setminus\mathcal{I}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle\bigg{|}$
$\displaystyle\leq\frac{1}{\binom{2K-2}{K-1}}\sum_{\begin{subarray}{c}\mathcal{I}\subseteq\mathcal{K}\\\
|\mathcal{I}|=K\end{subarray}}\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{K}\setminus\mathcal{I}}x_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\frac{1}{\binom{2K-2}{K-1}}\sum_{\begin{subarray}{c}\mathcal{I}\subseteq\mathcal{K}\\\
|\mathcal{I}|=K\end{subarray}}\theta_{K}\bigg{(}\sum_{i\in\mathcal{I}}|x_{i}|^{2}\bigg{)}^{1/2}\bigg{(}\sum_{j\in\mathcal{K}\setminus\mathcal{I}}|x_{j}|^{2}\bigg{)}^{1/2}.$

At this point, $x$ having unit norm implies
$(\sum_{i\in\mathcal{I}}|x_{i}|^{2})^{1/2}(\sum_{j\in\mathcal{K}\setminus\mathcal{I}}|x_{j}|^{2})^{1/2}\leq\frac{1}{2}$,
and so

$\bigg{|}\sum_{i\in\mathcal{K}}\sum_{\begin{subarray}{c}j\in\mathcal{K}\\\
j\neq i\end{subarray}}\langle
x_{i}\varphi_{i},x_{j}\varphi_{j}\rangle\bigg{|}\leq\frac{1}{\binom{2K-2}{K-1}}\sum_{\begin{subarray}{c}\mathcal{I}\subseteq\mathcal{K}\\\
|\mathcal{I}|=K\end{subarray}}\frac{\theta_{K}}{2}=\frac{\binom{2K}{K}}{\binom{2K-2}{K-1}}\frac{\theta_{K}}{2}=\bigg{(}4-\frac{2}{K}\bigg{)}\frac{\theta_{K}}{2}.$

Applying both this and (9) to (8) gives the result. ∎

Having discussed the relationship between restricted isometry and restricted
orthogonality, we are now ready to introduce the property used in [7] to
demonstrate RIP:

######  Definition 12.

The matrix $\Phi=[\varphi_{1}\cdots\varphi_{N}]$ has _$(K,\hat{\theta})$ -flat
restricted orthogonality_ if

$\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}\leq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$

for every disjoint pair of subsets
$\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}|,|\mathcal{J}|\leq K$.

Note that $\Phi$ has $(K,\theta_{K})$-flat restricted orthogonality (FRO) by
taking $x$ and $y$ in Definition 9 to be the characteristic functions
$\chi_{\mathcal{I}}$ and $\chi_{\mathcal{J}}$, respectively. Also to be clear,
_flat restricted orthogonality_ is called _flat RIP_ in [7]; we feel the name
change is appropriate considering the preceeding literature. Moreover, the
definition of flat RIP in [7] required $\Phi$ to have unit-norm columns,
whereas we strengthen the corresponding results so as to make no such
requirement. Interestingly, FRO bears some resemblence to the cut-norm of the
Gram matrix $\Phi^{*}\Phi$, defined as the maximum value of
$|\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}\langle\varphi_{i},\varphi_{j}\rangle|$
over _all_ subsets $\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$; the
cut-norm has received some attention recently for the hardness of its
approximation [2]. The following theorem illustrates the utility of flat
restricted orthogonality as an estimate of the RIC:

######  Theorem 13.

A matrix with $(K,\hat{\theta})$-flat restricted orthogonality has a
restricted orthogonality constant $\theta_{K}$ which is $\leq
C\hat{\theta}\log K$, and we may take $C=75$.

Indeed, when combined with Lemma 11, this result gives an upper bound on the
RIC: $\delta_{2K}\leq 2C\hat{\theta}\log K+\delta_{1}$. The noteworthy benefit
of this upper bound is that the problem of estimating singular values of
submatrices is reduced to a combinatorial problem of bounding the coherence of
disjoint sums of columns. Furthermore, this reduction comes at the price of a
mere log factor in the estimate. In [7], Bourgain et al. managed to satisfy
this combinatorial coherence property using techniques from additive
combinatorics. While we will not discuss their construction, we find the proof
of Theorem 13 to be instructive; our proof is valid for all values of $K$ (as
opposed to sufficiently large $K$ in the original [7]), and it has near-
optimal constants where appropriate. The proof can be found in the Appendix.

To reiterate, Bourgain et al. [7] used flat restricted orthogonality to build
the only known deterministic construction of $M\times N$ RIP matrices that
support sparsity levels $K$ on the order of $M^{1/2+\varepsilon}$ for some
small value of $\varepsilon$. We are particularly interested in the efficacy
of FRO as a technique to demonstrate RIP in general. Certainly, [7] shows that
FRO can produce at least an $\varepsilon$ improvement over the Gershgorin
technique discussed in the previous section, but it remains to be seen whether
FRO can do better.

In the remainder of this section, we will show that flat restricted
orthogonality is actually capable of demonstrating RIP with much higher
sparsity levels than indicated by [7]. Hopefully, this realization will spur
further research in deterministic constructions which satisfy FRO. To evaluate
FRO, we investigate how well it performs with random matrices; in doing so, we
give an alternative proof that certain random matrices satisfy RIP with high
probability:

######  Theorem 14.

Construct an $M\times N$ matrix $\Phi$ by drawing each of its entries
independently from a Gaussian distribution with mean zero and variance
$\frac{1}{M}$, take $C$ to be the constant from Theorem 13, and set
$\alpha=0.01$. Then $\Phi$ has $(K,\frac{(1-\alpha)\delta}{2C\log K})$-flat
restricted orthogonality and $\delta_{1}\leq\alpha\delta$, and therefore the
$(2K,\delta)$-restricted isometry property, with high probability provided
$M\geq\frac{33C^{2}}{\delta^{2}}K\log^{2}K\log N$.

In proving this result, we will make use of the following Bernstein
inequality:

######  Theorem 15 (see [5, 35]).

Let $\\{Z_{m}\\}_{m=1}^{M}$ be independent random variables of mean zero with
bounded moments, and suppose there exists $L>0$ such that

$\mathbb{E}|Z_{m}|^{k}\leq\frac{\mathbb{E}|Z_{m}|^{2}}{2}L^{k-2}k!$ (10)

for every $k\geq 2$. Then

$\mathrm{Pr}\bigg{[}\sum_{m=1}^{M}Z_{m}\geq
2t\bigg{(}\sum_{m=1}^{M}\mathbb{E}|Z_{m}|^{2}\bigg{)}^{1/2}\bigg{]}\leq
e^{-t^{2}}$ (11)

provided
$\displaystyle{t\leq\frac{1}{2L}\bigg{(}\sum_{m=1}^{M}\mathbb{E}|Z_{m}|^{2}\bigg{)}^{1/2}}$.

###### Proof of Theorem 14.

Considering Lemma 11, it suffices to show that $\Phi$ has restricted
orthogonality and that $\delta_{1}$ is sufficiently small. First, to
demonstrate restricted orthogonality, it suffices to demonstrate FRO by
Theorem 13, and so we will ensure that the following quantity is small:

$\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}=\sum_{m=1}^{M}\bigg{(}\sum_{i\in\mathcal{I}}\varphi_{i}[m]\bigg{)}\bigg{(}\sum_{j\in\mathcal{J}}\varphi_{j}[m]\bigg{)}.$
(12)

Notice that $X_{m}:=\sum_{i\in\mathcal{I}}\varphi_{i}[m]$ and
$Y_{m}:=\sum_{j\in\mathcal{J}}\varphi_{j}[m]$ are mutually independent over
all $m=1,\ldots,M$ since $\mathcal{I}$ and $\mathcal{J}$ are disjoint. Also,
$X_{m}$ is Gaussian with mean zero and variance $\frac{|\mathcal{I}|}{M}$,
while $Y_{m}$ similarly has mean zero and variance $\frac{|\mathcal{J}|}{M}$.
Viewed this way, (12) being small corresponds to the sum of independent random
variables $Z_{m}:=X_{m}Y_{m}$ having its probability measure concentrated at
zero. To this end, Theorem 15 is naturally applicable, as the absolute central
moments of a Gaussian random variable $X$ with mean zero and variance
$\sigma^{2}$ are well known:

$\mathbb{E}|X|^{k}=\left\\{\begin{array}[]{rl}\sqrt{\frac{2}{\pi}}\sigma^{k}(k-1)!!&\mbox{
if $k$ odd},\\\ \sigma^{k}(k-1)!!&\mbox{ if $k$ even}.\end{array}\right.$

Since $Z_{m}=X_{m}Y_{m}$ is a product of independent Gaussian random
variables, this gives

$\mathbb{E}|Z_{m}|^{k}=\mathbb{E}|X_{m}|^{k}~{}\mathbb{E}|Y_{m}|^{k}\leq\Big{(}\frac{|\mathcal{I}|}{M}\Big{)}^{k/2}\Big{(}\frac{|\mathcal{J}|}{M}\Big{)}^{k/2}\Big{(}(k-1)!!\Big{)}^{2}\leq\bigg{(}\frac{(|\mathcal{I}||\mathcal{J}|)^{1/2}}{M}\bigg{)}^{k}k!.$

Further since
$\mathbb{E}|Z_{m}|^{2}=\frac{|\mathcal{I}||\mathcal{J}|}{M^{2}}$, we may
define $L:=2\frac{(|\mathcal{I}||\mathcal{J}|)^{1/2}}{M}$ to get (10). Later,
we will take $\hat{\theta}<\delta<\sqrt{2}-1<\frac{1}{2}$. Considering

$t:=\frac{\hat{\theta}\sqrt{M}}{2}<\frac{\sqrt{M}}{4}=\frac{1}{2L}\Big{(}M\frac{|\mathcal{I}||\mathcal{J}|}{M^{2}}\Big{)}^{1/2}=\frac{1}{2L}\bigg{(}\sum_{m=1}^{M}\mathbb{E}|Z_{m}|^{2}\bigg{)}^{1/2},$

we therefore have (11), which in this case has the form

$\mathrm{Pr}\Bigg{[}\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}\geq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}\Bigg{]}\leq
2e^{-M\hat{\theta}^{2}/4},$

where the probability is doubled due to the symmetric distribution of
$\sum_{m=1}^{M}Z_{m}$. Since we need to account for all possible choices of
$\mathcal{I}$ and $\mathcal{J}$, we will perform a union bound. The total
number of choices is given by

$\sum_{|\mathcal{I}|=1}^{K}\sum_{|\mathcal{J}|=1}^{K}\binom{N}{|\mathcal{I}|}\binom{N-|\mathcal{I}|}{|\mathcal{J}|}\leq
K^{2}\binom{N}{K}^{2}\leq N^{2K},$

and so the union bound gives

$\mathrm{Pr}\Big{[}\mbox{$\Phi$ does not have
$(K,\hat{\theta})$-FRO}\Big{]}\leq
2e^{-M\hat{\theta}^{2}/4}~{}N^{2K}=2\exp\Big{(}-\frac{M\hat{\theta}^{2}}{4}+2K\log
N\Big{)}.$ (13)

Thus, Gaussian matrices tend to have FRO, and hence restricted orthogonality
by Theorem 13; this is made more precise below.

Again by Lemma 11, it remains to show that $\delta_{1}$ is sufficiently small.
To this end, we note that $M\|\varphi_{n}\|^{2}$ has chi-squared distribution
with $M$ degrees of freedom, and so we can use another (simpler)
concentration-of-measure result; see Lemma 1 of [20]:

$\mathrm{Pr}\bigg{[}\Big{|}\|\varphi_{n}\|^{2}-1\Big{|}\geq
2\Big{(}\sqrt{\frac{t}{M}}+\frac{t}{M}\Big{)}\bigg{]}\leq 2e^{-t}$

for any $t>0$. Specifically, we pick

$\delta^{\prime}:=2\Big{(}\sqrt{\frac{t}{M}}+\frac{t}{M}\Big{)}\leq\frac{4t}{M},$

and we perform a union bound over the $N$ choices for $\varphi_{n}$:

$\mathrm{Pr}\Big{[}\delta_{1}>\delta^{\prime}\Big{]}\leq
2\exp\Big{(}-\frac{M\delta^{\prime}}{4}+\log N\Big{)}.$ (14)

To summarize, Lemma 11, the union bound, Theorem 13, and (13) and (14) give

$\displaystyle\mathrm{Pr}\Big{[}\delta_{2K}>\delta\Big{]}$
$\displaystyle\leq\mathrm{Pr}\Big{[}\theta_{K}>\frac{(1-\alpha)\delta}{2}\mbox{
or }\delta_{1}>\alpha\delta\Big{]}$
$\displaystyle\leq\mathrm{Pr}\Big{[}\theta_{K}>\frac{(1-\alpha)\delta}{2}\Big{]}+\mathrm{Pr}\Big{[}\delta_{1}>\alpha\delta\Big{]}$
$\displaystyle\leq\mathrm{Pr}\Big{[}\mbox{$\Phi$ does not have
$\displaystyle{\Big{(}K,\frac{(1-\alpha)\delta}{2C\log
K}\Big{)}}$-FRO}\Big{]}+\mathrm{Pr}\Big{[}\delta_{1}>\alpha\delta\Big{]}$
$\displaystyle\leq
2\exp\Big{(}-\frac{M}{4}\Big{(}\frac{(1-\alpha)\delta}{2C\log
K}\Big{)}^{2}+2K\log N\Big{)}+2\exp\Big{(}-\frac{M\alpha\delta}{4}+\log
N\Big{)},$

and so $M\geq\frac{33C^{2}}{\delta^{2}}K\log^{2}K\log N$ gives that $\Phi$ has
$(2K,\delta)$-RIP with high probability. ∎

We note that a version of Theorem 14 also holds for matrices whose entries are
independent Bernoulli random variables taking values $\pm\frac{1}{\sqrt{M}}$
with equal probability. In this case, one can again apply Theorem 15 by
comparing moments with those of the Gaussian distribution; also, a union bound
with $\delta_{1}$ will not be necessary since the columns have unit norm,
meaning $\delta_{1}=0$.

##  4\. Restricted isometry by the power method

In the previous section, we established the efficacy of flat restricted
orthogonality as a technique to demonstrate RIP. While flat restricted
orthogonality has proven useful in the past [7], future deterministic RIP
constructions might not use this technique. Indeed, it would be helpful to
have other techniques available that demonstrate RIP beyond the square-root
bottleneck. In pursuit of such techniques, we recall that the smallest
$\delta$ for which $\Phi$ is $(K,\delta)$-RIP is given in terms of operator
norms in (2). In addition, we notice that for any self-adjoint matrix $A$,

$\|A\|_{2}=\|\lambda(A)\|_{\infty}\leq\|\lambda(A)\|_{p},$

where $\lambda(A)$ denotes the spectrum of $A$ with multiplicities. Let
$A=UDU^{*}$ be the eigenvalue decomposition of $A$. When $p$ is even, we can
express $\|\lambda(A)\|_{p}$ in terms of an easy-to-calculate trace:

$\|\lambda(A)\|_{p}^{p}=\mathrm{Tr}[D^{p}]=\mathrm{Tr}[(UDU^{*})^{p}]=\mathrm{Tr}[A^{p}].$

Combining these ideas with the fact that
$\|\cdot\|_{p}\rightarrow\|\cdot\|_{\infty}$ pointwise leads to the following:

######  Theorem 16.

Given an $M\times N$ matrix $\Phi$, define

$\delta_{K;q}:=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]^{\frac{1}{2q}}.$

Then $\Phi$ has the $(K,\delta_{K;q})$-restricted isometry property for every
$q\geq 1$. Moreover, the restricted isometry constant of $\Phi$ is approached
by these estimates: $\lim_{q\rightarrow\infty}\delta_{K;q}=\delta_{K}$.

Similar to flat restricted orthogonality, this _power method_ has a
combinatorial aspect that prompts one to check every sub-Gram matrix of size
$K$; one could argue that the power method is slightly _less_ combinatorial,
as flat restricted orthogonality is a statement about all pairs of disjoint
subsets of size $\leq K$. Regardless, the work of Bourgain et al. [7]
illustrates that combinatorial properties can be useful, and there may exist
constructions to which the power method would be naturally applied. Moreover,
we note that since $\delta_{K;q}$ approaches $\delta_{K}$, a sufficiently
large choice of $q$ should deliver better-than-$\varepsilon$ improvement over
the Gershgorin analysis. How large should $q$ be? If we assume $\Phi$ has
unit-norm columns, taking $q=1$ gives

$\delta_{K;1}^{2}=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2}]=\max_{\begin{subarray}{c}\mathcal{K}\subseteq\\{1,\ldots,N\\}\\\
|\mathcal{K}|=K\end{subarray}}\sum_{i\in\mathcal{K}}\sum_{\begin{subarray}{c}j\in\mathcal{K}\\\
j\neq i\end{subarray}}|\langle\varphi_{i},\varphi_{j}\rangle|^{2}\leq
K(K-1)\mu^{2},$ (15)

where $\mu$ is the worst-case coherence of $\Phi$. Equality is achieved above
whenever $\Phi$ is an ETF, in which case (15) along with reasoning similar to
(4) demonstrates that $\Phi$ is RIP with sparsity levels on the order of
$\sqrt{M}$, as the Gershgorin analysis established. It remains to be shown how
$\delta_{K;2}$ compares. To make this comparison, we apply the power method to
random matrices:

######  Theorem 17.

Construct an $M\times N$ matrix $\Phi$ by drawing each of its entries
independently from a Gaussian distribution with mean zero and variance
$\frac{1}{M}$, and take $\delta_{K;q}$ to be as defined in Theorem 16. Then
$\delta_{K;q}\leq\delta$, and therefore $\Phi$ has the $(K,\delta)$-restricted
isometry property, with high probability provided
$M\geq\frac{81}{\delta^{2}}K^{1+1/q}\log\frac{eN}{K}$.

While flat restricted orthogonality comes with a negligible penalty of
$\log^{2}K$ in the number of measurements, the power method has a penalty of
$K^{1/q}$. As such, the case $q=1$ uses the order of $K^{2}$ measurements,
which matches our calculation in (15). Moreover, the power method with $q=2$
can demonstrate RIP with $K^{3/2}$ measurements, i.e., $K\sim M^{1/2+1/6}$,
which is considerably better than an $\varepsilon$ improvement over the
Gershgorin technique.

###### Proof of Theorem 17.

Take $t:=\frac{\delta}{3K^{1/2q}}-(\frac{K}{M})^{1/2}$ and pick
$\mathcal{K}\subseteq\\{1,\ldots,N\\}$. Then Theorem II.13 of [13] states

$\mathrm{Pr}\bigg{[}1-\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\leq\sigma_{\min}(\Phi_{\mathcal{K}})\leq\sigma_{\max}(\Phi_{\mathcal{K}})\leq
1+\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\bigg{]}\geq 1-2e^{-Mt^{2}/2}.$

Continuing, we use the fact that
$\lambda(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})=\sigma(\Phi_{\mathcal{K}})^{2}$
to get

$\displaystyle 1-2e^{-Mt^{2}/2}$
$\displaystyle\leq\mathrm{Pr}\bigg{[}\bigg{(}1-\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\bigg{)}^{2}\leq\lambda_{\min}(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})\leq\lambda_{\max}(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})\leq\bigg{(}1+\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\bigg{)}^{2}\bigg{]}$
$\displaystyle\leq\mathrm{Pr}\bigg{[}1-3\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\leq\lambda_{\min}(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})\leq\lambda_{\max}(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})\leq
1+3\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\bigg{]},$ (16)

where the last inequality follows from the fact that
$(\frac{K}{M})^{1/2}+t<1$. Since $\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$
and $\mathrm{I}_{K}$ are simultaneously diagonalizable, the spectrum of
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K}$ is given by
$\lambda(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})=\lambda(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})-1$.
Combining this with (16) then gives

$\mathrm{Pr}\bigg{[}\Big{\|}\lambda(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})\Big{\|}_{\infty}\leq
3\bigg{(}\sqrt{\frac{K}{M}}+t\bigg{)}\bigg{]}\geq 1-2e^{-Mt^{2}/2}.$

Considering $\mathrm{Tr}[A^{2q}]^{\frac{1}{2q}}=\|\lambda(A)\|_{2q}\leq
K^{\frac{1}{2q}}\|\lambda(A)\|_{\infty}$, we continue:

$\mathrm{Pr}\bigg{[}\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]^{\frac{1}{2q}}\leq\delta\bigg{]}\geq\mathrm{Pr}\bigg{[}K^{\frac{1}{2q}}\Big{\|}\lambda(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})\Big{\|}_{\infty}\leq\delta\bigg{]}\geq
1-2e^{-Mt^{2}/2}.$

From here, we perform a union bound over all possible choices of
$\mathcal{K}$:

$\displaystyle\mathrm{Pr}\bigg{[}\exists\mathcal{K}\mbox{ s.t.
}\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]^{\frac{1}{2q}}>\delta\bigg{]}$
$\displaystyle\leq\binom{N}{K}\mathrm{Pr}\bigg{[}\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]^{\frac{1}{2q}}>\delta\bigg{]}$
$\displaystyle\leq 2\exp\Big{(}-\frac{Mt^{2}}{2}+K\log\frac{eN}{K}\Big{)}.$
(17)

Rearranging $M\geq\frac{81}{\delta^{2}}K^{1+1/q}\log\frac{eN}{K}$ gives
$K^{1/2}\leq\frac{\delta M^{1/2}}{9K^{1/2q}\log^{1/2}(eN/K)}\leq\frac{\delta
M^{1/2}}{9K^{1/2q}}$, and so

$\frac{Mt^{2}}{2}=\frac{1}{2}\bigg{(}\frac{\delta
M^{1/2}}{3K^{1/2q}}-K^{1/2}\bigg{)}^{2}\geq\frac{1}{2}\bigg{(}\frac{2\delta
M^{1/2}}{9K^{1/2q}}\bigg{)}^{2}\geq 2K\log\frac{eN}{K}.$ (18)

Combining (17) and (18) gives the result. ∎

##  5\. Equiangular tight frames as RIP candidates

In Section 2, we observed that equiangular tight frames (ETFs) are optimal RIP
matrices under the Gershgorin analysis. In the present section, we reexamine
ETFs as prospective RIP matrices. Specifically, we consider the possibility
that certain classes of $M\times N$ ETFs support sparsity levels $K$ larger
than the order of $\sqrt{M}$. Before analyzing RIP, let’s first observe some
important features of ETFs. Recall that Definition 5 characterized ETFs in
terms of their rows and columns. Interestingly, _real_ ETFs have a natural
alternative characterization.

Let $\Phi$ be a real $M\times N$ ETF, and consider the corresponding Gram
matrix $\Phi^{*}\Phi$. Observing Definition 5, we have from (i) that the
diagonal entries of $\Phi^{*}\Phi$ are 1’s. Also, (iii) indicates that the
off-diagonal entries are equal in absolute value (to the Welch bound); since
$\Phi$ has real entries, the phase of each off-diagonal entry of
$\Phi^{*}\Phi$ is either positive or negative. Letting $\mu$ denote the
absolute value of the off-diagonal entries, we can decompose the Gram matrix
as $\Phi^{*}\Phi=\mathrm{I}_{N}+\mu S$, where $S$ is a matrix of zeros on the
diagonal and $\pm 1$’s on the off-diagonal. Here, $S$ is referred to as a
_Seidel adjacency matrix_ , as $S$ encodes the adjacency rule of a simple
graph with $i\leftrightarrow j$ whenever $S[i,j]=-1$; this correspondence
originated in [31].

There is an important equivalence class amongst ETFs: given an ETF $\Phi$, one
can negate any of the columns to form another ETF $\Phi^{\prime}$. Indeed, the
ETF properties in Definition 5 are easily verified to hold for this new
matrix. For obvious reasons, $\Phi$ and $\Phi^{\prime}$ are called _flipping
equivalent_. This equivalence plays a key role in the following result, which
characterizes real ETFs in terms of a particular class of strongly regular
graphs:

######  Definition 18.

We say a simple graph $G$ is _strongly regular_ of the form
$\mathrm{srg}(v,k,\lambda,\mu)$ if

  * (i)

$G$ has $v$ vertices,

  * (ii)

every vertex has $k$ neighbors (i.e., $G$ is $k$_-regular_),

  * (iii)

every two adjacent vertices have $\lambda$ common neighbors, and

  * (iv)

every two non-adjacent vertices have $\mu$ common neighbors.

######  Theorem 19 (Corollary 5.6 in [32]).

Every real $M\times N$ equiangular tight frame with $N>M+1$ is flipping
equivalent to a frame whose Seidel adjacency matrix corresponds to the join of
a vertex with a strongly regular graph of the form

$\mathrm{srg}\bigg{(}N-1,L,\frac{3L-N}{2},\frac{L}{2}\bigg{)},\qquad
L:=\frac{N}{2}-1+\bigg{(}1-\frac{N}{2M}\bigg{)}\sqrt{\frac{M(N-1)}{N-M}}.$

Conversely, every such graph corresponds to flipping equivalence classes of
equiangular tight frames in the same manner.

The previous two sections illustrated the main issue with the Gershgorin
analysis: it ignores important cancellations in the sub-Gram matrices. We
suspect that such cancellations would be more easily observed in a real ETF,
since Theorem 19 neatly represents the Gram matrix’s off-diagonal oscillations
in terms of adjacencies in a strongly regular graph. The following result
gives a taste of how useful this graph representation can be:

######  Theorem 20.

Take a real equiangular tight frame $\Phi$ with worst-case coherence $\mu$,
and let $G$ denote the corresponding strongly regular graph in Theorem 19.
Then the restricted isometry constant of $\Phi$ is given by
$\delta_{K}=(K-1)\mu$ for every $K\leq\omega(G)+1$, where $\omega(G)$ denotes
the size of the largest clique in $G$.

###### Proof.

The Gershgorin analysis (3) gives the bound $\delta_{K}\leq(K-1)\mu$, and so
it suffices to prove $\delta_{K}\geq(K-1)\mu$. Since $K\leq\omega(G)+1$, there
exists a clique of size $K$ in the join of $G$ with a vertex. Let
$\mathcal{K}$ denote the vertices of this clique, and take $S_{\mathcal{K}}$
to be the corresponding Seidel adjacency submatrix. In this case,
$S_{\mathcal{K}}=\mathrm{I}_{K}-\mathrm{J}_{K}$, where $\mathrm{J}_{K}$ is the
$K\times K$ matrix of all 1’s. Observing the decomposition
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}=\mathrm{I}_{K}+\mu S_{\mathcal{K}}$,
it follows from (2) that

$\delta_{K}\geq\|\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K}\|_{2}=\|\mu
S_{\mathcal{K}}\|_{2}=\mu\|\mathrm{I}_{K}-\mathrm{J}_{K}\|_{2}=(K-1)\mu,$

which concludes the proof. ∎

This result indicates that the Gershgoin analysis is tight for all real ETFs,
at least for sufficiently small values of $K$. In particular, in order for a
real ETF to be RIP beyond the square-root bottleneck, its graph must have a
small clique number. As an example, note that the first four columns of the
Steiner ETF in (5) have negative inner products with each other, and thus the
corresponding subgraph is a clique. In general, each block of an $M\times N$
Steiner ETF, whose size is guaranteed to be $\mathrm{O}(\sqrt{M})$, is a
lower-dimensional simplex and therefore has this property; this is an
alternative proof that the Gershgorin analysis of Steiner ETFs is tight for
$K=\mathrm{O}(\sqrt{M})$.

###  5.1. Equiangular tight frames with flat restricted orthogonality

To find ETFs that are RIP beyond the square-root bottleneck, we must apply
better techniques than Gershgorin. We first consider what it means for an ETF
to have $(K,\hat{\theta})$-flat restricted orthogonality. Take a real ETF
$\Phi=[\varphi_{1}\cdots\varphi_{N}]$ with worst-case coherence $\mu$, and
note that the corresponding Seidel adjacency matrix $S$ can be expressed in
terms of the usual $\\{0,1\\}$-adjacency matrix $A$ of the same graph:
$S[i,j]=1-2A[i,j]$ whenever $i\neq j$. Therefore, for every disjoint
$\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}|,|\mathcal{J}|\leq K$, we want

$\displaystyle\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$
$\displaystyle\geq\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}=\bigg{|}\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}\mu
S[i,j]\bigg{|}$
$\displaystyle\qquad=\mu\bigg{|}|\mathcal{I}||\mathcal{J}|-2\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}A[i,j]\bigg{|}=2\mu\bigg{|}E(\mathcal{I},\mathcal{J})-\frac{1}{2}|\mathcal{I}||\mathcal{J}|\bigg{|},$
(19)

where $E(\mathcal{I},\mathcal{J})$ denotes the number of edges between
$\mathcal{I}$ and $\mathcal{J}$ in the graph. This condition bears a striking
resemblence to the following well-known result in graph theory:

######  Lemma 21 (Expander mixing lemma [19]).

Given a $d$-regular graph of $n$ vertices, the second largest eigenvalue
$\lambda$ of its adjacency matrix satisfies

$\bigg{|}E(\mathcal{I},\mathcal{J})-\frac{d}{n}|\mathcal{I}||\mathcal{J}|\bigg{|}\leq\lambda(|\mathcal{I}||\mathcal{J}|)^{1/2}$

for every pair of vertex subsets $\mathcal{I},\mathcal{J}$.

In words, the expander mixing lemma says that the number of edges between
vertex subsets of a regular graph is roughly what you would expect in a
_random_ regular graph. For this lemma to be applicable to (19), we need the
strongly regular graph of Theorem 19 to satisfy
$\frac{L}{N-1}=\frac{d}{n}\approx\frac{1}{2}$. Using the formula for $L$, it
is not difficult to show that
$|\frac{L}{N-1}-\frac{1}{2}|=\mathrm{O}(M^{-1/2})$ provided $N=\mathrm{O}(M)$
and $N\geq 2M$. Furthermore, the second largest eigenvalue of the strongly
regular graph will be $\lambda\approx\frac{1}{2}N^{1/2}$, and so the expander
mixing lemma says the optimal $\hat{\theta}$ is $\leq
2\mu\lambda\approx(\frac{N-M}{M})^{1/2}$ since
$\mu=(\frac{N-M}{M(N-1)})^{1/2}$. This is a rather weak estimate for
$\hat{\theta}$ because the expander mixing lemma does not account for the
sizes of $\mathcal{I}$ and $\mathcal{J}$ being $\leq K$. Put in this light, a
real ETF that has flat restricted orthogonality corresponds to a strongly
regular graph that satisfies a particularly strong version of the expander
mixing lemma.

###  5.2. Equiangular tight frames and the power method

Next, we try applying the power method to ETFs. Given a real ETF
$\Phi=[\varphi_{1}\cdots\varphi_{N}]$, let $H:=\Phi^{*}\Phi-\mathrm{I}_{N}$
denote the “hollow” Gram matrix. Also, take $E_{\mathcal{K}}$ to be the
$N\times K$ matrix built from the columns of $\mathrm{I}_{N}$ that are indexed
by $\mathcal{K}$. Then

$\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]=\mathrm{Tr}[(E_{\mathcal{K}}^{*}\Phi^{*}\Phi
E_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]=\mathrm{Tr}[(E_{\mathcal{K}}^{*}HE_{\mathcal{K}})^{2q}]=\mathrm{Tr}[(HE_{\mathcal{K}}E_{\mathcal{K}}^{*})^{2q}].$

Since
$E_{\mathcal{K}}E_{\mathcal{K}}^{*}=\sum_{k\in\mathcal{K}}\delta_{k}\delta_{k}^{*}$,
where $\delta_{k}$ is the $k$th identity basis element, we continue:

$\displaystyle\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]$
$\displaystyle=\mathrm{Tr}\bigg{[}\bigg{(}H\sum_{k\in\mathcal{K}}\delta_{k}\delta_{k}^{*}\bigg{)}^{2q}\bigg{]}$
$\displaystyle=\sum_{k_{0}\in\mathcal{K}}\cdots\sum_{k_{2q-1}\in\mathcal{K}}\mathrm{Tr}[H\delta_{k_{0}}\delta_{k_{0}}^{*}\cdots
H\delta_{k_{2q-1}}\delta_{k_{2q-1}}^{*}]$
$\displaystyle=\sum_{k_{0}\in\mathcal{K}}\cdots\sum_{k_{2q-1}\in\mathcal{K}}\delta_{k_{0}}^{*}H\delta_{k_{1}}\cdots\delta_{k_{2q-1}}^{*}H\delta_{k_{0}},$
(20)

where the last step used the cyclic property of the trace. From here, note
that $H$ has a zero diagonal, meaning several of the terms in (20) are zero,
namely, those for which $k_{\ell+1}=k_{\ell}$ for some
$\ell\in\mathbb{Z}_{2q}$. To simplify (20), take $\mathcal{K}^{(2q)}$ to be
the set of $2q$-tuples satisfying $k_{\ell+1}\neq k_{\ell}$ for every
$\ell\in\mathbb{Z}_{2q}$:

$\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{2q}]=\sum_{\\{k_{\ell}\\}\in\mathcal{K}^{(2q)}}\prod_{\ell\in\mathbb{Z}_{2q}}\langle\varphi_{k_{\ell}},\varphi_{k_{\ell+1}}\rangle=\mu^{2q}\sum_{\\{k_{\ell}\\}\in\mathcal{K}^{(2q)}}\prod_{\ell\in\mathbb{Z}_{2q}}S[k_{\ell},k_{\ell+1}],$
(21)

where $\mu$ is the wost-case coherence of $\Phi$, and $S$ is the corresponding
Seidel adjacency matrix. Note that the left-hand side is necessarily
nonnegative, while it is not immediate why the right-hand side should be. This
indicates that more simplification can be done, but for the sake of clarity,
we will perform this simplification in the special case where $q=2$; the
general case is very similar. When $q=2$, we are concerned with 4-tuples
$\\{k_{0},k_{1},k_{2},k_{3}\\}\in\mathcal{K}^{(4)}$. Let’s partition these
4-tuples according to the value taken by $k_{0}$ and $k_{q}=k_{2}$. Note, for
a fixed $k_{0}$ and $k_{2}$, that $k_{1}$ can be any value other than $k_{0}$
or $k_{2}$, as can $k_{3}$. This leads to the following simplification:

$\displaystyle\sum_{\\{k_{\ell}\\}\in\mathcal{K}^{(4)}}\prod_{\ell\in\mathbb{Z}_{4}}S[k_{\ell},k_{\ell+1}]$
$\displaystyle=\sum_{k_{0}\in\mathcal{K}}\sum_{k_{2}\in\mathcal{K}}\bigg{(}\sum_{\begin{subarray}{c}k_{1}\in\mathcal{K}\\\
k_{0}\neq k_{1}\neq
k_{2}\end{subarray}}S[k_{0},k_{1}]S[k_{1},k_{2}]\bigg{)}\bigg{(}\sum_{\begin{subarray}{c}k_{3}\in\mathcal{K}\\\
k_{2}\neq k_{3}\neq k_{0}\end{subarray}}S[k_{2},k_{3}]S[k_{3},k_{0}]\bigg{)}$
$\displaystyle=\sum_{k_{0}\in\mathcal{K}}\sum_{k_{2}\in\mathcal{K}}~{}~{}~{}~{}\bigg{|}\\!\\!\\!\\!\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\
k_{0}\neq k\neq k_{2}\end{subarray}}S[k_{0},k]S[k,k_{2}]\bigg{|}^{2}$
$\displaystyle=\sum_{k_{0}\in\mathcal{K}}\bigg{|}\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\
k\neq
k_{0}\end{subarray}}S[k_{0},k]S[k,k_{0}]\bigg{|}^{2}+\sum_{k_{0}\in\mathcal{K}}\sum_{\begin{subarray}{c}k_{2}\in\mathcal{K}\\\
k_{2}\neq
k_{0}\end{subarray}}~{}~{}~{}~{}\bigg{|}\\!\\!\\!\\!\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\
k_{0}\neq k\neq k_{2}\end{subarray}}S[k_{0},k]S[k,k_{2}]\bigg{|}^{2}.$

The first term above is $K(K-1)^{2}$, while the other term is not as easy to
analyze, as we expect a certain degree of cancellation. Substituting this
simplification into (21) gives

$\mathrm{Tr}[(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}-\mathrm{I}_{K})^{4}]=\mu^{4}\bigg{(}K(K-1)^{2}+\sum_{k_{0}\in\mathcal{K}}\sum_{\begin{subarray}{c}k_{2}\in\mathcal{K}\\\
k_{2}\neq
k_{1}\end{subarray}}~{}~{}~{}~{}\bigg{|}\\!\\!\\!\\!\sum_{\begin{subarray}{c}k\in\mathcal{K}\\\
k_{0}\neq k\neq k_{2}\end{subarray}}S[k_{0},k]S[k,k_{2}]\bigg{|}^{2}\bigg{)}.$

If there were no cancellations in the second term, then it would equal
$K(K-1)(K-2)^{2}$, thereby dominating the expression. However, if oscillations
occured as a $\pm 1$ Bernoulli random variable, we could expect this term to
be on the order of $K^{3}$, matching the order of the first term. In this
hypothetical case, since $\mu\leq M^{-1/2}$, the parameter $\delta_{K;2}^{4}$
defined in Theorem 16 scales as $\frac{K^{3}}{M^{2}}$, and so $M\sim K^{3/2}$;
this corresponds to the behavior exhibited in Theorem 17. To summarize, much
like flat restricted orthogonality, applying the power method to ETFs leads to
interesting combinatorial questions regarding subgraphs, even when $q=2$.

###  5.3. The Paley equiangular tight frame as an RIP candidate

Pick some prime $p\equiv 1\bmod 4$, and build an $M\times p$ matrix $H$ by
selecting the $M:=\frac{p+1}{2}$ rows of the $p\times p$ discrete Fourier
transform matrix which are indexed by $Q$, the quadratic residues modulo $p$
(including zero). To be clear, the entries of $H$ are scaled to have unit
modulus. Next, take $D$ to be an $M\times M$ diagonal matrix whose zeroth
diagonal entry is $p^{-1/2}$, and whose remaining $M-1$ entries are
$(\frac{2}{p})^{1/2}$. Now build the matrix $\Phi$ by concatenating $DH$ with
the zeroth identity basis element; for example, when $p=5$, we have a $3\times
6$ matrix:

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

We claim that in general, this process produces an $M\times 2M$ equiangular
tight frame, which we call the _Paley ETF_ [24]. Presuming for the moment that
this claim is true, we have the following result which lends hope for the
Paley ETF as an RIP matrix:

######  Lemma 22.

An $M\times 2M$ Paley equiangular tight frame has restricted isometry constant
$\delta_{K}<1$ for all $K\leq M$.

###### Proof.

First, we note that Theorem 6 of [1] used Chebotarëv’s theorem [28] to prove
that the spark of the $M\times 2M$ Paley ETF $\Phi$ is $M+1$, that is, every
size-$M$ subcollection of columns of $\Phi$ forms a spanning set. Thus, for
every $\mathcal{K}\subseteq\\{1,\ldots,2M\\}$ of size $\leq M$, the smallest
singular value of $\Phi_{\mathcal{K}}$ is positive. It remains to show that
the square of the largest singular value is strictly less than 2. Let $x$ be a
unit vector for which
$\|\Phi_{\mathcal{K}}^{*}x\|=\|\Phi_{\mathcal{K}}^{*}\|_{2}$. Then since the
spark of $\Phi$ is $M+1$, the columns of $\Phi_{\mathcal{K}^{\mathrm{c}}}$
span, and so

$\|\Phi_{\mathcal{K}}\|_{2}^{2}=\|\Phi_{\mathcal{K}}^{*}\|_{2}^{2}=\|\Phi_{\mathcal{K}}^{*}x\|^{2}<\|\Phi_{\mathcal{K}}^{*}x\|^{2}+\|\Phi_{\mathcal{K}^{\mathrm{c}}}^{*}x\|^{2}=\|\Phi^{*}x\|^{2}\leq\|\Phi^{*}\|_{2}^{2}=\|\Phi\Phi^{*}\|_{2}=2,$

where the final step follows from Definition 5(i)-(ii), which imply
$\Phi\Phi^{*}=2\mathrm{I}_{M}$. ∎

Now that we have an interest in the Paley ETF $\Phi$, we wish to verify that
it is, in fact, an ETF. It suffices to show that the columns of $\Phi$ have
unit norm, and that the inner products between distinct columns equal the
Welch bound in absolute value. Certainly, the zeroth identity basis element is
unit-norm, while the squared norm of each of the other columns is given by
$\frac{1}{p}+(M-1)\frac{2}{p}=\frac{2M-1}{p}=1$. Also, the inner product
between the zeroth identity basis element and any other column equals the
zeroth entry of that column: $p^{-1/2}=(\frac{N-M}{M(N-1)})^{1/2}$. It remains
to calculate the inner product between distinct columns which are not identity
basis elements. To this end, note that since $a^{2}=b^{2}$ if and only if
$a=\pm b$, the sequence $\\{k^{2}\\}_{k=1}^{p-1}\subseteq\mathbb{Z}_{p}$
doubly covers $Q\setminus\\{0\\}$, and so

$\langle\varphi_{n},\varphi_{n^{\prime}}\rangle=\frac{1}{p}+\sum_{m\in
Q\setminus\\{0\\}}\bigg{(}\sqrt{\frac{2}{p}}e^{-2\pi\mathrm{i}mn/p}\bigg{)}\bigg{(}\sqrt{\frac{2}{p}}e^{2\pi\mathrm{i}mn^{\prime}/p}\bigg{)}=\frac{1}{p}\sum_{k=0}^{p-1}e^{2\pi\mathrm{i}(n^{\prime}-n)k^{2}/p}.$

This well-known expression is called a quadratic Gauss sum, and since $p\equiv
1\bmod 4$, its value is determined by the Legendre symbol in the following
way:
$\langle\varphi_{n},\varphi_{n^{\prime}}\rangle=\frac{1}{\sqrt{p}}(\frac{n^{\prime}-n}{p})$
for every $n,n^{\prime}\in\mathbb{Z}_{p}$ with $n\neq n^{\prime}$, where

$\bigg{(}\frac{k}{p}\bigg{)}:=\left\\{\begin{array}[]{rl}+1&\mbox{ if $k$ is a
nonzero quadratic residue modulo $p$,}\\\ 0&\mbox{ if $k=0$,}\\\ -1&\mbox{
otherwise.}\end{array}\right.$

Having established that $\Phi$ is an ETF, we notice that the inner products
between distinct columns of $\Phi$ are real. This implies that the columns of
$\Phi$ can be unitarily rotated to form a real ETF $\Psi$; indeed, one may
take $\Psi$ to be the $M\times 2M$ matrix formed by taking the nonzero rows of
$L^{\mathrm{T}}$ in the Cholesky factorization $\Phi^{*}\Phi=LL^{\mathrm{T}}$.
As such, we consider the Paley ETF to be real. From here, Theorem 19 prompts
us to find the corresponding strongly regular graph. First, we can flip the
identity basis element so that its inner products with the other columns of
$\Phi$ are all negative. As such, the corresponding vertex in the graph will
be adjacent to each of the other vertices; naturally, this will be the vertex
to which the strongly regular graph is joined. For the remaining vertices,
$n\leftrightarrow n^{\prime}$ precisely when $(\frac{n^{\prime}-n}{p})=-1$,
that is, when $n^{\prime}-n$ is not a quadratic residue. The corresponding
subgraph is therefore the complement of the Paley graph, namely, the Paley
graph [26]. In general, Paley graphs of order $p$ necessarily have $p\equiv
1\bmod 4$, and so this correspondence is particularly natural.

One interesting thing about the Paley ETF’s restricted isometry is that it
lends insight into important properties of the Paley graph. The following is
the best known upper bound for the clique number of the Paley graph of prime
order (see Theorem 13.14 of [6] and discussion thereafter), and we give a new
proof of this bound using restricted isometry:

######  Theorem 23.

Let $G$ denote the Paley graph of prime order $p$. Then the size of the
largest clique is $\omega(G)<\sqrt{p}$.

###### Proof.

We start by showing $\omega(G)+1\leq M$. Suppose otherwise: that there exists
a clique $\mathcal{K}$ of size $M+1$ in the join of a vertex with $G$. Then
the corresponding sub-Gram matrix of the Paley ETF has the form
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}=(1+\mu)\mathrm{I}_{M+1}-\mu\mathrm{J}_{M+1}$,
where $\mu=p^{-1/2}$ is the worst-case coherence and $\mathrm{J}_{M+1}$ is the
$(M+1)\times(M+1)$ matrix of 1’s. Since the largest eigenvalue of
$\mathrm{J}_{M+1}$ is $M+1$, the smallest eigenvalue of
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$ is
$1+p^{-1/2}-(M+1)p^{-1/2}=1-\frac{1}{2}(p+1)p^{-1/2}$, which is negative when
$p\geq 5$, contradicting the fact that
$\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}}$ is positive semidefinite.

Since $\omega(G)+1\leq M$, we can apply Lemma 22 and Theorem 20 to get

$1>\delta_{\omega(G)+1}=\Big{(}\omega(G)+1-1\Big{)}\mu=\frac{\omega(G)}{\sqrt{p}},$
(22)

and rearranging gives the result. ∎

It is common to apply probabilistic and heuristic reasoning to gain intuition
in number theory. For example, consecutive entries of the Legendre symbol are
known to mimic certain properties of a $\pm 1$ Bernoulli random variable [22].
Moreover, Paley graphs enjoy a certain quasi-random property that was studied
in [11]. On the other hand, Graham and Ringrose [18] showed that, while random
graphs of size $p$ have an expected clique number of $(1+o(1))2\log p/\log 2$,
Paley graphs of prime order deviate from this random behavior, having a clique
number $\geq c\log p\log\log\log p$ infinitely often. The best known universal
lower bound, $(1/2+o(1))\log p/\log 2$, is given in [12], which indicates that
the random graph analysis is at least tight in some sense. Regardless, this
has a significant difference from the upper bound $\sqrt{p}$ in Theorem 23,
and it would be nice if probabilistic arguments could be leveraged to improve
this bound, or at least provide some intuition.

Note that our proof (22) hinged on the fact that $\delta_{\omega(G)+1}<1$,
courtesy of Lemma 22. Hence, any improvement to our estimate for
$\delta_{\omega(G)+1}$ would directly lead to the best known upper bound on
the Paley graph’s clique number. To approach such an improvement, note that
for large $p$, the Fourier portion of the Paley ETF $DH$ is not significatly
different from the normalized partial Fourier matrix $(\frac{2}{p+1})^{1/2}H$;
indeed,
$\|H_{\mathcal{K}}^{*}D^{2}H_{\mathcal{K}}-\frac{2}{p+1}H_{\mathcal{K}}^{*}H_{\mathcal{K}}\|_{2}\leq\frac{2}{p}$
for every $\mathcal{K}\subseteq\mathbb{Z}_{p}$ of size $\leq\frac{p+1}{2}$,
and so the difference vanishes. If we view the quadratic residues modulo $p$
(the row indices of $H$) as random, then a random partial Fourier matrix
serves as a proxy for the Fourier portion of the Paley ETF. This in mind, we
appeal to the following:

######  Theorem 24 (Theorem 3.2 in [23]).

Draw rows from the $N\times N$ discrete Fourier transform matrix uniformly at
random with replacement to construct an $M\times N$ matrix, and then normalize
the columns to form $\Phi$. Then $\Phi$ has restricted isometry constant
$\delta_{K}\leq\delta$ with probability $1-\varepsilon$ provided
$\frac{M}{\log M}\geq\frac{C}{\delta^{2}}K\log^{2}K\log
N\log\varepsilon^{-1}$, where $C$ is a universal constant.

In our case, both $M$ and $N$ scale as $p$, and so picking $\delta$ to achieve
equality above gives

$\delta^{2}=\frac{C^{\prime}}{p}K\log^{2}K\log^{2}p\log\varepsilon^{-1}.$

Continuing as in (22), denote $\omega=\omega(G)$ and take $K=\omega$ to get

$\frac{C^{\prime}}{p}\omega\log^{2}\omega\log^{2}p\log\varepsilon^{-1}\geq\delta_{\omega}^{2}=\frac{(\omega-1)^{2}}{p}\geq\frac{\omega^{2}}{2p},$

and then rearranging gives $\omega/\log^{2}\omega\leq
C^{\prime\prime}\log^{2}p\log\varepsilon^{-1}$ with probability
$1-\varepsilon$. Interestingly, having
$\omega/\log^{2}\omega=\mathrm{O}(\log^{3}p)$ with high probability (again,
under the model that quadratic residues are random) agrees with the results of
Graham and Ringrose [18]. This gives some intuition for what we can expect the
size of the Paley graph’s clique number to be, while at the same time
demonstrating the power of Paley ETFs as RIP candidates. We conclude with the
following, which can be reformulated in terms of both flat restricted
orthogonality and the power method:

######  Conjecture 25.

The Paley equiangular tight frame has the $(K,\delta)$-restricted isometry
property with some $\delta<\sqrt{2}-1$ whenever
$K\leq\frac{Cp}{\log^{\alpha}p}$, for some universal constants $C$ and
$\alpha$.

##  6\. Appendix

In this section, we prove Theorem 13, which states that a matrix with
$(K,\hat{\theta})$-flat restricted orthogonality has $\theta_{K}\leq
C\hat{\theta}\log K$, that is, it has restricted orthogonality. The proof
below is adapted from the proof of Lemma 3 in [7]. Our proof has the benefit
of being valid for all values of $K$ (as opposed to sufficiently large $K$ in
the original [7]), and it has near-optimal constants where appropriate.
Moreover in this version, the columns of the matrix are not required to have
unit norm.

###### Proof of Theorem 13.

Given arbitrary disjoint subsets
$\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}|,|\mathcal{J}|\leq K$, we will bound the following quantity
three times, each time with different constraints on
$\\{x_{i}\\}_{i\in\mathcal{I}}$ and $\\{y_{j}\\}_{j\in\mathcal{J}}$:

$\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}.$
(23)

To be clear, our third bound will have no constraints on
$\\{x_{i}\\}_{i\in\mathcal{I}}$ and $\\{y_{j}\\}_{j\in\mathcal{J}}$, thereby
demonstrating restricted orthogonality. Note that by assumption, (23) is
$\leq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$ whenever the $x_{i}$’s
and $y_{j}$’s are in $\\{0,1\\}$. We first show that this bound is preserved
when we relax the $x_{i}$’s and $y_{j}$’s to lie in the interval $[0,1]$.

Pick a disjoint pair of subsets
$\mathcal{I}^{\prime},\mathcal{J}^{\prime}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}^{\prime}|,|\mathcal{J}^{\prime}|\leq K$. Starting with some
$k\in\mathcal{I}^{\prime}$, note that flat restricted orthogonality gives that

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2},$
$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}\setminus\\{k\\}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\hat{\theta}(|\mathcal{I}\setminus\\{k\\}||\mathcal{J}|)^{1/2}\leq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$

for every disjoint $\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}|,|\mathcal{J}|\leq K$ and $k\in\mathcal{I}$. Thus, we may take
any $x_{k}\in[0,1]$ to form a convex combination of these two expressions, and
then the triangle inequality gives

$\displaystyle\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$
$\displaystyle\geq
x_{k}\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}+(1-x_{k})\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}\setminus\\{k\\}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\geq\bigg{|}x_{k}\bigg{\langle}\sum_{i\in\mathcal{I}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}+(1-x_{k})\bigg{\langle}\sum_{i\in\mathcal{I}\setminus\\{k\\}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle=\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\bigg{\\{}\begin{array}[]{cc}x_{k},&i=k\\\
1,&i\neq
k\end{array}\bigg{\\}}\varphi_{i},\sum_{j\in\mathcal{J}}\varphi_{j}\bigg{\rangle}\bigg{|}.$
(26)

Since (26) holds for every disjoint
$\mathcal{I},\mathcal{J}\subseteq\\{1,\ldots,N\\}$ with
$|\mathcal{I}|,|\mathcal{J}|\leq K$ and $k\in\mathcal{I}$, we can do the same
thing with an additional index $i\in\mathcal{I}^{\prime}$ or
$j\in\mathcal{J}^{\prime}$, and replace the corresponding unit coefficient
with some $x_{i}$ or $y_{j}$ in $[0,1]$. Continuing in this way proves the
claim that (23) is $\leq\hat{\theta}(|\mathcal{I}||\mathcal{J}|)^{1/2}$
whenever the $x_{i}$’s and $y_{j}$’s lie in the interval $[0,1]$.

For the second bound, we assume the $x_{i}$’s and $y_{j}$’s are nonnegative
with unit norm:
$\sum_{i\in\mathcal{I}}x_{i}^{2}=\sum_{j\in\mathcal{J}}y_{j}^{2}=1$. To bound
(23) in this case, we partition $\mathcal{I}$ and $\mathcal{J}$ according to
the size of the corresponding coefficients:

$\mathcal{I}_{k}:=\\{i\in\mathcal{I}:2^{-(k+1)}<x_{i}\leq
2^{-k}\\},\qquad\mathcal{J}_{k}:=\\{j\in\mathcal{J}:2^{-(k+1)}<y_{j}\leq
2^{-k}\\}.$

Note the unit-norm constraints ensure that
$\mathcal{I}=\bigcup_{k=0}^{\infty}\mathcal{I}_{k}$ and
$\mathcal{J}=\bigcup_{k=0}^{\infty}\mathcal{J}_{k}$. The triangle inequality
thus gives

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle=\bigg{|}\bigg{\langle}\sum_{k_{1}=0}^{\infty}\sum_{i\in\mathcal{I}_{k_{1}}}x_{i}\varphi_{i},\sum_{k_{2}=0}^{\infty}\sum_{j\in\mathcal{J}_{k_{2}}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}2^{-(k_{1}+k_{2})}\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}_{k_{1}}}\frac{x_{i}}{2^{-k_{1}}}\varphi_{i},\sum_{j\in\mathcal{J}_{k_{2}}}\frac{y_{j}}{2^{-k_{2}}}\varphi_{j}\bigg{\rangle}\bigg{|}.$
(27)

By the definitions of $\mathcal{I}_{k_{1}}$ and $\mathcal{J}_{k_{2}}$, the
coefficients of $\varphi_{i}$ and $\varphi_{j}$ in (27) all lie in $[0,1]$. As
such, we continue by applying our first bound:

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\sum_{k_{1}=0}^{\infty}\sum_{k_{2}=0}^{\infty}2^{-(k_{1}+k_{2})}\hat{\theta}(|\mathcal{I}_{k_{1}}||\mathcal{J}_{k_{2}}|)^{1/2}$
$\displaystyle=\hat{\theta}\bigg{(}\sum_{k=0}^{\infty}2^{-k}|\mathcal{I}_{k}|^{1/2}\bigg{)}\bigg{(}\sum_{k=0}^{\infty}2^{-k}|\mathcal{J}_{k}|^{1/2}\bigg{)}.$
(28)

We now observe from the definition of $\mathcal{I}_{k}$ that

$1=\sum_{i\in\mathcal{I}}x_{i}^{2}=\sum_{k=0}^{\infty}\sum_{i\in\mathcal{I}_{k}}x_{i}^{2}>\sum_{k=0}^{\infty}4^{-(k+1)}|\mathcal{I}_{k}|.$

Thus for any positive integer $t$, the Cauchy-Schwarz inequality gives

$\displaystyle\sum_{k=0}^{\infty}2^{-k}|\mathcal{I}_{k}|^{1/2}$
$\displaystyle=\sum_{k=0}^{t-1}2^{-k}|\mathcal{I}_{k}|^{1/2}+\sum_{k=t}^{\infty}2^{-k}|\mathcal{I}_{k}|^{1/2}$
$\displaystyle\leq
t^{1/2}\bigg{(}\sum_{k=0}^{t-1}4^{-k}|\mathcal{I}_{k}|\bigg{)}^{1/2}+\sum_{k=t}^{\infty}2^{-k}K^{1/2}$
$\displaystyle<2(t^{1/2}+K^{1/2}2^{-t}),$ (29)

and similarly for the $\mathcal{J}_{k}$’s. For a fixed $K$, we note that (29)
is minimized when $K^{1/2}2^{-t}=\frac{t^{-1/2}}{2\log 2}$, and so we pick $t$
to be the smallest positive integer such that
$K^{1/2}2^{-t}\leq\frac{t^{-1/2}}{2\log 2}$. With this, we continue (28):

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle<\hat{\theta}\Big{(}2(t^{1/2}+K^{1/2}2^{-t})\Big{)}^{2}$
$\displaystyle\leq 4\hat{\theta}\bigg{(}t^{1/2}+\frac{t^{-1/2}}{2\log
2}\bigg{)}^{2}=4\hat{\theta}\bigg{(}t+\frac{1}{\log 2}+\frac{1}{(2\log
2)^{2}t}\bigg{)}.$ (30)

From here, we claim that $t\leq\lceil\frac{\log K}{\log 2}\rceil$. Considering
the definition of $t$, this is easily verified for $K=2,3,\ldots,7$ by showing
$K^{1/2}2^{-s}\leq\frac{s^{-1/2}}{2\log 2}$ for $s=\lceil\frac{\log K}{\log
2}\rceil$. For $K\geq 8$, one can use calculus to verify the second inequality
of the following:

$K^{1/2}2^{-\lceil\frac{\log K}{\log 2}\rceil}\leq K^{1/2}2^{-\frac{\log
K}{\log 2}}\leq\frac{1}{2\log 2}\bigg{(}\frac{\log K}{\log
2}+1\bigg{)}^{-1/2}\leq\frac{1}{2\log 2}\bigg{\lceil}\frac{\log K}{\log
2}\bigg{\rceil}^{-1/2},$

meaning $t\leq\lceil\frac{\log K}{\log 2}\rceil$. Substituting
$t\leq\frac{\log K}{\log 2}+1$ and $t\geq 1$ into (30) then gives

$\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}<4\hat{\theta}\bigg{(}\frac{\log
K}{\log 2}+1+\frac{1}{\log 2}+\frac{1}{(2\log 2)^{2}}\bigg{)}\\\
=\hat{\theta}(C_{0}\log K+C_{1}),$

with $C_{0}\approx 5.77$, $C_{1}\approx 11.85$. As such, (23) is $\leq
C^{\prime}\hat{\theta}\log K$ with $C^{\prime}=C_{0}+\frac{C_{1}}{\log 2}$ in
this case.

We are now ready for the final bound on (23) in which we apply no constraints
on the $x_{i}$’s and $y_{j}$’s. To do this, we consider the positive and
negative real and imaginary parts of these coefficients:

$x_{i}=\sum_{k=0}^{3}x_{i,k}\mathrm{i}^{k}\quad\mbox{s.t.}\quad x_{i,k}\geq
0\quad\forall k,$

and similarly for the $y_{j}$’s. With this decomposition, we apply the
triangle inequality to get

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle=\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}\sum_{k_{1}=0}^{3}x_{i,k_{1}}\mathrm{i}^{k_{1}}\varphi_{i},\sum_{j\in\mathcal{J}}\sum_{k_{2}=0}^{3}y_{j,k_{2}}\mathrm{i}^{k_{2}}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\sum_{k_{1}=0}^{3}\sum_{k_{2}=0}^{3}\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i,k_{1}}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j,k_{2}}\varphi_{j}\bigg{\rangle}\bigg{|}.$

Finally, we normalize the coefficients by
$(\sum_{i\in\mathcal{I}}x_{i,k_{1}}^{2})^{1/2}$ and
$(\sum_{j\in\mathcal{J}}y_{j,k_{2}}^{2})^{1/2}$ so we can apply our second
bound:

$\displaystyle\bigg{|}\bigg{\langle}\sum_{i\in\mathcal{I}}x_{i}\varphi_{i},\sum_{j\in\mathcal{J}}y_{j}\varphi_{j}\bigg{\rangle}\bigg{|}$
$\displaystyle\leq\sum_{k_{1}=0}^{3}\sum_{k_{2}=0}^{3}\bigg{(}\sum_{i\in\mathcal{I}}x_{i,k_{1}}^{2}\bigg{)}^{1/2}\bigg{(}\sum_{j\in\mathcal{J}}y_{j,k_{2}}^{2}\bigg{)}^{1/2}C^{\prime}\hat{\theta}\log
K$ $\displaystyle\leq(C\hat{\theta}\log K)\|x\|\|y\|,$

where $C=4C^{\prime}\approx 74.17$ by the Cauchy-Schwarz inequality, and so we
are done. ∎

## References

  * [1] B. Alexeev, J. Cahill, D.G. Mixon, Full spark frames, submitted, Available online: arXiv:1110.3548
  * [2] N. Alon, A. Naor, Approximating the cut-norm via Grothendieck’s inequality, SIAM J. Comput. 35 (2006) 787–803.
  * [3] L. Applebaum, S.D. Howard, S. Searle and R. Calderbank, Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery, Appl. Comp. Harmon. Anal. 26 (2009) 283–290.
  * [4] R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx. 28 (2008) 253–263.
  * [5] S.N. Bernstein, Theory of Probability, 4th ed., Moscow-Leningrad, 1946.
  * [6] B. Bollobás, Random Graphs, 2nd ed., Cambridge, 2001.
  * [7] J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, Explicit constructions of RIP matrices and related problems, Duke Math. J. 159 (2011) 145–185.
  * [8] E.J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci. Paris, Ser. I 346 (2008) 589–592.
  * [9] E.J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 44 (2005) 4203–4215.
  * [10] E.J. Candès and T. Tao, The Dantzig selector: Statistical estimation when $p$ is much larger than $n$, Ann. Statist. 35 (2007) 2313–2351.
  * [11] F.R.K. Chung, R.L. Graham and R.M. Wilson, Quasi-random graphs, Combinat. 9 (1989) 345–362.
  * [12] S.D. Cohen, Clique numbers of Paley graphs, Quaestiones Math. 11 (1988), 225–231.
  * [13] K.R. Davidson and S.J. Szarek, Local operator theory, random matrices and Banach spaces, In: Handbook in Banach Spaces Vol I, ed. W.B. Johnson, J. Lindenstrauss, Elsevier (2001), 317–366.
  * [14] R.A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007) 918–925.
  * [15] D.L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell_{1}$ minimization, Proc. Nat. Acad. Sci. USA 100 (2003) 2197–2202.
  * [16] M. Fickus, D.G. Mixon and J.C. Tremain, Steiner equiangular tight frames, Linear Algebra Appl. 436 (2012) 1014–1027.
  * [17] S. Gerschgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. 7 (1931) 749–754.
  * [18] S.W. Graham and C.J. Ringrose, Lower bounds for least quadratic non-residues, Prog. Math. 85 (1990) 269–309.
  * [19] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006) 439–561.
  * [20] B. Laurent and P. Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Statist. 28 (2000) 1302–1338.
  * [21] B.K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995) 227–234.
  * [22] R. Peralta, On the distribution of quadratic residues and nonresidues modulo a prime number, Math. Comput. 58 (1992) 433–440.
  * [23] H. Rauhut, Stability results for random sampling of sparse trigonometric polynomials, IEEE Trans. Inform. Theory 54 (2008) 5661–5670.
  * [24] J.M. Renes, Equiangular tight frames from Paley tournaments, Linear Algebra Appl. 426 (2007) 497–501.
  * [25] M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math. 61 (2008) 1025–1045.
  * [26] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962) 270–288.
  * [27] J.J. Seidel, A survey of two-graphs, in: Proc. Intern. Coll. Teorie Combinatorie (1973) 481–511.
  * [28] P. Stevenhagen, H.W. Lenstra, Chebotarëv and his density theorem, Math. Intelligencer 18 (1996) 26–37.
  * [29] T. Strohmer and R.W. Heath, Grassmannian frames with applications to coding and communication, Appl. Comp. Harmon. Anal. 14 (2003) 257–275.
  * [30] T. Tao, Open question: Deterministic UUP matrices,
http://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-
matrices.

  * [31] J.H. van Lint, J.J. Seidel, Equilateral point sets in elliptic geometry, Nederl. Akad. Wetensch. Proc. Ser. A 69 (1966) 335–348; Indag. Math. 28.
  * [32] S. Waldron, On the construction of equiangular frames from graphs, Linear Algebra Appl. 431 (2009) 2228–2242.
  * [33] L.R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory 20 (1974) 397–399.
  * [34] P. Xia, S. Zhou and G.B Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory 51 (2005) 1900–1907.
  * [35] V.V. Yurinskii, Exponential inequalities for sums of random vectors, J. Multivariate Anal. 6 (1976) 473–499.