Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Introduction

Much of probabilistic combinatorics deals with questions of the following type:

Given a probability distribution over “large” combinatorial objects $X$ and a real-valued parameter $P=P(X)$ defined over such objects, does there exists a typical value $P^{\rm typ}$ such that $P(X)$ is very likely to be close to $P^{\rm typ}$?

Starting with the seminal work of Shamir and Spencer on the chromatic number of $G_{n,p}$, many answers to instances of the above question have been obtained via concentration inequalities, and developments in the two fields have often gone hand in hand; see and the references therein for many examples.

In this paper we introduce a new concentration inequality for random Hermitian matrices in order to address a variant of Question 1.1. Our combinatorial objects consist of random graphs with independent edges. These are random graphs where the events “$ij$ is an edge” (with $ij$ varying over all unordered pairs of vertices) are independent, but not necessarily identically distributed. The new twist is that the “parameters” for which we prove concentration are the adjacency matrix and the graph Laplacian of the resulting graph (defined in Section 2.3).

We briefly recall why these two matrices are important. Many (real-valued) parameters of a graph can be computed and/or estimated from these two matrices, including the diameter, distances between distinct subsets, discrepancy-like properties, path congestion, chromatic number and the mixing time for random walk; see e.g. for a compendium of these results, for the relationship between the two matrices and “pseudo-random” properties of graphs and for algorithmic applications. Given these facts, our main Theorem (stated below) sheds some light on the typical properties of the corresponding random graph models.

Let ${\sf G}_{\bf p}$ be a random graph on vertex set $[n]$ where each potential edge $ij$, $1\leq i\leq j\leq n$ appears with probability ${\bf p}(i,j)$. Let $A_{\bf p}$ and $\mathcal{L}_{\bf p}$ be the adjacency matrix and graph Laplacian of ${\sf G}_{\bf p}$ and $A_{\bf p}^{{\rm typ}}$ and $\mathcal{L}_{\bf p}^{{\rm typ}}$ be the adjacency matrix and Laplacian of the weighted graph ${\sf G}_{\bf p}^{{\rm typ}}$ where $ij$ has weight ${\bf p}(i,j)$ for each pair $ij$. Define $d$, $\Delta$ as the minimum and maximal weighted degrees in ${\sf G}_{\bf p}^{{\rm typ}}$. Then there exists a universal constant $C>0$ such that if $\Delta\geq C\ln n$,

A more precise quantitative statement of Theorem 1.1 is given in Section 3 below.

Theorem 1.1 is related to several known results about the standard Erdös-Rényi graph $G_{n,p}$ (the special case where ${\bf p}(i,j)=p$ for $i\neq j$). We will show in Section 4 that the kind of matrix concentration we prove here is implicit in the literature and that the standard notion of quasi-randomness for dense graphs can be reformulated in terms of concentration of the adjacency matrix around the “typical matrix” for the corresponding $G_{n,p}$ model. There is also a relationship between concentration of the Laplacian and quasi-randomness for given degree sequences which is briefly discussed in Section 4.1.

For the special cases just described, the bounds obtained from Theorem 1.1 for the Laplacian are qualitatively sharp, in the sense that they becomes trivial at roughly the same point where one cannot expect concentration to hold. However, more specialized (and much more complex) approaches yield improved bounds . In some sense, this is due to the fact that the typical adjacency matrices and Laplacians for such random graph models turn out to be very degenerate: one of the eigenvalues of each matrix has multiplicity $n-1$, and the other eigenvalue is well separated from the first.

The cases where this does not happen turn out to be more interesting. For instance, consider the case of bond percolation with a parameter $p\in(0,1)$ on an arbitrary $n$-vertex graph $G$. That is, we consider a random subgraph $G_{p}$ of $G$ that is obtained by retaining each edge of $G$ independently with probability $p$. Let $A$ be the adjacency matrix and $\mathcal{L}$ be the Laplacian of $G$ (respectively). We will show that when the minimum expected degree in $G_{p}$ is $\omega(\ln n)$, the adjacency matrix and Laplacian of $G_{p}$ are close to $pA$ and $\mathcal{L}$ (respectively); therefore, any estimate for $G$ derived from $\mathcal{L}$ continues to hold (at least approximately) for the random subgraph. A simple corollary of our Theorem is a bound for the spectral gap of $G_{p}$ that improves upon a recent result of Chung and Horn , derived via much more complicated methods.

Not much is known in general about such inequalities. This is in sharp contrast with the scalar case, where there are several remarkable inequalities and many techniques to prove them . The concentration results for random matrices that have been proven correspond to relatively old developments in the scalar case, such as the standard bounds due to Chernoff and Hoeffding , as well as Khintchine’s inequality . Accordingly, the new concentration result we introduce in this paper is a matrix analogue of Freedman’s inequality for martingale sequences , which dates back to the 1970’s. Here is a precise statement. [Measurability and conditional expectations are defined entrywise; see Section 2.4 for this and other definitions.]

Compared with Freedman’s original bound, Theorem 1.2 has worse constants in the exponent and an extra $d$ factor (which is necessary; cf. Section 8), but the two bounds are otherwise of the same form. In this paper we only need a version of Theorem 1.2 for independent sums (cf. Remark 7.1 and Corollary 7.1), but the martingale inequality is not any harder to prove.

The proof of Theorem 1.2 follows a methodology first proposed by Ahlswede and Winter . These authors proved a version of the Chernoff bound for matrices which has had a very strong impact on the development of Quantum Information Theory . Christofides and Markström used the same method to obtain a version of Hoeffding’s inequality for matrix martingales.

In the setting of Theorem 1.2, replace the assumption on $\|Z_{i}-Z_{i-1}\|$ by the assumption that there exist $0\leq r_{i}\leq 1$ such that $\lambda_{\max}(Z_{i}-Z_{i-1})\leq 1-r_{i}$ and $\lambda_{\max}(Z_{i-1}-Z_{i})\leq r_{i}$. Then for all $t>0$,

where $R=\sum_{i=1}^{n}r_{i}/n$ and for $x,r\in$

As we will see in Remark 3.1, this bound would not suffice for our applications. Roughly speaking, our Theorem is better because the variance term in our bound is the largest value of a sum of matrices, not the sum of the largest eigenvalues. In that respect, Theorem 1.2 is closer to an influential bound obtained by Rudelson via certain inequalities from non-commutative probability . The Ahlswede-Winter approach we adopt here has the advantage of requiring no such unfamiliar tools.There is now a proof of Rudelson’s bound along the lines of the Ahlswede-Winter method; see for details and for further discussion on the difference between the three bounds.

