# Frame Coherence and Sparse Signal Processing

Dustin G. Mixon1, Waheed U. Bajwa2, Robert Calderbank2  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. 1Program in
Applied and Computational Mathematics, Princeton University, Princeton, New
Jersey 08544  2Department of Electrical and Computer Engineering, Duke
University, Durham, North Carolina 27708

###### Abstract

The sparse signal processing literature often uses random sensing matrices to
obtain performance guarantees. Unfortunately, in the real world, sensing
matrices do not always come from random processes. It is therefore desirable
to evaluate whether an arbitrary matrix, or frame, is suitable for sensing
sparse signals. To this end, the present paper investigates two parameters
that measure the coherence of a frame: worst-case and average coherence. We
first provide several examples of frames that have small spectral norm, worst-
case coherence, and average coherence. Next, we present a new lower bound on
worst-case coherence and compare it to the Welch bound. Later, we propose an
algorithm that decreases the average coherence of a frame without changing its
spectral norm or worst-case coherence. Finally, we use worst-case and average
coherence, as opposed to the Restricted Isometry Property, to garner near-
optimal probabilistic guarantees on both sparse signal detection and
reconstruction in the presence of noise. This contrasts with recent results
that only guarantee noiseless signal recovery from arbitrary frames, and which
further assume independence across the nonzero entries of the signal—in a
sense, requiring small average coherence replaces the need for such an
assumption.

##  I Introduction

Many classical applications, such as radar and error-correcting codes, make
use of over-complete spanning systems [1]. 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 [4, 5, 2, 3, 1, 6, 7, 8].
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 [4, 5, 6, 7, 8]. Recently, [9] 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. It was established in [9] that when
$\nu_{F}$ is sufficiently smaller than $\mu_{F}$, a number of guarantees can
be provided for sparse signal processing. It is therefore evident from [9, 4,
5, 2, 3, 1, 6, 7, 8] that there is 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 four main contributions in this regard. First, we discuss
three types of frames that exhibit small spectral norm, worst-case coherence,
and average coherence: normalized Gaussian, random harmonic, and code-based
frames. With all three frame parameters provably small, these frames are
guaranteed to perform well in relevant applications. Second, performance in
many applications is dictated by worst-case coherence [4, 5, 2, 3, 1, 6, 7,
8]. It is therefore particularly important to understand which worst-case
coherence values are achievable. To this end, the Welch bound [1] 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$
[1]. Another lower bound, given in [10] and [11], beats the Welch bound when
there are more frame elements, but it is known to be loose for real frames
[12]. Given this context, our next contribution is a new lower bound on the
worst-case coherence of real frames. Our bound beats both the Welch bound and
the bound in [10] and [11] when the number of frame elements far exceeds the
spatial dimension. Third, since average coherence is new to the frame theory
literature, we investigate how it relates to worst-case coherence and spectral
norm. In particular, we want average coherence to satisfy the following
property, which is used in [9] to provide various guarantees for sparse signal
processing:

######  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.

Since average coherence is so new, there is currently no intuition as to when
(SCP-2) is satisfied. As a third contribution, this paper shows how 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).
Finally, this paper uses the Strong Coherence Property to provide new
guarantees on both sparse signal detection and reconstruction in the presence
of noise. These guarantees are related to those in [4, 5, 7], and we elaborate
on this relationship in Section V. In the interest of space, the proofs have
been omitted throughout, but they can be found in [13].

##  II Frame constructions

Many applications require nearly tight frames with small worst-case and
average coherence. In this section, we give three types of frames that satisfy
these conditions.

###  II-A 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 [9, 14, 15,
16], which only ensure that the frame elements of Gaussian frames have unit
norm in expectation. In other words, normalized Gaussian frames are frames
with individual frame elements 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 2 (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}}}}$.

###  II-B 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
[17, 18, 19]. 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 3 (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=1}^{N}$ 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}}$.

###  II-C Code-based frames

Many structures in coding theory are also useful for constructing frames.
Here, we build frames from a code that originally emerged with Berlekamp in
[20], and found recent reincarnation with [21]. 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

$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{]}},$
(3)

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.

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

The $2^{m}\times 2^{(t+1)m}$ frame defined by (3) 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}}}}$.

##  III Fundamental limits on worst-case coherence

In many applications of frames, performance is dictated by worst-case
coherence. It is therefore particularly important to understand which worst-
case coherence values are achievable. To this end, the following bound is
commonly used in the literature:

######  Theorem 5 (Welch bound [1]).

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

The Welch bound is not tight whenever $N>M^{2}$ [1]. For this region, the
following gives a better bound:

######  Theorem 6 ([10],[11]).

Every $M\times N$ unit norm frame $F$ has worst-case coherence $\mu_{F}\geq
1-2N^{-1/(M-1)}$. 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 6 is known to be loose for real frames [12]. We therefore
improve Theorem 6 for the case of real unit norm frames:

######  Theorem 7.

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{]}.$
(4)

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

In [12], numerical results are given for $M=3$, and we compare these results
to Theorems 6 and 7 in Figure 1. Considering this figure, we note that the
bound in Theorem 6 is inferior to the maximum of the Welch bound and the bound
in Theorem 7, at least when $M=3$. This illustrates the degree to which
Theorem 7 improves the bound in Theorem 6 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 7 is asymptotically better than the bound for complex frames
in Theorem 6. Moreover, for $M=2$, Theorem 7 says
$\mu\geq\cos(\frac{\pi}{N})$, and [22] proved this bound to be tight for every
$N\geq 2$. For $M=3$, Theorem 7 can be further improved as follows:

######  Theorem 8.

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

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 [12]. Dotted curve gives Welch bound, dash-dotted curve
gives bound from Theorem 6, dashed curve gives general bound from Theorem 7,
and solid curve gives bound from Theorem 8.

##  IV Reducing average coherence

In [9], average coherence is used to garner 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 9 (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 10 (Geometry of wiggling equivalent frames).

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

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 10, 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 11 (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}}}$.

While Theorem 11 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 1). 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 11.

Algorithm 1 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 for shorter sum}

else

$g_{n}\leftarrow-f_{n}$ {Flip frame element for shorter sum}

end if

end for

######  Theorem 12.

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

As an example of how linear-time flipping improves 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 can 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 12 is sufficient
but not necessary.

##  V Near-optimal sparse signal processing without the Restricted Isometry
Property

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 [5] to provide uniform
bounds on the signal and support recovery performance of combinatorial and
convex optimization methods and greedy algorithms. Later, Tropp [7] and Candès
and Plan [4] 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. [9] 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.

###  V-A The Weak Restricted Isometry Property

A common task in signal processing applications is to test whether a
collection of measurements corresponds to mere noise [23]. 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$ [24, 25,
23]. In particular, existing literature on the detection of sparse signals
[24, 25] 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 13.

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
$x\in\mathbb{C}^{N}$, a random permutation $y$ of $x$’s entries satisfies

$(1-\delta)\|y\|^{2}\leq\|Fy\|^{2}\leq(1+\delta)\|y\|^{2}$

with probability exceeding $1-p$.

We 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 [7], 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 14.

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
$2K\log{N}\leq\min\\{\frac{\delta^{2}}{100\mu_{F}^{2}},M\\}$.

###  V-B 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 [7] used both the worst-
case coherence and spectral norm of frames to find bounds on the
reconstruction performance of _basis pursuit (BP)_ [26] for most support sets
under the assumption that the nonzero entries of $x$ are independent with zero
median. In contrast, [9] 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 [7] and
[9] 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 [5], our guarantees will hold for arbitrary 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 [9],
which is described in Algorithm 2. The following theorem extends the analysis
of [9] and shows that the OST algorithm leads to near-optimal reconstruction
error for large 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 2 One-Step Thresholding (OST) [9]

Input: An $M\times N$ unit norm frame $F$, a vector $y=Fx+e$, and a threshold
$\lambda>0$
Output: An estimate $\hat{\mathcal{K}}\subseteq\\{1,\ldots,N\\}$ of the
support of $x$ and an estimate $\hat{x}\in\mathbb{C}^{N}$ of $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 15 (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 2 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
$\smash{c_{3}=1+\frac{\mathrm{e}^{-1/2}}{1-\mathrm{e}^{-1/2}}}$ are numerical
constants.

A few remarks are in order now for Theorem 15. 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, the
$\ell_{2}$ error associated with the OST algorithm is the near-optimal (modulo
the $\log$ factor) error of $\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 $O(\mu_{F}\|x\|\sqrt{2\log{N}})$.
Nevertheless, it is easy to convince oneself that such error is still near-
optimal for large classes of sparse signals. Consider, for example, the case
where $\mu_{F}=O(1/\sqrt{M})$, the magnitudes of $K/2$ nonzero entries of $x$
are some $\alpha=\Omega(\sqrt{\sigma^{2}\log{N}})$, while the magnitudes of
the other $K/2$ nonzero entries are not necessarily same but scale as
$O(\sqrt{\sigma^{2}\log{N}})$. Then we have from Theorem 15 that
$\|x-x_{T}\|=O(\sqrt{\sigma^{2}K\log{N}})$, which leads to near-optimal
$\ell_{2}$ error of $\|x-\hat{x}\|=O(\sqrt{\sigma^{2}K\log{N}})$. To the best
of our knowledge, this 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 in the presence of noise, while
using either random or deterministic frames, even when $K=O(M/\log{N})$.

## References

  * [1] T. Strohmer, R.W. Heath, Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal. 14 (2003) 257–275.
  * [2] R.B. Holmes, V.I. Paulsen, Optimal frames for erasures, Linear Algebra Appl. 377 (2004) 31–51.
  * [3] 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.
  * [4] E.J. Candès, Y. Plan, Near-ideal model selection by $\ell_{1}$ minimization, Ann. Statist. 37 (2009) 2145–2177.
  * [5] 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.
  * [6] J.A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004) 2231–2242.
  * [7] J.A. Tropp, On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal. 25 (2008) 1–24.
  * [8] 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.
  * [9] 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.
  * [10] 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.
  * [11] P. Xia, S. Zhou, G.B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory 51 (2005) 1900–1907.
  * [12] J.H. Conway, R.H. Hardin, N.J.A. Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces, Experiment. Math. 5 (1996) 139–159.
  * [13] W.U. Bajwa, R. Calderbank, D.G. Mixon, Two are better than one: Fundamental parameters of frame coherence, arXiv:1103.0435v1.
  * [14] 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.
  * [15] E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005) 4203–4215.
  * [16] 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.
  * [17] 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.
  * [18] E.J. Candès, T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006) 5406–5425.
  * [19] M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math. 61 (2008) 1025–1045.
  * [20] E.R. Berlekamp, The weight enumerators for certain subcodes of the second order binary Reed-Muller codes, Inform. Control 17 (1970) 485–500.
  * [21] N.Y. Yu, G. Gong, A new binary sequence family with low correlation and large size, IEEE Trans. Inform. Theory 52 (2006) 1624–1636.
  * [22] 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.
  * [23] S.M. Kay, Fundamentals of Statistical Signal Processing: Detection Theory, Upper Saddle River, Prentice Hall, 1998.
  * [24] 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.
  * [25] J. Haupt, R. Nowak, Compressive sampling for signal detection, Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (2007) 1509–1512.
  * [26] S.S. Chen, D.L. Donoho, M.A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Scientific Comput. 20 (1998) 33–61.


p}}{{\rightarrow}}0}\underbrace{R_{M,2}}_{<\infty}+\underbrace{\big{\|}\hat{\beta}-\beta\big{\|}_{2}^{2}}_{\stackrel{{\scriptstyle
p}}{{\rightarrow}}0}\underbrace{R_{M,3}}_{<\infty}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0,$

which proves $\|\hat{V}_{N,M}-\tilde{V}_{N,M}\|_{F}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$.

To sum up, combining parts (1), (2) and (3), we have

$\displaystyle\|\hat{V}_{N,M}-V_{N,M}\|_{F}$
$\displaystyle\leq\underbrace{\|\hat{V}_{N,M}-\tilde{V}_{N,M}\|_{F}}_{\stackrel{{\scriptstyle
p}}{{\rightarrow}}0}+\underbrace{\|\tilde{V}_{N,M}-V^{c}_{N,M}\|_{F}}_{\stackrel{{\scriptstyle
p}}{{\rightarrow}}0}+\underbrace{\|V^{c}_{N,M}-V_{N,M}\|_{F}}_{\stackrel{{\scriptstyle
p}}{{\rightarrow}}0}$ $\displaystyle\stackrel{{\scriptstyle
p}}{{\rightarrow}}0,$

which completes the proof. $\square$

###  C.3 Corollary 4.1

Proof of Corollary 4.1: For simplicity we denote

$\displaystyle\hat{V}_{N,M}^{Dyad}\coloneqq\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}}\mathbbm{1}_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1},$

and

$\displaystyle\hat{V}_{N,M}^{Network}\coloneqq\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}}h_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1},$

where we choose the kernel function and the lag truncation parameter so that
the weights become equal one for all active dyads: namely, we use the
rectangular kernel with the lag truncation being the length of the longest
path in the network. Define moreover $\widetilde{Var}(\hat{\beta})$ to be the
same variance as (12), but is now applied to the network-regression model (1)
and (2). By the triangular inequality,

$\displaystyle\big{\|}N\hat{V}_{N,M}^{Network}-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}$
$\displaystyle=\big{\|}N\hat{V}_{N,M}^{Network}-\widetilde{Var}(\hat{\beta})+\widetilde{Var}(\hat{\beta})-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}$
$\displaystyle\leq\big{\|}N\hat{V}_{N,M}^{Network}-\widetilde{Var}(\hat{\beta})\big{\|}_{F}+\big{\|}\widetilde{Var}(\hat{\beta})-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}.$

Since Theorem 4.1 implies
$\big{\|}N\hat{V}_{N,M}^{Network}-\widetilde{Var}(\hat{\beta})\big{\|}_{F}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$, then in the limit we are left with

$\displaystyle\big{\|}N\hat{V}_{N,M}^{Network}-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}$
$\displaystyle\leq\big{\|}\widetilde{Var}(\hat{\beta})-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}.$
(C.1)

Now we prove the statement by way of contradiction. Assume for the sake of
contradiction that the dyadic-robust variance estimator $\hat{V}_{N,M}^{Dyad}$
is consistent, i.e.,
$\big{\|}\widetilde{Var}(\hat{\beta})-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$. This, combined with the inequality (C.1), implies
$\big{\|}N\hat{V}_{N,M}^{Network}-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$. Now, observe that

$\displaystyle\big{\|}N\hat{V}_{N,M}^{Network}-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}$
$\displaystyle=\Big{\|}N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}}h_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}$
$\displaystyle\qquad-N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}}\mathbbm{1}_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{\|}_{F}$
$\displaystyle=\Big{\|}N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{s\geq
0}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}h_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}$
$\displaystyle\qquad-N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{s\geq
0}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\mathbbm{1}_{m,m^{\prime}}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{\|}_{F}$
$\displaystyle=\Big{\|}N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{s=\\{0,1\\}}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\underbrace{\Big{(}h_{m,m^{\prime}}-\mathbbm{1}_{m,m^{\prime}}\Big{)}}_{0}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}$
$\displaystyle\qquad+N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\Big{(}\underbrace{h_{m,m^{\prime}}}_{1}-\underbrace{\mathbbm{1}_{m,m^{\prime}}}_{0}\Big{)}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{\|}_{F}$
$\displaystyle=\Big{\|}N\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{\|}_{F}$
$\displaystyle=\frac{N}{M}\Big{\|}\Big{(}\frac{1}{M}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{(}\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{)}\Big{(}\frac{1}{M}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\Big{)}^{-1}\Big{\|}_{F},$

where we note that $\frac{N}{M}<\infty$ by Assumption 2.1. We prove that the
inside the Frobenius norm does not converge in probability to zero.

First it can immediately be shown, by Lemma B.1 (ii), that the “bread” part
$\big{(}\frac{1}{M}\sum_{m\in\mathcal{M}_{N}}x_{m}x_{m}^{\prime}\big{)}^{-1}$
converges to
$\big{(}\frac{1}{M}\sum_{m\in\mathcal{M}_{N}}E\big{[}x_{m}x_{m}^{\prime}\big{]}\big{)}^{-1}$.

Next plugging the definition of $\hat{\varepsilon}$ into the middle part, we
have

$\displaystyle\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\hat{\varepsilon}_{m}\hat{\varepsilon}_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle=\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\big{\\{}\varepsilon_{m}+x_{m}^{\prime}(\beta-\hat{\beta})\big{\\}}\big{\\{}\varepsilon_{m^{\prime}}+x_{m^{\prime}}^{\prime}(\beta-\hat{\beta})\big{\\}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle=\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}+\varepsilon_{m}(\beta-\hat{\beta})x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}+x_{m}^{\prime}(\beta-\hat{\beta})\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}+x_{m}^{\prime}(\beta-\hat{\beta})(\beta-\hat{\beta})^{\prime}x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle=\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}+\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}(\beta-\hat{\beta})x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle\quad+\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}x_{m}^{\prime}(\beta-\hat{\beta})\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}+\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}x_{m}^{\prime}(\beta-\hat{\beta})(\beta-\hat{\beta})^{\prime}x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}.$