Theorem 1.2 should also be contrasted with other ways for controlling eigenvalues and eigenvectors of random matrices. One of them is the “trace method” which consists of analyzing traces of high powers of the matrices under consideration. This method can be very sharp, but it is also quite complex and we will see that we obtain better bounds in one context (but not all contexts) where the trace method has been applied. A more recent way of bounding eigenvalues and eigenvectors is in some sense based on bounding “discrepancies” . This is better than our bound when the technique applies (see e.g. the comments in Section 4.1), but our main applications seem to be beyond the reach of this methodology.

Finally, we note that our result is not quite comparable concentration bounds of Alon, Krivelevich and Vu for the largest eigenvalues of a random symmetric matrix. Our bound is poorer than theirs when applied to $k$-th largest eigenvalue for any fixed $k$, but their bound quickly deteriorates when $k$ grows, whereas our result bounds the maximal deviation of all eigenvalues simultaneously (cf. Corollary 3.1), as well as the deviation of eigenspaces (cf. Corollary 3.2). Moreover, their result cannot be used to determine the typical value of each eigenvalue.

2 Organization

The remainder of the paper is organized as follows. After the preliminary Section 2, we prove the main concentration result in Section 3. As a test case, we apply our results to the Erdös-Rényi random graph Section 4 where the connection with quasi-randomness is also discussed. Bond percolation is discussed in Section 5. The more complicated case of inhomogeneous random graphs is treated in Section 6, where we also compare our results to what is known about graph limits. The new concentration inequality is proven in Section 7. Some final remarks are made in Section 8. The Appendix contains two simple results on the perturbation theory of compact operators for which we did not find adequate references.

Preliminaries

We also note an equivalent statement of the spectral theorem as:

where the $\{\Pi_{\alpha}\}_{\alpha\in{\rm spec}(A)}$ are projections with orthogonal ranges and $\sum_{\alpha\in{\rm spec}(A)}\Pi_{\alpha}=I_{d}$, the $d\times d$ identity matrix. The multiplicity of $\alpha\in{\rm spec}(A)$ is the dimension of the range of the corresponding $\Pi_{\alpha}$; this is equal to the number of $0\leq i\leq d-1$ with $\lambda_{i}(A)=\alpha$.

In Section 6 we will compare adjacency matrices with certain integral operators on $L^{2}()$. The spectral theory of these and other compact operators is a classical topic in Functional Analysis and we refer to for all the results we review in this Section.

We will work with the space $L^{2}()$ of real measurable functions that are square-integrable with respect to Lebesgue measure. This space has a natural inner product

and an associated norm $\|f\|_{L^{2}}^{2}\equiv(f,f)_{L^{2}}$ with respect to which it is a real Hilbert space.

Given a function $\eta\in L^{2}(^{2})$ (the latter space being defined similarly to $L^{2}()$), one can define a linear operator on $L^{2}()$ by the formula:

The “$L^{2}\to L^{2}$” norm of a linear operator $V$ from $L^{2}()$ to itself is given by:

It is an exercise to show via the Cauchy Schwartz inequality that:

Assume that $\eta(x,y)=\eta(y,x)$ for almost every $(x,y)\in$ (i.e. $\eta$ is symmetric). In that case the operator $T_{\eta}$ is a compact, self adjoint linear operator on the Hilbert space $L^{2}()$.

3 Concepts from Graph Theory

For our purposes a graph $G=(V,E)$ consists of a finite set $V$ of vertices and a set $E$ of edges, which are subsets of size $1$ (loops) or $2$ of $V$ (we do not allow for parallel edges). Unless otherwise noted, we will assume that $V=[n]$ for some integer $n\geq 2$, where $[n]\equiv\{1,2,\dots,n\}$. We will write edges as pairs $ij$ (allowing for $i=j$), but we make no distinction between $ij$ and $ji$. We will also write $i\sim_{G}j$ to mean that $ij\in E$. The degree $\mbox{d}_{G}(i)$ of a vertex $i$ is the number of $1\leq j\leq n$ such that $ij\in E$.

Assume that $V=[n]$. The adjacency matrix of $G$ is the $n\times n$ matrix $A=A_{G}$ such that, for all $1\leq i,j\leq n$, the $(i,j)$-th entry of $A$ is $1$ if $ij\in E$ and otherwise. The Laplacian $\mathcal{L}=\mathcal{L}_{G}$ of $G$ is the matrix:

where $T$ is the $n\times n$ diagonal matrix whose $(i,i)$-th entry is $\mbox{d}_{G}(i)^{-1/2}$ if $\mbox{d}_{G}(i)\neq 0$, or if $\mbox{d}_{G}(i)=0$. We also let

We will also consider weighted graphs, which correspond to a graph $H=(V^{\prime},E^{\prime})$ where a positive weight $w_{e}>0$ is assigned to each edge $e\in E$. This is the same as defining a symmetric function $w:(V^{\prime})^{2}\to[0,+\infty)$ (i.e. $w(i,j)=w(j,i)\geq 0$ for all $i,j\in V$) and setting $E^{\prime}=\{\{i,j\}\,:\,w(i,j)>0\}$. In this case, the degree of $i\in V^{\prime}$ is defined as

Assume $V^{\prime}=[m]$. The adjacency matrix of such an $H$ is the $m\times m$ matrix $A_{H}$ where for each $1\leq i,j\leq m$ the $(i,j)$-th entry of $A_{H}$ is $w(i,j)$. The Laplacian $\mathcal{L}_{H}$ is defined as

where $T_{H}$ is defined as before, but with the new notion of degree. The definition of $\lambda(H)$ is the same as for unweighted graphs.

4 Probability with matrices

If the entries are also square-integrable, one can define the variance by the usual formula,

We will need two easily checked properties of matrix (conditional) expectations, valid for all integrable random $d\times d$ Hermitian matrices $X$ and $Y$ and any sub-$\sigma$-field $\mathcal{G}\subset\mathcal{F}$:

Concentration of graph matrices

In this section we state and prove our main result, Theorem 1.1.

We also define $I_{ji}=I_{ij}$ for $j>i$.

Define a random unweighted graph ${\sf G}_{\bf p}$ with vertex set $[n]$ and edge set

Let $A_{\bf p}$ and $\mathcal{L}_{\bf p}$ be the adjacency matrix and Laplacian of the graph ${\sf G}_{\bf p}$. We will compare these to the corresponding matrices $A_{\bf p}^{{\rm typ}}$, $\mathcal{L}_{\bf p}^{{\rm typ}}$ of the weighted graph ${\sf G}_{\bf p}^{{\rm typ}}$ defined by the function ${\bf p}$.