Denote

$\displaystyle Q_{N,1}\coloneqq\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle Q_{N,2}\coloneqq\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}(\beta-\hat{\beta})x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle Q_{N,3}\coloneqq\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}x_{m}^{\prime}(\beta-\hat{\beta})\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}$
$\displaystyle Q_{N,4}\coloneqq\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}x_{m}^{\prime}(\beta-\hat{\beta})(\beta-\hat{\beta})^{\prime}x_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}.$

From Theorem 3.1, it can be seen that $Q_{M,2}$, $Q_{M,3}$ and $Q_{M,3}$
either converge to zero or diverge as $N$ goes to infinity. When it comes to
$Q_{M,1}$, observe that

$\displaystyle E\Big{[}Q_{N,1}\Big{]}$
$\displaystyle=E\Big{[}\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}\varepsilon_{m}\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{]}$
$\displaystyle=\frac{1}{M}\sum_{s\geq
2}\sum_{m\in\mathcal{M}_{N}}\sum_{m^{\prime}\in\mathcal{M}_{N}^{\partial}(m;s)}E\Big{[}\varepsilon_{m}\varepsilon_{m^{\prime}}x_{m}x_{m^{\prime}}^{\prime}\Big{]},$

which never equals to zero due to the hypothesis (14) of this corollary. In
either case, the middle part does not converge in probability to zero, meaning
that
$\big{\|}N\hat{V}_{N,M}^{Network}-N\hat{V}_{N,M}^{Dyad}\big{\|}_{F}\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$ is not true. This, however, contradicts the implication
of the assumption that the dyadic-robust variance estimator is consistent.
Hence, by means of contradiction, we conclude that the dyadic-robust variance
estimator is not consistent, which completes the proof. $\square$

##  Appendix D Additional Monte Carlo Simulation Results

###  D.1 Summary Statistics

Table D.1 shows summary statistics (i.e., the average and maximum degrees) of
the networks across nodes that are used in our simulation study. By
construction, the maximum degree and the average degree monotonically increase
in the parameters for both specifications.

Table D.1: The Average and Maximum Degrees of Networks among Nodes in the
Simulations

|  | Specification 1 |  | Specification 2
---|---|---|---|---
$N$ |  | $\nu=1$ | $\nu=2$ | $\nu=3$ |  | $\lambda=1$ | $\lambda=2$ | $\lambda=3$
500 | $d_{max}$ | 23 | 40 | 41 |  | 5 | 7 | 8
| $d_{ave}$ | 0.8020 | 1.5780 | 2.3540 |  | 0.4760 | 0.9680 | 1.4800
1000 | $d_{max}$ | 26 | 36 | 47 |  | 4 | 7 | 8
| $d_{ave}$ | 0.8590 | 1.7000 | 2.5410 |  | 0.4980 | 0.9810 | 1.5010
5000 | $d_{max}$ | 53 | 125 | 130 |  | 6 | 9 | 10
| $d_{ave}$ | 0.9326 | 1.8618 | 2.7910 |  | 0.4952 | 1.0016 | 1.5114

  * Notes: Observation units in this table are nodes (individuals) as usual in the literature. The maximum degree, $d_{max}$, means the maximum number of nodes that are adjacent to a node, and the average degree, $d_{ave}$, is the average number of nodes adjacent to each node of the network.

Table D.2 reports the degree characteristics of the networks when viewed as
networks over the active edges. The table provides the average degree, the
maximum degree, and the number of active edges (i.e., dyads).

Table D.2: The Average and Maximum Degrees of Networks among Edges in the
Simulations

|  | Specification 1 |  | Specification 2
---|---|---|---|---
$N$ |  | $\nu=1$ | $\nu=2$ | $\nu=3$ |  | $\lambda=1$ | $\lambda=2$ | $\lambda=3$
500 | $d_{act}$ | 401 | 788 | 1175 |  | 238 | 484 | 740
| $d_{max}$ | 32 | 45 | 70 |  | 4 | 9 | 14
| $d_{ave}$ | 3.6858 | 6.0063 | 9.1881 |  | 0.9580 | 2.0248 | 3.0027
1000 | $d_{act}$ | 859 | 1699 | 2540 |  | 498 | 981 | 1501
| $d_{max}$ | 35 | 55 | 76 |  | 5 | 8 | 10
| $d_{ave}$ | 3.9581 | 6.7810 | 9.2047 |  | 1.0341 | 1.9888 | 2.9594
5000 | $d_{act}$ | 4663 | 9305 | 13952 |  | 2476 | 5008 | 7557
| $d_{max}$ | 74 | 161 | 210 |  | 7 | 12 | 15
| $d_{ave}$ | 5.2989 | 9.5159 | 12.8521 |  | 1.0137 | 2.0228 | 3.0341

  * Note: Observation units in this table are active edges (dyads), which departs from the convention. Active edges are edges that are at work in the original network over the nodes. The number of active edges is denoted by $d_{act}$. The maximum degree, $d_{max}$, expresses the maximum number of edges that are adjacent to an edge, and the average degree, $d_{ave}$, is the average number of edges adjacent to each edge of the network.

###  D.2 $S=2$ and $\gamma=0.8$

In this section, we further discuss the results of the Monte Carlo simulations
presented in the main text. The asymptotic behaviors of the three variance
estimators are illustrated in Figure D.2, where the horizontal axes represent
the sample size and the vertical axes indicate the standard error of the
regression coefficient. The boxplots show the 25th and 75th percentiles across
simulations, as well as the median, with the whiskers indicating the bounds
that are not considered as outliers. The whisker length is set to cover $\pm
2.7$ times the standard deviation of the standard-error estimates. The light-,
medium- and dark-gray boxplots describe the distribution of the Eicker-Huber-
White, the dyadic-robust and our proposed network-robust variance estimates
across simulations, respectively. The diamonds indicate the empirical standard
errors of the estimates of the regression coefficients, what Aronow et al.
(2015) call the true standard error. It is unsurprising that the empirical
standard errors are the same across different variance estimators, as we use
the same $\hat{\beta}$. The boxplots show that as the sample size increases,
the variation of the network-robust variance estimator shrinks, reaching the
empirical standard error (the diamonds). This is as expected since this
estimator is consistent for the true variance (Theorem 4.1). The estimates
appear to vary little for moderate sample sizes (e.g., $N=1000$). However, the
other variance estimators (the light- and medium-gray boxplots) converge to
lower values than the empirical standard errors (the diamonds), verifying
their inconsistency in this environment with network spillovers, as shown by
Corollary 4.1. As we make such spillovers very small (e.g., $\gamma=0.2$ in
Appendix D.3), all estimators have similar performance. This highlights the
role of condition (14): namely, the dyadic-robust variance estimator might
perform satisfactorily well as long as higher-order correlations beyond
immediate neighbors are negligible.

Figure D.2: Boxplots of Standard Errors for Specifications 1 and 2 ($S=2$,
$\gamma=0.8$)

---

  * Note: This figure shows boxplots describing the estimated standard errors and the empirical standard errors for various combinations of parameters under Specification 1 (Barabási-Albert networks) and Specification 2 (Erdös-Renyi networks). The horizontal axis shows the number of nodes and the vertical axis represents the the standard error of the coefficient. The shaded boxes represent the 25th, 50th and 75th percentiles of estimated standard errors with the whiskers indicating the most extreme values that are not considered as outliers. The light-gray box illustrates the Eicker-Huber-White standard error, the medium-gray one the dyadic-robust standard error and the dark-gray one the network-robust standard error. The diamonds stand for the empirical standard error, defined as the standard deviation of the estimates of the regression coefficient. The estimator is considered as not covering the true standard error when the diamond is outside of the shaded area.

Table D.3 describes the standard deviations of the estimated regression
coefficients (what Aronow et al. (2015) calls the true standard errors) and
the means of the estimated standard errors for each variance estimator. The
round brackets indicate the biases of each estimate relative to the true
standard error in percentage ($\%$). For instance, the Eicker-Huber-White
variance estimator and the dyadic-robust variance estimator, when applied to
Specification 1 with $\nu=3$, underestimate the true standard error by 21.45%
and 14.14%, respectively.

Table D.3: Means and Biases of the Standard Errors: $N=5000$, $S=2$,
$\gamma=0.8$.

| Specification 1 |  | Specification 2
---|---|---|---
| $\nu=1$ | $\nu=2$ | $\nu=3$ |  | $m=1$ | $m=2$ | $m=3$
True | 0.0430 | 0.0518 | 0.0570 |  | 0.0285 | 0.0283 | 0.0302
Eicker-Huber-White | 0.0337 | 0.0404 | 0.0448 |  | 0.0234 | 0.0229 | 0.0239
aaa (Bias %) | (-21.61) | (-21.92) | (-21.45) |  | (-17.91) | (-19.14) | (-20.68)
Dyadic-robust | 0.0403 | 0.0453 | 0.0490 |  | 0.0270 | 0.0266 | 0.0275
aaa (Bias %) | (-6.19) | (-12.54) | (-14.14) |  | (-5.01) | (-6.12) | (-8.93)
Network-robust | 0.0425 | 0.0509 | 0.0565 |  | 0.0280 | 0.0285 | 0.0302
aaa (Bias %) | (-1.09) | (-1.78) | (-0.92) |  | (-1.70) | (0.58) | (0.09)

  * Note: This table shows the standard deviations of the estimated regression coefficients (the true standard error) and the means of the estimated standard errors for each variance estimator with the round brackets indicating the biases relative to the true standard error in percentage ($\%$). To facilitate the comparison, the biases are rounded off to the second decimal places.