The following is a more precise statement of Theorem 1.1.

For any constant $c>0$ there exists another constant $C=C(c)>0$, independent of $n$ or ${\bf p}$, such that the following holds. Let $d\equiv\min_{i\in[n]}\mbox{d}_{{\sf G}_{\bf p}^{{\rm typ}}}(i)$, $\Delta\equiv\max_{i\in[n]}\mbox{d}_{{\sf G}_{\bf p}^{{\rm typ}}}(i)$. If $\Delta>C\ln n$, then for all $n^{-c}\leq\delta\leq 1/2$,

Moreover, if $d\geq C\ln n$, then for the same range of $\delta$:

We will quickly derive some corollaries before we prove Theorem 3.1.

Therefore, the RHS holds with probability $\geq 1-\delta$ for any $n^{-c}<\delta<1/2$ if $\Delta\geq C\ln n$. Similarly,

and the RHS holds with probability $\geq 1-\delta$ for all $\delta$ as above if $d\geq C\ln n$.

Given some $\gamma>0$, let $N_{\gamma}(A_{\bf p}^{{\rm typ}})$ be the set of all pairs $a<b$ such $a+\gamma<b-\gamma$ and $A_{\bf p}^{{\rm typ}}$ has no eigenvalues in $(a-\gamma,a+\gamma)\cup(b-\gamma,b+\gamma)$. Then for $\gamma>4\,\sqrt{\Delta\,\ln(n/\delta)}$,

In particular, the RHS holds with probability $\geq 1-\delta$ for any $n^{-c}<\delta<1/2$.

Define $N_{\gamma}(\mathcal{L}_{\bf p}^{{\rm typ}})$ similarly. Then for $\gamma>14\sqrt{{\ln(4n/\delta)/d}}$,

In particular, the RHS holds with probability $\geq 1-\delta$ for any $n^{-c}<\delta<1/2$.

The upshot is that for any range of eigenvalues of $A_{\bf p}^{{\rm typ}}$ (resp. $\mathcal{L}_{\bf p}^{{\rm typ}}$) that are well-separated from the rest of the spectrum, the projection onto the corresponding eigenvectors of $A$ (resp. $\mathcal{L}$) will be typically close to that of $A_{\bf p}^{{\rm typ}}$ (resp. $\mathcal{L}_{\bf p}^{{\rm typ}}$)Of course, there is not much one can do near eigenvalue degeneracies, where eigenvectors are typically unstable.. We will see when dealing with inhomogeneous random graphs that the separation conditions demanded by the corollary are satisfied in non-trivial cases.

One can check that $A_{\bf p}=\sum_{1\leq i\leq j\leq n}I_{ij}\,A_{ij}$ and $A_{\bf p}^{{\rm typ}}=\sum_{1\leq i\leq j\leq n}{\bf p}(i,j)A_{ij}$. Therefore,

as the eigenvalues of $A_{ij}$ are always contained in the set $\{1,0,-1\}$ . Thus the assumptions of the Corollary apply with $M=1$, but we still need to compute the sum of the variances. For this, fix some pair $ij$ and note that:

This is a diagonal matrix and its largest eigenvalue is at most

One can now apply Corollary 7.1 with $\sigma^{2}=\Delta$ and $M=1$ to obtain:

Now let $c>0$ be given and assume $n^{-c}\leq\delta\leq 1/2$. Then it is clear that there exists a $C=C(c)$ independent of $n$ and ${\bf p}$ such that whenever $\Delta\geq C\ln n$,

This proves the first inequality in Theorem 3.1.

In order to prove the second inequality, we again fix $n^{-c}\leq\delta\leq 1/2$. Our first task is to control the vertex degrees in ${\sf G}_{\bf p}$. Notice that for each $1\leq i\leq n$, $\mbox{d}_{{\sf G}_{\bf p}}(i)=\sum_{j=1}^{n}I_{ij}$ is a sum of independent indicator random variables and the mean of that sum is $\mbox{d}_{{\sf G}_{\bf p}^{{\rm typ}}}(i)\geq d$. Standard Chernoff bounds (or the case $d=1$ of our own Corollary 7.1!) imply that there exists a value of $C=C(c)$ such that for $d\geq C\ln n$,

Thus with probability $\geq 1-\delta/2$ one has that

We will use this inequality to compare the matrices

By increasing $C$ if necessary (and recalling that $\delta>n^{-c}$, $d>C\ln n$), we can ensure that the RHS of (3.5) is at most $3/4$. By the Mean Value Theorem for any $x\in[-3/4,3/4]$:

We now wish compare $\mathcal{L}_{\bf p}=I-TA_{\bf p}T$ to $\mathcal{L}_{\bf p}^{{\rm typ}}=I-T_{\rm typ}A_{\bf p}^{{\rm typ}}T_{\rm typ}$. Introduce an intermediate operator:

The spectrum of any Laplacian lies in $$; this implies$\|I-\mathcal{L}_{\bf p}\|\leq 1$. Using this in conjunction with (3.6) yields:

where again we increase $C$ if necessary to ensure that $d\geq C\ln n$ and $\delta>n^{-c}$ imply the desired bound.

To finish the proof, we must show that $\|\mathcal{M}-\mathcal{L}_{\bf p}^{{\rm typ}}\|\leq 4\,\sqrt{\ln(4n/\delta)/d}$ with probability $\geq 1-\delta/2$. For this we will use the concentration result, Corollary 7.1. One can write:

where the $X_{ij}$ are the same matrices from the first part of the proof (cf. (3.1)). Again we have a sum of mean- independent random matrices, in this case:

In all possible cases, the eigenvalues of $Y_{ij}$ are contained in the set:

Again we have a diagonal matrix. Its $(i,i)$-th entry is at most:

We may thus apply Corollary 7.1 to $\sum_{ij}Y_{ij}$ with $M=\sigma^{2}=1/d$ to obtain:

We have already ensured that $t\leq 3/4\leq 2$. This implies

This was precisely the required bound. $\Box$

We now explain why the Hoeffding bound of Christofides and Markström is insufficient for our purposes. In the case of the adjacency matrix, the random sum we deal with is $\sum_{ij}(I_{ij}-{\bf p}(i,j))A_{ij}$. We observed above that $A_{ij}$ has eigenvalues $1$, $-1$ and , hence we would have to take $r_{i}=1/2$ in order to apply Theorem 1.3 to $(A_{\bf p}-A_{\bf p}^{{\rm typ}})/2$. A simple calculation shows that the exponent in that bound would be of the order $-t^{2}/\binom{n}{2}$ for small enough $t$, which is much worse than the $-t^{2}/\Delta$ behavior we obtain. Our improvement comes from the fact that our “variance” term is the largest eigenvalue of a sum, not the sum of largest eigenvalues. Similar comments apply to the concentration of the Laplacian.

The Erdös-Rényi graph and quasi-randomness

As a first illustration of Theorem 3.1, we apply our results to the Erdös-Rényi graphs. Our bounds are suboptimal in this very special case, but the stronger results in require more difficult arguments that do not seem to generalize to other cases of bond percolation (cf. Section 5). Moreover, our result correctly predicts the range of $p$ for which one can expect concentration of the adjacency matrix.

We then connect concentration to the theory of quasi-randomness for dense graphs showing that, in a certain sense, quasi-randomness is equivalent to concentration of the adjacency matrix.

While we will not dwell on this point, a similar connection could be presented between random graphs with given expected degrees and concentration of the Laplacian. Our bounds are also suboptimal in this setting, as attested by a recent preprint of Coja-Oghlan and Lanka .

The following result is immediate from Theorem 3.1

This result is qualitatively sharp in the sense that one cannot expect that the Laplacian concentrates when $pn\ll\ln n$. To see this, recall that the multiplicity of in the spectrum of $\mathcal{L}_{n,p}$ is the number of connected components of $G_{n,p}$ (this is a deterministic statement; cf. ). If $pn\leq\ln n$, the probability of there being $2$ or more components is bounded away from . But if has multiplicity $\geq 2$, (3.1) implies that $\|\mathcal{L}_{n,p}-(I_{n}-{\bf 1}_{n}{\bf 1}_{n}^{*}/n)\|\geq 1$, therefore $\mathcal{L}_{n,p}$ is far from the “typical Laplacian” with positive probability.

Quantitatively, the bounds in Proposition 4.1 can be improved. We quickly sketch the argument for the adjacency matrix, which is implicit in the work of Feige and Ofek . A key idea is that, since the typical adjacency matrix $p({\bf 1}_{n}{\bf 1}_{n}^{*}-I_{n})$ has one very large eigenvalue and lots of small ones, the same should hold for $A_{n,p}$.

One can use the reasoning in [33, Lemma 2.1] to show that, for $pn=\Omega\left(\ln n\right)$ the dominant eigenvector of $A_{n,p}$ is always close to ${\bf 1}_{n}/\sqrt{n}$. Moreover, the largest eigenvalue is $pn+O\left(\sqrt{pn}\right)$ and all other are of the order $O\left(\sqrt{pn}\right)$ . This shows that, with probability $\geq 1-\delta/2$

2 Quasi-randomness as concentration of the adjacency matrix

We now point out that the idea of concentration of the adjacency matrix is implicit in the theory of dense quasi-random graphs

This theory was initiated by Chung, Graham and Wilson . Their surprising discovery was that several properties that a Erdös-Rényi random graph is very likely to have are in fact equivalent.

[Q1] There exists a $s\geq 4$ such that for all $0\leq k\leq\binom{s}{2}$, $G_{m}$ contains more than $p^{-k}(1-p)^{\binom{s}{2}-k}n_{m}^{s}$ induced labeled copies of each graph on $s$ vertices and $k$ edges.

[Q2] $G_{m}$ has $\geq(1+o\left(1\right))pn_{m}^{2}/2$ edges and $\leq(1+o\left(1\right))(pn_{m})^{4}$ labeled copies of the four-cycle $C_{4}$.

[Q3] $G_{m}$ has $\geq(1+o\left(1\right))pn_{m}^{2}/2$ edges, the largest eigenvalue of $A_{m}$ is $(1+o\left(1\right))pn$ and all other eigenvalues of $A_{m}$ are $o\left(n\right)$ in absolute value.

[Q4] $\max_{S\subset V_{m}}|e(S)-p|S|^{2}/2|=o\left(n_{m}^{2}\right)$ where $e(S)$ is the number of edges of $G_{m}$ inside $S$ and $V_{m}$ is the vertex set of $G_{m}$.

We now provide a characterization of quasi-randomness in terms of “concentration” of the adjacency matrix. Let

The following result shows that a sequence of graphs is quasi-random if and only if the adjacency matrices of the graphs are sufficiently close to $A^{\rm typ}_{m}$.

A sequence $\{G_{m}\}_{m}$ of graphs as above satisfies properties [Q1]-[Q4] above if and only if:

Proof: [of Proposition 4.2] We will show that [P1] is equivalent to [Q3] in the previous list.

[P1]$\Rightarrow$[Q3] : The eigenvalues of $A^{\rm typ}_{m}$ are $p(n_{m}-1)$ (with multiplicity $1$) and $-p$ (with multiplicity $n_{m}-1$).

We use inequality (3.1) above to deduce that:

Moreover, the number of edges in $G_{m}$ is:

[Q3]$\Rightarrow$[P1]: It is immediate from [Q3] that $A_{m}$ is $o\left(n\right)$-close to a rank-one operator: if $\psi_{\max}$ is the (normalized) eigenvector corresponding to the largest eigenvalue $\lambda_{\max}(A_{m})$, then:

It is shown in the proof of Fact 7 in that, under [Q3], $\psi_{\max}$ is $o\left(1\right)$-close to ${\bf 1}_{n_{m}}/\sqrt{n_{m}}$. Thus we see that:

Putting all the inequalities together implies the desired result. $\Box$

Application to bond percolation

In the previous section we discussed a random graph model where the typical Laplacian and adjacency matrices had one “special” eigenvalue with multiplicity $1$ and $n-1$ “trivial” eigenvalues. In this setting, proving concentration of the adjacency matrix (say) essentially amounted to showing that one eigenvector was close to what it should be while the other eigenvalues clustered around the degenerate eigenvalue of the typical case.

We now consider a class of models for which one cannot expect this strategy to work. Let $p\in(0,1)$ and $G=(V,E)$ be an arbitrary unweighted graph on vertex set $V=[n]$. Consider the random subgraph $G_{p}$ of $G$ that is obtained via by deleting each edge of $G$ independently with probability $1-p$. This model of bond percolation has received much attention in recent years, with a special focus the emergence of a giant component . Much less seems to be known about the spectrum of $G_{p}$ .