###  D.3 $S=2$ and $\gamma=0.2$

Table D.4 presents the empirical coverage probability and average length of
confidence intervals for $\beta$ at $5\%$ nominal size when $S=2$ and
$\gamma=0.2$. The associated boxplots are given in Figure D.3. Since the
magnitude of spillovers is now much smaller than the case of $\gamma=0.8$,
there are only minor differences in performance between the network-robust
variance estimator and the other two existing methods (namely, the Eicker-
Huber-White and dyadic-robust variance estimators). In terms of convergence,
the comparable performance of the dyadic-robust-variance estimator is evident
in Figure D.3.

Table D.4: The empirical coverage probability and average length of confidence
intervals for $\beta$ at $95\%$ nominal level: $S=2$, $\gamma=0.2$.

|  | Specification 1 |  | Specification 2
---|---|---|---|---
| $N$ | $\nu=1$ | $\nu=2$ | $\nu=3$ |  | $\lambda=1$ | $\lambda=2$ | $\lambda=3$
|  | Coverage Probability |
Eicker-Huber-White | 500 | 0.9286 | 0.9186 | 0.9108 |  | 0.9434 | 0.9292 | 0.9308
| 1000 | 0.9320 | 0.9158 | 0.9148 |  | 0.9338 | 0.9322 | 0.9322
| 5000 | 0.9200 | 0.9110 | 0.9124 |  | 0.9434 | 0.9382 | 0.9308
Dyadic-robust | 500 | 0.9342 | 0.9350 | 0.9336 |  | 0.9454 | 0.9368 | 0.9422
| 1000 | 0.9454 | 0.9376 | 0.9458 |  | 0.9398 | 0.9422 | 0.9486
| 5000 | 0.9446 | 0.9448 | 0.9432 |  | 0.9486 | 0.9490 | 0.9472
Network-robust | 500 | 0.9284 | 0.9246 | 0.9162 |  | 0.9428 | 0.9360 | 0.9384
| 1000 | 0.9414 | 0.9294 | 0.9370 |  | 0.9392 | 0.9410 | 0.9456
| 5000 | 0.9454 | 0.9476 | 0.9418 |  | 0.9494 | 0.9492 | 0.9470
|  | Average Length of the Confidence Intervals |
Eicker-Huber-White | 500 | 0.1578 | 0.1214 | 0.1092 |  | 0.1860 | 0.1360 | 0.1141
| 1000 | 0.1088 | 0.0846 | 0.0743 |  | 0.1290 | 0.0955 | 0.0799
| 5000 | 0.0486 | 0.0388 | 0.0346 |  | 0.0579 | 0.0423 | 0.0357
Dyadic-robust | 500 | 0.1648 | 0.1316 | 0.1213 |  | 0.1890 | 0.1410 | 0.1205
| 1000 | 0.1158 | 0.0931 | 0.0833 |  | 0.1319 | 0.0994 | 0.0848
| 5000 | 0.0532 | 0.0439 | 0.0398 |  | 0.0594 | 0.0443 | 0.0381
Network-robust | 500 | 0.1637 | 0.1291 | 0.1174 |  | 0.1885 | 0.1404 | 0.1196
| 1000 | 0.1154 | 0.0922 | 0.0825 |  | 0.1318 | 0.0993 | 0.0848
| 5000 | 0.0533 | 0.0440 | 0.0401 |  | 0.0594 | 0.0444 | 0.0382

  * Note: The upper-half of the table displays the empirical coverage probability of the asymptotic confidence interval for $\beta$, and the lower-half showcases the average length of the estimated confidence intervals. One computational issue that plagues the Monte Carlo simulation is the potential lack of positive-semi-definiteness of the estimated variance-covariance matrix. In general, this problem prevails only when the sample size ($N$) is small. In our case, when $N=500$, four variance estimates out of five thousands take negative values. We deal with this issue by first applying the eigenvalue decomposition to the estimated variance-covariance matrix and then augmenting the diagonal matrix of eigenvalues by a small constant, followed by pre- and post-multiplications by the matrix of eigenvectors to obtain the updated estimate for the variance-covariance matrix. As the sample size ($N$) increases, the empirical coverage probability approaches $0.95$, the nominal level. This convergence is accompanied by the shrinking average length of confidence intervals.

Figure D.3: Boxplots of Standard Errors for Specifications 1 and 2 ($S=2$,
$\gamma=0.2$)

  * Note: This picture shows boxplots describing the estimated standard errors and the empirical standard errors for various combinations of parameters under Specification 1 (Barabási-Albert networks) and Specification 2 (Erdös-Renyi networks). The horizontal axis shows the number of nodes and the vertical axis represents the the standard error of the coefficient. The shaded boxes represent the 25th, 50th and 75th percentiles of estimated standard errors with the whiskers indicating the most extreme values that are not considered as outliers. The light-gray box illustrates the Eicker-Huber-White standard error, the medium-gray one the dyadic-robust standard error and the dark-gray one the network-robust standard error. The diamonds stand for the empirical standard error, defined as the standard deviation of the estimates of the regression coefficient. This figure showcases the boxplots for the case when $\gamma=0.2$.

###  D.4 $S=1$

For comparison purposes, this subsection explores the results for $S=1$. If
$S=1$, there are no higher-order correlations beyond direct (adjacent)
neighbors. Then, the network-robust variance estimator ought to coincide with
the dyadic-robust variance estimator by definition, for any $\gamma$, as
pointed out in Example 2.2. This is verified below for the case of
$\gamma=0.8$. Table D.5 shows the simulation results.

Table D.5: The empirical coverage probability and average length of confidence
intervals for $\beta$ at $95\%$ nominal level: $S=1$, $\gamma=0.8$.

|  | Specification 1 |  | Specification 2
---|---|---|---|---
| $N$ | $\nu=1$ | $\nu=2$ | $\nu=3$ |  | $\lambda=1$ | $\lambda=2$ | $\lambda=3$
|  | Coverage Probability |
Eicker-Huber-White | 500 | 0.8804 | 0.8676 | 0.8734 |  | 0.8906 | 0.8768 | 0.8692
| 1000 | 0.8678 | 0.8810 | 0.8710 |  | 0.8984 | 0.8864 | 0.8856
| 5000 | 0.8752 | 0.8652 | 0.8742 |  | 0.8996 | 0.8910 | 0.8778
Dyadic-robust | 500 | 0.9292 | 0.9304 | 0.9384 |  | 0.9366 | 0.9416 | 0.9368
| 1000 | 0.9364 | 0.9426 | 0.9432 |  | 0.9428 | 0.9454 | 0.9484
| 5000 | 0.9474 | 0.9414 | 0.9498 |  | 0.9452 | 0.9518 | 0.9506
Network-robust | 500 | 0.9292 | 0.9304 | 0.9384 |  | 0.9366 | 0.9416 | 0.9368
| 1000 | 0.9364 | 0.9426 | 0.9432 |  | 0.9428 | 0.9454 | 0.9484
| 5000 | 0.9474 | 0.9414 | 0.9498 |  | 0.9452 | 0.9518 | 0.9506
|  | Average Length of the Confidence Intervals |
Eicker-Huber-White | 500 | 0.3282 | 0.2901 | 0.2881 |  | 0.2664 | 0.2377 | 0.2235
| 1000 | 0.2321 | 0.2088 | 0.1964 |  | 0.1887 | 0.1665 | 0.1564
| 5000 | 0.1131 | 0.1042 | 0.0980 |  | 0.0844 | 0.0742 | 0.0704
Dyadic-robust | 500 | 0.3934 | 0.3591 | 0.3603 |  | 0.3104 | 0.2888 | 0.2776
| 1000 | 0.2853 | 0.2625 | 0.2500 |  | 0.2227 | 0.2037 | 0.1950
| 5000 | 0.1428 | 0.1330 | 0.1259 |  | 0.0998 | 0.0913 | 0.0882
Network-robust | 500 | 0.3934 | 0.3591 | 0.3603 |  | 0.3104 | 0.2888 | 0.2776
| 1000 | 0.2853 | 0.2625 | 0.2500 |  | 0.2227 | 0.2037 | 0.1950
| 5000 | 0.1428 | 0.1330 | 0.1259 |  | 0.0998 | 0.0913 | 0.0882

  * Note: The upper-half of the table displays the empirical coverage probability of the asymptotic confidence interval for $\beta$, and the lower-half showcases the average length of the estimated confidence intervals. As the sample size ($N$) increases, the empirical coverage probability approaches $0.95$, the nominal level. This convergence is accompanied by the shrinking average length of confidence intervals.

##  Appendix E Additional Information for the Empirical Illustration

###  E.1 Seating Arrangement at the European Parliament

Figure E.4 exhibits an example of the seating arrangement at the European
Parliament, and describes how we construct an adjacency relationship among
MEPs within their EPG groups.

Figure E.4: Seating Plan at the European Parliament: Strasbourg, September 14,
2009

ALDE PPE Row 10 $\cdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$\cdots$ Row 9 $\cdots$ Seat 36: Seat 37: Seat 38: Seat 39: Seat 40: Seat 41:
$\cdots$ ALFANO ALVARO CAVADA COELHO COLLINO COMI Row 8 $\cdots$ Seat 32: Seat
33: Seat 34: Seat 35: Seat 36: $\cdots$ OJULAND OVIIR BACH BALDASSARRE BALZ
Row 7 $\cdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\cdots$
---

  * Note: Panel (A) illustrates a zoomed-out view of a seating plan for the European parliament in Strasbourg on September 14, 2009. gray circles are individual MEPs, while black circles embody members of conseil and commission. The associated party (EPG) is denoted at the top. Panel (B) provides a zoomed-in view elaborating on the part of Panel (A) marked by the dotted trapezoid shaded in gray. Alafano and Alvaro are treated as adjacent because they are sitting next to each other and belong to the same political party, i.e., ALE. Similarly, Ojuland and Oviir are considered to be adjacent. On the other hand, following the original authors, Alvaro and Cavada are not regarded as adjacent though they are seated together because they belong to different political parties, i.e., ALE and PPE, respectively. In terms of dyad-level adjacency, Cavada-Coelho and Coelho-Collino are adjacent dyads as they share Coelho, whereas Cavada-Coelho and Collino-Comi are not adjacent, but they are still connected as they have indirect paths to one another along the dyadic network.

###  E.2 Data Construction

Data construction for our empirical exercise in Section 6 proceeds in multiple
steps:

Step 1:

Our subsample consists of the location of interest (i.e., Strasbourg) for the
period of interest (i.e., Term 7). We select a further subset of the extracted
data by seating arrangement (i.e., we focus on Pattern 1 for the present
analysis - see Table E.6).

Step 2:

Since our analysis is concerned with voting concordance, we follow the
original authors in dropping entries with missing data or “abstain” in the
variable “vote.”363636This amounts to assuming that those observations are
missing completely at random (MCAR).

Step 3:

The resulting data still contains individuals belonging to “Identity,
Tradition and Sovereignty (ITS),” one of the European Political Groups that
dissolved in November 7, during the sixth term. We drop such MEPs from our
analysis.

Step 4:

The selected data is used to form the dyadic data registering the pair-of-
MEPs-specific information. When pairing two MEPs, we follow Harmon et al.
(2019) in focusing on those pairs of MEPs, both of whom are

  * (i)

in the same EPG;

  * (ii)

from an alphabetically-seated EPG; and

  * (iii)

non-leaders at the time of voting.

Our dyadic data consists of two types of variables: binary variables and
numerical variables. The dyad-level binary (i.e., indicator) variables are
defined to be one if the individual-level binary variables are the same, and
zero otherwise. The dyadic-specific numerical variables in our analysis are
the differences between the individual-level numerical variables, such as age
and tenure. When calculating the differences in ages and tenures, we take the
absolute values as we do not consider directional dyads, and we then rescale
them into ten-year units. See the note below Table 2 for details.

Table E.6: Patterns of Seating Arrangements: Strasbourg, Term 7

Pattern | Date | Number of Proposals
---|---|---
1 | 7/14/2009 | $\sim$ | 7/16/2009 | 116
2 | 8/18/2009 | $\sim$ | 8/21/2009 | 72
3 | 9/23/2009 | $\sim$ | 9/25/2009 | 114
4 | 10/13/2009 | $\sim$ | 10/16/2009 | 40
5 | 11/19/2009 | $\sim$ | 12/11/2009 | 94
6 | 1/5/2010 | $\sim$ | 1/8/2010 | 79
7 | 3/17/2010 | $\sim$ | 3/19/2010 | 45
8 | 4/14/2010 | $\sim$ | 4/16/2010 | 120
9 | 5/5/2010 | $\sim$ | 5/7/2010 | 79
10 | 7/7/2010 | $\sim$ | 7/9/2010 | 34
11 | 7/21/2010 | $\sim$ | 7/22/2010 | 50
12 | 8/18/2010 | $\sim$ | 8/20/2010 | 118

  * Note: This table presents patterns of seating arrangements with the corresponding dates and the number of total observations for each pattern. Since voting may be taken place for multiple proposals within the same day, the total number proposals tends to be higher than that of days in a single pattern. For example, the first line indicates that 116 proposals were discussed and votes were cast over the three days (from the 14th of July, 2009 to the 16th of July, 2009).

###  E.3 Full Results

Table E.7 reports the detailed result of the empirical illustration. As
explained in Section 6.3, Panel A reports the estimates of the parameter of
interest, while Panel B lists the standard errors based on the different
variance estimators. Panel C collects the parameter estimates for other
covariates accompanied by the standard errors obtained from our proposed
variance estimator from equation (7), and indicates the presence or absence of
day-level fixed effects.

Table E.7: Spillovers in Legislative Voting – Main Analysis

| Specification (I) | Specification (II) | Specification (III)
---|---|---|---
Panel A: Parameter estimates for Seat neighbors |  |  |
Seat neighbors | 0.0069 | 0.0060 | 0.0060
Panel B: Standard errors for Seat neighbors |  |  |
Eicker-Huber-White | 0.0031 | 0.0030 | 0.0030
Dyadic-robust | 0.0075 | 0.0082 | 0.0087
Network-robust | 0.0095 | 0.0104 | 0.0112
Panel C: Parameter estimates for other covariates |  |  |
Same country |  | 0.0561 | 0.0562
|  | (0.0008) | (0.0008)
Same quality education |  | 0.0030 | 0.0028
|  | (0.0007) | (0.0007)
Same freshman status |  | -0.0070 | -0.0070
|  | (0.0008) | (0.0008)
Same gender |  | 0.0004 | 0.0004
|  | (0.0007) | (0.0006)
Age difference |  | 0.0007 | 0.0004
|  | (0.0004) | (0.0004)
Tenure difference |  | -0.0149 | -0.0149
|  | (0.0006) | (0.0006)
Day-level FE | No | No | Yes

  * Note: Panel A displays the parameter estimates for the three different specifications; Panel B shows the standard errors for the regression coefficient of SeatNeighbors using different variance estimators; and Panel C collects the parameter estimates for other covariates accompanied by the standard errors obtained from our proposed variance estimator from equation (7), and indicates the presence or absence of day-level fixed effects. Adjacency of MEPs is defined at the level of a row-by-EP-by-EPG. (See the note below Figure E.4.) Independent variables are as follows: Seat neighbors is an indicator variable denoting whether both MEPs sit together; Same country represents an indicator for whether both MEPs are from the same country; Same quality education is an indicator showing whether both MEPs have the same quality of education background, measured by if both have the degree from top 500 universities; Same freshman status encodes whether both MEPs are freshman or not; Age difference is the difference in the MEPs’ ages; and Tenure difference measures the difference in the MEPs’ tenures.