In this section we apply our general Theorem, Theorem 3.1, in order to answer the following question: how large does $p$ need to be in order for the graph matrices to concentrate? Clearly, this must occur way after the percolation threshold.

Bond percolation is a special case of the random model ${\sf G}_{\bf p}$ in Section 3. To see this, one only needs to define:

A computation shows that the “typical matrices” for this choice of ${\bf p}$ are:

Moreover, the parameters $d$, $\Delta$ appearing in Theorem 3.1 are $pd_{G}$ and $p\Delta_{G}$, where $d_{G}$ (resp. $\Delta_{G}$) is the minimum (resp. maximal) degree in $G$.

The following result is a direct corollary of Theorem 3.1.

For each $c>0$ there exists a $C>0$ such that the following holds. Suppose that $G$, $p$ and $G_{p}$ are as above and $pd_{G}\geq C\,\ln n$. Then:

where $A_{G_{p}}$ and $\mathcal{L}_{G_{p}}$ are the adjacency matrix and Laplacian of $G_{p}$ (resp.)

One can of course derive corollaries about eigenvectors and eigenvectors following Corollaries 3.1 and 3.2. For instance, suppose that:

Then the following holds with probability $1-\delta$: for each $0\leq i\leq n-1$ such that the interval $(\lambda_{i}(\mathcal{L}_{G})-2\gamma,\lambda_{i}(\mathcal{L}_{G})+2\gamma)$ contains no eigenvalues of $\mathcal{L}_{G}$ other than $\lambda_{i}(\mathcal{L})$, $\lambda_{i}(\mathcal{L}_{G_{p}})$ has multiplicity $1$ in the spectrum of $\mathcal{L}_{G_{p}}$ and moreover, the corresponding normalized eigenvectors $\psi$, $\psi_{p}$ of $\mathcal{L}_{G}$ and $\mathcal{L}_{G_{p}}$ (resp.) satisfy:

with probability $\geq 1-\delta$. This implies:

for the same eigenvectors, which implies that $\psi_{p}$ is close to $\psi$ or $-\psi$. A similar result for the eigenspace projectors could be derived even if $\lambda_{i}(G)$ had higher multiplicity. It seems quite remarkable that one can approximately obtain the eigenvectors or eigenspaces of $G$ from a (potentially very sparse) subgraph $G_{p}$.

We also note that the threshold for Laplacian concentration is indeed $pd_{G}=\Theta\left(\ln n\right)$, as shown in Section 4.1 in the special case of the Erdös-Rényi random graph $G_{n,p}$.

The following simple corollary is also of interest.

There exist $C,C^{\prime}>0$ such that, if $pd_{G}\geq C\ln n$, then with probability $1-1/n^{2}$,

We have singled out this bound in order to compare it with a recent bound of Chung and Horn . These authors proved that, with high probability,

Our bound is better for all values of $n$ and $pd_{G}$, most dramatically for $\ln n\ll pd_{G}\ll\ln^{3/2-\epsilon}n$, in which case their bound is vacuous while ours is non-trivial.

Application to inhomogeneous random graphs

In this section we consider a more complex random graph model that is defined in terms of an attachment kernel $\kappa$, a density parameter $0<p<1$ and a set of points $X_{1},X_{2},\dots,X_{n}$.

One can define a random graph ${\sf G}_{\bf p}$ as in Section 3 with the above weight function; we call this graph $G_{n,p,\kappa}$, the inhomogeneous random graph on $n$ vertices, density parameter $p$ and attachment kernel $\kappa$ (the dependency on $X_{1:n}$ is implicit in this nomenclature). The adjacency matrix of this random graph will be denoted by $A_{n,p,\kappa}$

Our goal in this section will be to prove that, up to some error terms that are small with high probability, the adjacency matrix $A_{n,\kappa,p}/pn$ of $G_{n,p,\kappa}$ will be related to the integral operator on $L^{2}()$ that is defined by $\kappa$.

Similar results for the Laplacian of $G_{n,p,\kappa}$ are discussed in Section 8.

The phrase “inhomogeneous random graph” comes from a paper by Bollobas, Janson and Riordan where the above model was studied in the range $p=\Theta\left(1/n\right)$ with background spaces more general than $$. Their goal was to study the structure of connected components in the general model, in analogy with the well-known Erdös-Rényi phase transition at$p=1/n$ .

A related random graph model generating dense graphs ($p=1$) was introduced in and studied in . This model is related to the beautiful theory of graph limits where the space of graphs is “completed” into the space of graphons, which are non-negative, symmetric functions like $\kappa$ above, with the further restriction that $\kappa\leq 1$. There is a fairly complete correspondence between the properties of sequences of graphs that are convergent in terms of normalized subgraph counts and the corresponding limiting graphon. Conversely, the sequence of random graphs correponding to a given graphon $\kappa$ converges to that same graphon. The cut metric that defines graph convergence will be further discussed in Section 6.3 below.

The connection between the convergent graph sequences and inhomogeneous random graphs was noted in , where the authors studied bond percolation over a convergent sequence of graphs and found the critical probability for existence of a giant component. Other papers have focused on the relationship between convergence of subgraph counts vs. convergence in the cut metric (see below) for sparse graphs, a topic that is far from completely elucidated. In what follows we will show that our random graphs converge to the corresponding kernel in a stronger metric.

2 The precise result

We will use the following technical assumption.

Moreover, the points $X_{1},X_{2},\dots,X_{n}$ are random i.i.d. uniform over $$.

where $\chi_{S}$ is the indicator function of the set $S$ and $E(G_{n,p,\kappa})$ is the edge set of $G_{n,p,\kappa}$. Notice that $\mathcal{G}_{n,p,\kappa}$ defines a bounded linear operator on $L^{2}()$ via a formula similar to (6.2):

and note that $T_{\mathcal{G}_{n,p,\kappa}}=H_{n}A_{n,p,\kappa}E_{n}/pn$.

Finally, let ${\rm spec}(T_{\kappa})$ be the spectrum of the operator $T_{\kappa}$ in (6.2) (see Section 2.2 to recall what the spectrum is).

There exist universal constants $c,C>0$ such that the following holds under Assumption 6.1. Given $\epsilon>0$, suppose there exists a $L$-Lipschitz function $\kappa_{\epsilon}$ that also takes values in $[0,K]$ and which is $\epsilon$-close to $\kappa$ in the $L^{2}(^{2})$ norm. Define:

The $n\times n$ matrices $A_{n,p,\kappa}$ and $E_{n}T_{\kappa}H_{n}$ satisfy:

The integral operators $T_{\mathcal{G}_{n,p,\kappa}}$ and $T_{\kappa}$ satisfy:

This Theorem implies that, up to error terms that are small with high probability, $A_{n,p,\kappa}/pn$ is defined solely in terms of the kernel function $\kappa$, up to a permutation of coordinates. It also implies that, statistical parlance, it implies that the non-zero eigenvalues of $A_{n,p,\kappa}$ are strongly consistent estimators of the non-zero eigenvalues of $T_{\kappa}$ when $n\to+\infty$ and $p=p(n)$ $pn/\ln n\to+\infty$.

Both of these assertions hinge on the fact that Lipschitz functions are dense in $L^{2}(^{2})$. Unfortunately, our error bounds are not independent of $\kappa$, as quality of the approximation by Lipschitz functions, measured by the size of the Lipschitz constant for a given approximation error $\epsilon$, may vary with $\kappa$. This is in contrast with approximation in the cut norm, which we now discuss.

3 Convergence in the operator and cut metrics

One can check that $\|\eta\|_{\rm cut}\leq\|\eta\|_{L^{1}}$ always. This definition of $\|\eta\|_{\rm cut}$ is natural from the point of view of Functional Analysis; a more “combinatorial” definition,

is equivalent to the previous one in the sense that:

Now assume that $G_{1}$ and $G_{2}$ are graphs with common vertex set $[n]$ and adjacency matrices $A_{G_{1}},A_{G_{2}}$. Define:

is the normalized cut norm of $A_{G}-A_{H}$ .

Thus the cut norm on $L^{1}(^{2})$ induces a distance on graphs. Notice, however, that this distance might be positive even though $G$ and $H$ are isomorphic. This motivates the following definition: given two kernels $\kappa,\kappa^{\prime\prime}\in L^{1}(^{2})$ , say that $\kappa^{\prime\prime}$ is a rearrangement of $\kappa$ ($\kappa^{\prime\prime}\approx\kappa$) is there exists a measure-preserving bijection $\tau:\to$ such that $\kappa(x,y)=\kappa(\tau(x),\tau(y))$ for almost every $(x,y)\in^{2}$. The cut metric assigng to each pair $\kappa,\kappa^{\prime}$ of kernels a distance:

Notice that the cut metric does not distinguish between (the kernels of) isomorphic graphs.

3.2 The operator norm and the operator metric

The metric $d_{\rm cut}$ yields a criterion for convergence of graph sequences. In the dense case $p=\Theta\left(1\right)$, this implies the convergence of normalized subgraph counts and also gives a criterion for testable graph properties . As mentioned above, much less is understood about the case $p=o\left(1\right)$ (see however the conjectures of Bollobás and Riordan [13, Section 5.2]).

Theorem 6.1 is mostly concerned with the eigenvalues and the eigenvectors of the adjacency matrix $A_{n,p,\kappa}$. Unfortunately, in general we do not even know how to control the eigenvalues of $A_{n,p,\kappa}$ in terms of the cut norm alone. For bounded kernels ($p=\Theta\left(1\right)$), this is easy enough (see [17, Theorem 6.6]), but there are difficulties in extending this to the sparse case. This does seem to be a serious problem, as related difficulties appear in when the authors attempt to relate the convergence of subgraph counts to cut metric convergence. [Estimating the eigenvalues is related to counting cycles in the corresponding graph or graphon.]

Luckily, a stronger notion of convergence implied by the $L^{2}\to L^{2}$ norm suffices for our purpose, and it is precisely this notion that we achieve via our methods.

From (6.4) we see that that $\|\eta\|_{\rm op}\geq\|\eta\|_{\rm cut}$ whenever $\eta$ is square-integrable.

In analogy with the cut metric, one can also define an operator (pseudo-)metric on square-integrable kernels via the formula:

One can show via our results that when Assumption 6.1 holds, $n\gg 1$ and $p\gg\ln n/n$, then the kernel determined by $G_{n,p,\kappa}$ – which is equivalent to $\mathcal{G}_{n,p,\kappa}$ in Theorem 6.1 – converges in the $d_{\rm op}$ metric to $\kappa$. We omit the details.

A drawback of $d_{\rm op}$ is that it lacks a corresponding (weak or strong) regularity lemma, which would allow one to approximate up to error $\epsilon$ any (say bounded) kernel $\kappa$ by simple functions taking at most $m=m(\epsilon,\|\kappa\|_{L^{\infty}})$ values. Indeed, this is precisely why the bound in Theorem 6.1 depends on $\kappa$.

4 Proof of Theorem 6.1

For $f,g\in L^{2}()$, define $(f,g)_{L^{2}}\equiv\int_{0}^{1}f(x)g(x)\,dx$ and $\|f\|_{L^{2}}^{2}\equiv(f,f)_{L^{2}}$.

The following facts can be easily checked (proof omitted).

Let us now relate the non-zero eigenvalues and eigenvectors of $A_{n,p,\kappa}$ with those of $T_{\mathcal{G}_{n,p,\kappa}}$. Write:

where each $\Pi_{\alpha}$ the projection onto the eigenspace corresponding to $\alpha pn$. By (6.10),

The operators $H_{n}\,\Pi_{\alpha}E_{n}$ are orthogonal projections with orthogonal ranges. Therefore, the non-zero eigenvalues of $T_{\mathcal{G}_{n,p,\kappa}}$ are the numbers $\alpha\neq 0$ with $\alpha pn\in{\rm spec}(A_{n,p,\kappa})$. Moreover, for each such $\alpha$, $H_{n}\,\Pi_{\alpha}E_{n}$ is the projection onto the corresponding eigenspace of $T_{\mathcal{G}_{n,p,\kappa}}$.

Proof: [of the Claim] First notice that for each $\alpha$:

because $E_{n}H_{n}=I_{n}$ (eqn. (6.8)) and $\Pi_{\alpha}^{2}=\Pi_{\alpha}$. One can also check that for all $f,g\in L^{2}()$,

where we used (6.5) for the first and third equalities and the fact that $\Pi_{\alpha}=\Pi_{\alpha}^{*}$ for the second one. It follows that $H_{n}\,\Pi_{\alpha}E_{n}$ is a self-adjoint operator on $L^{2}$ that equals its square; this means that it is an orthogonal projection onto its range.

To see that these ranges are orthogonal for distinct $\alpha$, notice that the range of $H_{n}\,\Pi_{\alpha}E_{n}$ is the set of all vectors of the form $H_{n}\psi$ where $\psi$ belongs to the range of $\Pi_{\alpha}$ and is therefore an eigenvector of $A_{n,p,\kappa}$ with eigenvalue $\alpha pn$. But eigenvectors of $A_{n,p,\kappa}$ with distinct eigenvalues are orthogonal, hence their images under $H_{n}$ are orthogonal in $L^{2}$ (by (6.6)).

The other assertions follow directly. $\Box$

4.2 The concentration argument

Let us introduce a matrix $\overline{A}_{n,p,\kappa}$ whose $(i,j)$-th entry is $p\kappa(X_{i},X_{j})$, $1\leq i\leq j\leq n$. Conditioning on the realization of the $X_{1},\dots,X_{j}$, our random graph model has independent edges with respective probabilities ${\bf p}(i,j)=p\kappa(X_{i},X_{j})$ and $\overline{A}_{n,p,\kappa}$ is precisely the typical adjacency matrix $A_{\bf p}^{{\rm typ}}$ in this setting. We deduce from Theorem 3.1 that there exists a constant $C>0$ independent of $n,\kappa$ and $X_{1},\dots,X_{n}$, such that if $\Delta=\Delta(X_{1},\dots,X_{n})$ is as in that Theorem and $\Delta\geq C\ln n$,

where $K$ is the quantity in Assumption 6.1. Therefore,

Since $H_{n}$ is an isometry (by (6.6)) and $E_{n}$ has norm at most $1$ (by (6.7)),

4.3 Nearing the end of the argument

We will show in Lemma 6.1 below that there exists a universal $c>0$ such that for any $\epsilon>0$

Increasing $c$ if necessary, this implies that, with probability $\geq 1-n^{-2}$

for $\theta$ as in the Theorem. This proves the second assertion in the Theorem. To prove the first one, first notice that, since $E_{n}H_{n}=I_{n}$ (cf. (6.8)),

Now use again the fact that $E_{n}$ and $H_{n}$ have norm $1$ to deduce:

The other two assertions follow from the perturbation lemmas provided in the Appendix. More precisely, recall from Claim 6.1 that the eigenvalues of $T_{\mathcal{G}_{n,p,\kappa}}$ are either or equal to some $\alpha\neq 0$ with $\alpha pn\in{\rm spec}(A_{n,\kappa,p})$. Assertion $3$ follows from Lemma A.1 applied to $T_{\mathcal{G}_{n,p,\kappa}}$ and $T_{\kappa}$.

As for Assertion $4$, we recall from Claim 6.1 that whenever $\beta pn\in{\rm spec}(A_{n,p,\kappa})$ with corresponding eigenspace projection $\Pi_{\beta}$ the corresponding eigenspace of $T_{\mathcal{G}_{n,\kappa,p}}$ is $H_{n}\Pi_{\beta}E_{n}$. This implies that:

is the projection onto the eigenspaces of $T_{\mathcal{G}_{n,p,\kappa}}$ corresponding to eigenvalues between $\alpha-\gamma$ and $\alpha+\gamma$. One can apply Lemma A.2 with $\epsilon=\theta$ and $b-\gamma=a+\gamma=\alpha$ to deduce that, whenever $\alpha$ is as in assertion $4$ and $\|T_{\mathcal{G}_{n,p,\kappa}}-T_{\kappa}\|\leq\theta$,

Multiplying both operators above by $E_{n}$ on the left and by $H_{n}$ on the right, using that $H_{n}$ and $E_{n}$ have norm $\leq 1$ and that $E_{n}H_{n}=I_{n}$, we see that:

This finishes the proof modulo inequality (6.12), which is the subject of Lemma 6.1 below.

Then the following holds with probability $\geq 1/2n^{2}$:

By the results in Section 2.2, one can bound the first term in the RHS by:

For the second term, we observe that $\overline{T}-\widehat{T}$ is of the form $T_{\eta}$ for $\eta$ taking the values $\kappa(X_{i},X_{j})-\kappa_{\epsilon}(X_{i},X_{j})$ on squares of area $1/n^{2}$. We deduce from the results in Section 2.2 that:

Moreover, the random variables $X_{i}$ are independent and replacing $X_{i}$ by some other $X_{i}^{\prime}\in$ can change the value of the sum in the RHS of (6.14) by at most $K^{2}/n$ (as each term is bounded by $K$ and only $n$ terms involve $X_{i}$). Azuma’s inequality implies:

Therefore, with probability $\geq 1-1/4n^{2}$ we have:

where $c>0$ is some universal constant. We deduce:

To finish the proof, we must bound the third term in (6.13). To do this, we notice that:

Using the definition of $\sigma_{n}$ from Section 6.2, one can rewrite this as:

Recall that $\kappa_{\epsilon}$ is $L_{\epsilon}$-Lipschitz and therefore,

A simple calculation using e.g. Massart’s version of the Dvoretsky-Kiefer-Wolfowitz inequality reveals that the last term is $\leq c^{2}\ln n/n$ ($c>0$ universal) with probability $\geq 1-1/4n^{2}$. We deduce that:

with probability $\geq 1-1/4n^{2}$. Combining this with (6.15) and replacing $c>0$ with a larger universal constant if necessary finishes the proof. $\Box$

Freedman’s inequality for matrix martingales

In this Section we prove our new concentration inequality, Theorem 1.2. We begin with some preliminaries from matrix analysis.

Matrix inequalities for the positive semi-definite order will be essential in our proof.

We will need four other properties of the partial order “$\preceq$”. The first three are easily checked and we omit their proofs:

The fourth one is slightly less standard.

To prove (7.4), notice that for for $A,B,C$ as above,

since $A\succeq 0$. This implies that $(C-B)^{1/2}A(C-B)^{1/2}$ must be positive semi-definite, hence its trace is non-negative: ${\rm Tr}(A(C-B))\geq 0$, which is equivalent to (7.4) by linearity.

1.2 Conditional expectations are monotone

and the RHS follows from $X\preceq Y$ by the previous implication (since $Q$ is countable).

1.3 Matrix functions and matrix exponentials

We need one more result from matrix analysis, called the Golden Thompson inequality.

This inequality is fundamental in adapting the standard proofs of concentration to the matrix setting .

2 The proof

Proof: $\|C\|_{2}^{k-2}C^{2}-C^{k}$ has the same eigenvectors as $C$ and its eigenvalues are given by

This is always $\geq 0$ because $\|C\|_{2}=\max_{1\leq i\leq d}|\lambda_{i}(C)|$. $\Box$

Proof: The previous lemma implies that $C^{i}\preceq C^{2}$ for all $i\geq 2$. Property (7.2) of “$\preceq$” implies that for any $k$,

Now let $k\nearrow+\infty$ and use (7.1). $\Box$

The next step is an exponential inequality for martingales.

Taking conditional expectations, we see that:

Here the equality is a result of ${\rm Tr}$ and expected values commuting (2.3), as well as noting that $e^{sX_{n-1}-2s^{2}W_{n-1}+C}$ is $\mathcal{F}_{n-1}$-measurable and then applying (2.4) to the conditional expectation.

This will imply (via monotonicity of the trace (7.4)) that:

and the Lemma follows from this via induction in $n$.

To prove the claim, we first note that for $|s|\leq 1/2$,

by the assumption that $\|X_{n}\|_{2}\leq 1$. We now apply Lemma 7.2 with $C=sX_{n}-s^{2}\Delta_{n}$ and the monotonicity of conditional expectations (7.4) to obtain:

Now notice that the eigenvalues of $-s^{2}\Delta_{n}+4s^{4}\Delta_{n}^{2}$ are given by:

The inequality $s\leq 1/2$ implies $4s^{4}\leq s^{2}$. Moreover, each $\lambda_{i}(\Delta_{n})$ is between and $1$, since $\|\Delta_{n}\|\leq 1$ and $\Delta_{n}\succeq 0$ (it is the conditional expectation of $X_{n}^{2}$). This implies that the above expression is at most:

Proof: [of Theorem 1.2] One may assume that $M=1$ (one can always rescale $Z_{n}$ so that this is the case; the bound behaves accordingly). If $\lambda_{\max}(W_{n})\leq\sigma^{2}$, $\sigma^{2}I-W_{n}\succeq 0$ is positive semi-definite. Inequality (7.3) then implies that for all $s>0$,

Notice that with this choice $s\leq 1/2$ always. Moreover,

is a martingale satisfying the assumptions of the Theorem and that, moreover, $W_{n}$ is deterministic in this case:

in Theorem 1.2 and deduce the first half of the Corollary below. The other half comes from considering $-\sum_{i=1}^{n}X_{i}$.

Final remarks

Sharpness of Theorem 1.2. One can show that Theorem 1.2 is close to sharp and that, in particular, the $d$ factor in the bound is necessary for general martingale sequences. To see this, consider a sum $Z_{n}$ of $n$ independent, identically distributed $d\times d$ diagonal random matrices $X_{1},\dots,X_{n}$ whose diagonal entries are independent, unbiased $\pm 1$. The largest eigenvalue of $Z_{n}$ is a maximum of $d$ independent random sums, each with $n$ terms of the kind $\pm 1$ above. One can see that for large $n$ and $d$ and for $t\approx\sqrt{n\ln d}$,

which is what Corollary 7.1 gives up to the constants in the exponent.

An interesting question is to understand the circumstances under which one can remove the $d$ factor from the bound. For instance, can the sharper results of be reobtained via some variant of Theorem 1.2?

Other applications of Theorem 1.2. In a related paper (in preparation) we show how Theorem 1.2 can be used to show concentration of the matrices of random lifts of large graphs. A pleasing corollary of our result is this: consider a random $k_{1}k_{2}$-lift of a large graph $G$ with minimum degree $\omega(\ln(k_{1}k_{2}n))$. The Laplacian of this lift is essentially indistinguishable from that of the (in principle very different) random graph obtained by performing a $k_{1}$-lift on $G$ and then a $k_{2}$-lift on the resulting graph.

It would be interesting to see other applications of Theorem 1.2, especially in settings where the Christofides-Märkstrom bound is useless because its variance term is too large (cf. Remark 3.1).

The Laplacian of inhomogeneous random graphs. The results of the Section 6 can be extended to the Laplacian $\mathcal{L}_{n,p,\kappa}$ of $G_{n,p,\kappa}$. More precisely, add the following condition to Assumption 6.1: that there exists a $K_{-}>0$ such that for all $x\in$, $\kappa(x)\equiv\int_{0}^{1}\kappa(x,y)\,dy\geq K_{-}$. Then there is a close correspondence between $\mathcal{L}_{n,p,\kappa}$ and the operator $S_{\xi}\equiv{\rm Id}_{L^{2}}-T_{\xi}$, where ${\rm Id}_{L^{2}}$ is the identity operator on $L^{2}()$ and $T_{\xi}$ is the integral operator given by the symmetric, non-negative function:

That is, if $p\leq 1/K$ and $pnK_{-}\gg C\ln n$ for some $C$, we will have:

with consequences for the spectrum and eigenspaces of $\mathcal{L}_{n,p,\kappa}$. We omit the details.

Better bounds and extensions? We have mentioned the results on spectral gaps in references and , on $G_{n,p}$ and random graphs with given expected degrees. These papers actually do much more than we described, as they show that, even is very sparse graphs, there is a large “core” set of vertices so that the matrices of the induced subgraph are well-behaved. It would be an interesting question to prove a similar result either for more general instances of bond percolation or inhomonegeous random graphs.

Cut convergence, eigenvalues and eigenvectors. It is not clear to the author what one can/cannot prove about eigenvectors and eigenvalues of sparse graphs while only assuming that they converge to a given $\kappa$ in the cut norm. Ideally, one would wish to be able to prove that this suffices for the convergence of the given operators, at least under suitable assumptions, but it is not clear how one should proceed.

Appendix A Appendix: two perturbation results

The following functional-analytic perturbation results are needed in the main text. In what follows $\mathcal{H}$ is a real Hilbert space and $\|\cdot\|$ denotes both the Hilbert space norm and the induced norm on linear operators. Undefined notions and quoted results can be found in any textbook on Functional Analysis, eg. .

For the case of infinite-dimensional rank, $V$ and $W$ are the limit (in the operator norm) of operators of finite-dimensional rank. More specifically, recall from Section 2.2 that the spectral theorem for compact, self-adjoint operators states that $V$ can be written as a sum:

where the $P_{\alpha}$ are orthogonal projectors of orthogonal ranges, with finite rank if $\alpha\neq 0$. Moreover, for any $\delta>0$, ${\rm spec}(V)\backslash(-\delta,\delta)$ is finite. Therefore, the finite-rank operator:

satisfies $\|V_{\delta}-V\|\leq\delta$. One may similarly define $W_{\delta}$ with $\|W_{\delta}-W\|\leq\delta$ and it follows that $\|V_{\delta}-W_{\delta}\|\leq\epsilon+2\delta$. Moreover, we have the simple fact: