arXiv: 1708.02107

Adaptive Estimation of Nonparametric Geometric
Graphs
Yohann De Castro, Claire Lacour and Thanh Mai Pham Ngoc

arXiv:1708.02107v2 [] 22 Sep 2017

Laboratoire de Mathématiques d’Orsay
Univ. Paris-Sud, CNRS, Université Paris-Saclay, 91405 Orsay, France
Abstract: This article studies the recovery of graphons when they are convolution kernels on compact
(symmetric) metric spaces. This case is of particular interest since it covers the situation where the
probability of an edge depends only on some unknown nonparametric function of the distance between
latent points, referred to as Nonparametric Geometric Graphs (NGG).
In this setting, almost minimax adaptive estimation of NGG is possible using a spectral procedure
combined with a Goldenshluger-Lepski adaptation method. The latent spaces covered by our framework
encompasses (among others) compact symmetric spaces of rank one, namely real spheres and projective
spaces. For these latter, explicit computations of the eigenbasis and of the model complexity can be
achieved, leading to quantitative non-asymptotic results. The time complexity of our method scales
cubicly in the size of the graph and exponentially in the regularity of the graphon. Hence, this paper
offers an algorithmically and theoretically efficient procedure to estimate smooth NGG.
As a by product, this paper shows a non-asymptotic concentration result on the spectrum of integral
operators defined by symmetric kernels (not necessarily positive).
MSC 2010 subject classifications: Primary 62G05; secondary 60C05, 60B15.
Keywords and phrases: Graphon, Random Networks, Spectral Estimation, Kernel Matrix, Convolution
Operator, Sphere.

1. Introduction
Over the recent years, the study of networks has become prevailing in many fields. Through the advent
of social networks, biological neural networks, food webs, protein interaction in genomics and World
wide web for instance, large scale data have become available. Extracting information from those
repositories of data is a true challenge. Random graphs prove to be particularly relevant to model
real-world networks. They are capable to capture complex interactions between actors of a system.
Vertices of a random graph usually represent entities of a system and the edges stand for the presence of
a specified relation between those entities. An important statistical problem is seeking better and more
informative representations of random graphs.
Following the seminal work of [13] various random graphs models have been suggested, see [5, 26, 20,
23] and references therein. Aside from classical random graphs, random geometric graphs, see [28],
have emerged as an interesting alternative to model real networks having spatial content. Examples
include the Internet (where the nodes are the routers) and other physical communication networks
such as road networks or neural networks in the brain. Recall that a random geometric graph is an
undirected graph in which each vertex is assigned a latent (unobservable) random label in some metric
spaces S. Two vertices are connected by an edge if the distance between them is smaller than some
threshold. Assuming that the underlying metric is the unit sphere Sd−1 and latent variables drawn from
the uniform distribution on Sd−1 , the paper [8] considered the problem of testing if the observed graph
is an Erdös-Rényi one (no geometric structure) or a geometric graph on the sphere where points are
connected if their distance is smaller than some threshold.
More generally, random graphs with latent space can be characterized by the so-called graphon. In
fact, graphons can be seen as kernel functions for latent position graphs. For more insight about the
theory of graphon, we refer to the excellent monograph of [22]. In the case of graphons defining positive
1

imsart-generic ver. 2014/10/16 file: Graph17.tex date: September 25, 2017

2

1

INTRODUCTION

definite kernels, the paper [33] proved that the eigen-decomposition of the adjacency matrix yields
consistent estimator of the graphon feature maps involving the latent variables. Besides, nonparametric
representations of graphons has gained attention. Statistical approaches on estimating graphons have
been developed using Least-Squares estimation [19] or Maximum Likelihood estimation [37]. Dealing
with estimation of (sparse) graphons from the observation of the adjacency matrix, the paper [19]
derives sharp rates of convergence for the L2 loss for the Stochastic Block Model.

1.1. A Statistical Pledge for Structured Latent Spaces
The graphons are limiting objects that describe large dense graphs. The graphon model [22] is standardly
and without loss of generality formulated choosing [0, 1] as latent space. In this model, given latent
points x 1 , . . . , x n ∈ [0, 1], the probability to draw an edge between i and j is W (x i , x j ) where W is a
function from [0, 1]2 onto [0, 1], referred to as a graphon. This model is general and well referenced in
the literature—as mentioned earlier, the reader may consult the book [22] for further details.
However, this model may underneath intrinsic features of a random graph. For instance, recall the
prefix attachment graph model [22, page 190] where the nodes are added one at a time and each new
node connects to a random previous node and all its predecessors. In this model, the graph sequence
converges in cut distance [22, Proposition 11.42] to the graphon Wpref defined as
∀(x 1 , y1 ), (x 2 , y2 ) ∈ [0, 1]2 ,

Wpref ((x 1 , y1 ), (x 2 , y2 )) = 1(x 1 < x 2 y2 ) + 1(x 2 < x 1 y1 ) ,

(1)

up to a measure preserving homomorphism of the latent space [0, 1]2 . From a statistical point of view, the
estimation of the function ((x 1 , y1 ), (x 2 , y2 )) 7→ 1(x 1 < x 2 y2 ) from sample points ((x k , yk ))k uniformly
distributed on [0, 1]2 is a well understood standard task.
Yet one may also represent this graphon on the standard latent space [0, 1]. And, in this case, one
cannot represent this graphon using the indicator function of two symmetric convex sets with piecewise
smooth border as done in (1). Actually, in this case, a fractal-like structure appear and the statistical
estimation of this function seems more difficult than in (1). Our statement may be loose here but one
may emphasize that there may exist better latent spaces than [0, 1] on which the graphon may presents
a simple and better estimable formulation.
An other important statistical issue is that, by construction, graphons are defined on an equivalent class
“up to a measure preserving homomorphism” and it can be challenging to have a simple description from
an observation given by sampled graph—since one has to deal with all possible composition of a bivariate
function by any measure preserving homomorphism. In this paper, we circumvent this disappointing
statistical issue restraining our attention to graph models for which the probability of appearance of an
edge depends as a nonparametric function of the distance between latent points.

1.2. Main results
In this paper, we focus on latent metric spaces for which the distance is invariant by translation (or
conjugation) of pairs of points. This natural assumption leads to consider that the latent space S has
some group structure, namely it is a compact Lie group or some compact symmetric space. Hence,
consider graphons defined as functions p of (the cosine of) the distance γ (normalized so that the range
of γ equals [0, π]) of some compact Lie group S, or more generally of some compact symmetric space,
see Section 4. In this case, the graphon is given by
∀x, y ∈ S,

W (x, y) = p(cos γ(x, y)) = p(cos γ(z, e)) and z = x y −1 ,

where y −1 is the inverse of y, e denotes the identity element of S and p is a function from [−1, 1]
onto [0, 1] referred to as the “envelope”. In the case when S is the Euclidean sphere, we consider

1.2

Main results

3

graphons that are a function p of cosine of the distance, namely cos γ(x, y) = 〈x, y〉, between latent
points x, y ∈ S.
First, note that W , viewed as an integral operator on square-integrable functions, is a compact convolution
(on the left) operator. The convolution (on the left) kernel is simply
z ∈ S 7→ p(cos γ(z, e)) ∈ [0, 1] .
Then the main point is that there exists an L2 -decomposition of the Hilbert space of square integrable
functions such that the eigenfunctions basis of the convolution kernel (and the graphon W viewed as a
integral operator) depends only on the latent space S and does not depend on the function p. This basis
is the irreducible characters in the (Lie) Group case and the zonal spherical functions in the non-Group
case, see Cartan’s Classification of “sscc” Lie Groups and “ssccss” in Section 4 for further details. This
decomposition can be pushed on [−1, 1] and one gets an L2 -decomposition of the envelope function p
such that the orthonormal basis (Z` ) depends only on the latent space S and does not depend on p,
see (2). Furthermore, the eigenvalues λ? = (λ?k )k≥0 of the kernel W are exactly (up to some known
multiplicities and up to some known multiplicative constants) the coefficients of p onto the orthonormal
basis (Z` )`≥0 . Hence, the graphon W is entirely described by the univariate function p defined on [−1, 1].
It follows that this subclass of graphons may be well suited for estimation since it reduces to estimate a
simple univariate function on [−1, 1].
Now, consider the case when S is one of the compact symmetric space of rank one—namely real spheres
or real/complex/quaternionic/octonionic projective spaces. In this case, one can explicitly give the
decomposition of the envelope function p. One can prove that the orthonormal polynomials (Z` )`≥0 are
the orthonormal polynomials (more precisely, normalized Jacobi polynomials) of some Beta law with
known shape parameters (α, β), see Table 1 for the explicit values. This decomposition is given by
XÆ
1
d` p?` Z` and p?` = p 〈p, Z` 〉L2 ([−1,1],w) ,
(2)
p=
d`
`≥0
in L2 ([−1, 1], w) where w denotes the density function of the Beta distribution. We further assume that
there exists s > 0, a (Sobolev) regularity parameter, such that
X
∀R ≥ 1 ,
d` (p?` )2 ≤ C(p, s, S) R−2s .
`>R

for some constant C(p, s, S) > 0 and for some known dimensions (d` )`∈N (given by the representation of
the group/quotient S) that depends only on S, see Table 1. This assumption governs the regularity of
the kernel W and it can be understood that the derivative of order s (in the Laplacian on S sense) of W
b Rb (from the spectrum of the adjacency
is square-integrable. In this case, one can build an estimator λ
?
matrix of the graph) of the spectrum λ of W (viewed as an integral operator) such that


2s
 

n − 2s+(d−1)
b
2 bR
?
E δ2 λ , λ
=O
,
log n
where n is the size of the graph, d is the dimension of the latent space (actually, S is a (d − 1)-manifold)
and δ2 is the `2 distance between spectra, see (7) for a definition. We uncover the minimax rate of
estimating a s-regular function on a space of (Riemannian) dimension d − 1 up to a multiplicative log
factor. This result is stated in Theorem 6 without adaptation to the smoothness parameter, Theorem 7
and Corollary 8 with smoothness adaptation, and Theorem 9 and Corollary 10 for adaptive estimation of
the envelope function p at rate O (log n/n) when p is a polynomial. The general statement for compact
symmetric spaces is given by Theorem 11.
Note that our results hold for general convolution kernels and not necessarily semidefinite positive
kernels. Indeed, it is often assumed in the literature, see for instance [14, 29, 33, 32], that the graphon W
is a semidefinite positive kernels. In this case, the adjacency matrix of the random graph is almost surely
semidefinite positive, which is a strong requirement in Graph theory. To bypass this limitation, our
approach does not use any RKHS representation but a new non-asymptotic concentration result on
the integral operator, see Theorem 2 and Corollary 3. The rates uncovered by these results allow us to
introduce a minimax adaptive estimation procedure of the spectrum of the graphon.

4

2

SPECTRAL CONVERGENCE OF THE SAMPLED GRAPHONS

From a computational point of view, Theorem 5 enlightens on the time complexity of our estimator.
Remarkably, the time complexity is n3 + (Rmax + 2)!, that is cubic in the graph size n (as any spectral
method) and exponential in the number of coefficients p?` one has to estimate. The spatial complexity is
quadratic in n as one has to store the adjacency matrix of the graph.

1.3. Outline
The convergence of the spectrum of the “matrix of probabilities” towards the spectrum of the integral
operator in a non-asymptotic frame is given in Section 2. Then, we begin our study by a comprehensive
example on the d-dimensional sphere in Section 3. Interestingly, we uncover that the spectrum of the
graphon (viewed as a kernel operator) presents a structure: the eigenvalues have prescribed multiplicities
and the eigenvectors are fixed—they are the spherical harmonics. Adaptive minimax estimation of the
spectrum of the graphon W (viewed as an integral operator) is proved and computational complexities
are discussed. Extensions to compact symmetric spaces is done in Section 4. Numerical experiments are
presented in Section 5. The proofs are given in the appendix.

2. Spectral Convergence of the Sampled graphons
2.1. Estimating the Matrix of Probabilities
We denote [n] := {1, . . . , n} for all n ≥ 1. Consider a random undirected graph G with n nodes and
assume that we observe its n × n adjacency matrix A given by entries Ai j ∈ {0, 1} where Ai j = 1 if the
nodes i and j are connected and Ai j = 0 otherwise. We set Aii = 0 on its diagonal entries for all i ∈ [n]
and we assume that Ai j are independent Bernoulli random variables with (Θ0 )i j := P{Ai j = 1} for
1 ≤ i < j ≤ n. We denote by Θ0 the n × n symmetric matrix with entries (Θ0 )i j for 1 ≤ i < j ≤ n and
zero diagonal entries. This is a matrix of probabilities associated to the random graph G. Throughout
this paper, we denote by
b n := (1/n) A and T n := (1/n) Θ0 .
T
(3)
Using the central limit theorem, it is elementary that, with high probability,


 
X
1 
1
b n − T n k2 ∈ 
kT
(Θ0 )i j (1 − (Θ0 )i j ) ± O
,
F
n2 i6= j
n
b n and T n
where k · k F denotes the Frobenius norm. We witness that the Euclidean distance between T
is of the order of the average value of the entries (Θ0 )i j . The Frobenius norm seems an inappropriate
prediction loss. Instead, our analysis leverages the operator norm k · k loss to account for the distance
b n and the target parameter T n . Furthermore, a near optimal error bound can
between the observation T
be derived for the operator norm k · k loss as shown in [2].
Proposition 1 (Bandeira & van Handel [2]). There exists a universal constant C0 > 0 such that for all
α ∈ (0, 1), it holds
p
p


2D 0
log(n/α)
b n − T nk ≥ 3
P kT
+ C0
≤α
(4)
n
n
X

where D 0 = max
(Θ0 )i j (1 − (Θ0 )i j ) ≤ n/4.
i∈[n]

j∈[n]

A proof is recalled in Appendix A.1. Proposition 1 is of particular interest giving an error bound on each
eigenvalue λk (T n ) of T n , where λk (M ) denotes the k-th largest eigenvalue of the symmetric matrix M .

2.2

Non-Asymptotic Error Bounds on the Kernel Spectrum in δ2 -metric

5

Indeed, it holds, with probability greater that 1 − n exp(−n),
∀k ∈ [n],

p
b n ) − λk (T n )| ≤ k T
b n − T n k = O (1/ n) ,
|λk ( T

(5)

by Weyl’s perturbation Theorem, see [4, page 63] for instance.

2.2. Non-Asymptotic Error Bounds on the Kernel Spectrum in δ2 -metric
b n can be a good approximation of the spectrum of T n in the sense
We understand that the spectrum of T
of (5). Assuming a graphon W model we can link the spectrum of T n (sampled graphon onto the latent
points X 1 , . . . , X n see below) to the spectrum of an integral operator TW defined by the graphon W
viewed as a symmetric kernel. More precisely, we consider J := (S, A , σ) a probability space on S
endowed with measure σ on the σ-algebra A, and W : S × S → [0, 1] a symmetric σ-measurable
function. The couple (J, W ) is referred to as a graphon, see for instance [22, Chapter 13]. We then
define a probabilistic model on Θ0 setting
(Θ0 )i, j = W (X i , X j ) for i 6= j and 0 otherwise
where X 1 , . . . , X n are i.i.d. drawn w.r.t. σ. Assume that the kernel satisifies W ∈ L2 (S × S, σ ⊗ σ), so that
Z
∀x ∈ S, ∀g ∈ L2 (S, σ),

(TW g)(x) =

W (x, y)g( y)dσ( y) ,

S

defines a symmetric Hilbert-Schmidt operator TW on L2 (S, σ) and we can invoke the spectral theorem.
Hence, it holds that, in the L2 (S × S, σ ⊗ σ)-sense,
X
for almost every x, y ∈ S, W (x, y) =
λ?k φk (x)φk ( y) ,
(6)
k≥1

for an L2 (S, σ)-orthonormal basis (φi )i≥1 . This operator has a discrete spectrum, i.e. a countable
multiset λ? of nonzero (real) labeled eigenvalues (λ?k )k≥1 such that λ?k → 0. In particular, every nonzero
eigenvalue has finite multiplicity. We are free to choose any labeling of the target eigenvalues (λ?k )k≥1
and observe that our results are valid for any choice of labeling. For instance, we can standardly label the
eigenvalues in decreasing order with respect to their absolute values such that |λ?1 | ≥ |λ?2 | ≥ · · · and this
gives results whose error rates (typically kW −WR k2 see below) are in terms of the best L2 -approximation
of rank R of the kernel W . An other choice may result in labeling the eigenvalues in increasing order of
“frequencies”. This labeling is natural for instance when we have a representation by spherical harmonics
of the kernel as in Section 3. This gives results whose error rates are in terms of the best approximation
by low frequency (i.e. the R first frequencies) kernels.
Given
P 2 two2 sequences x and y of real numbers—completing finite sequences by zeros—such that it holds
x i + yi < ∞, we standardly define the `2 -rearrangement distance δ2 (x, y) as
δ2 (x, y) := inf

π∈P

X
 21
(x i − yπ(i) )2 ,

where the infimum is taken over P the set of permutations with finite support. Using Hardy-Littlewood
rearrangement inequality [16, Theorem 368], it is standard to observe that

δ2 (x, y) = lim

N →∞

N
X

 12
(x k − yk )2

,

(7)

k=−N

with the convenient notation x −1 ≤ x −2 ≤ . . . ≤ 0 ≤ . . . ≤ x 2 ≤ x 1 ≤ x 0 (respectively y−1 ≤ y−2 ≤ . . . ≤
0 ≤ . . . ≤ y2 ≤ y1 ≤ y0 ) where we denote x = (x k )k∈Z (respectively y = ( yk )k∈Z ) completing with zeros
if necessary.

6

3

THE SPHERE EXAMPLE, PRELUDE OF SYMMETRIC COMPACT SPACES

Using this metric we can compare the (finite) spectrum λ(T n ) of T n to the (infinite) spectrum λ? of TW .
To the best of our knowledge, existing results on this issue assume that W is a positive kernel and use a
RKHS representation and/or Mercer theorem. This assumption might seem meaningless for a graphon.
Indeed, it implies that TW is semi-definite and if W = WH is a “step-function” kernel representing a finite
graph H, it implies that the adjacency matrix of H is semi-definite which might be seen as restrictive. In
this article, we bypass this limitation with the next result based on the analysis developed in [21] and
some recent development in random matrix concentration, see [34] for instance.
Theorem 2. Let W ∈ L2 (S × S, σ ⊗ σ) be a symmetric kernel and let (φk )k≥1 be an orthonormal eigenbasis
as in (6). Let R ≥ 1 and α ∈ (0, 1/3). Set


ρ(R) := max 1,

R
X
r=1

φ r2


∞

−1

and ∀x, y ∈ S, WR (x, y) :=

R
X

λ?i φi (x)φi ( y).

i=1

Then, for all n3 ≥ ρ(R) log(2R/α), it holds
 2 log(2/α)  14
δ2 (λ(T n ), λ? ) ≤2kW − WR k2 + kW − WR k∞
n
v

t log(R/α)  1 
 ρ(R) log(2R/α)  12  2ρ(R) 
2
2
+ kWR k2
,
+
1 + max ||φ r ||∞
1≤r≤R
n
n
2n
with probability at least 1 − 3α.
A proof of Theorem 2 can be found in Appendix A.2. This result shows that for all n ≥ n0 (R), it holds
1
that δ2 (λ(T n ), λ? ) ≤ 2kW − WR k2 + C0 (R) n− 4 with probability at least 1 − 3α, where the constants
n0 (R) ≥ 1 and C0 (R) > 0 may depend on R, the orthogonal basis (φk )k∈[R] , α and the graphon W . We
have the following improvement for canonical kernels, see [11, Definition 3.5.1] for a definition.

Corollary 3. Assume further that the kernel (W − WR )2 (x, y) − E (W − WR )2 is canonical, namely
For almost every x ∈ S,



E (W − WR )2 (x, X 1 ) = E (W − WR )2 (X 1 , X 2 ) ,

then there exist universal constants C1 , C2 > 0 such that for all n3 ≥ ρ(R) log(2R/α), it holds
 C log(C /α)  12
1
2
δ2 (λ(T n ), λ? ) ≤2kW − WR k2 + kW − WR k∞
n
v

t log(R/α)  1 
 ρ(R) log(2R/α)  12  2ρ(R) 
2
2
+ kWR k2
+
1 + max ||φ r ||∞
,
1≤r≤R
n
n
2n
with probability at least 1 − 3α.
A proof of this corollary can be found in Appendix A.6.

3. The Sphere Example, Prelude of Symmetric Compact Spaces
From a general point of view, this article focuses on the case where the value W (x, y) depends on a
nonparametric function p of the distance between the points x and y of a latent space S assumed a
compact Lie group or a compact symmetric space, see Section 4 for further details. Such assumptions on
the graphon W allows to lead the spectral analysis a step further. In this section, we restrict our analysis
to the pleasant case of S := Sd−1 the unit sphere of Rd equipped with the uniform probability measure σ
and the usual scalar product 〈·, ·〉. In the literature, a popular model is given by the Random Geometric
Graph for which the value W (x, y) depends on the distance between the points x and y of the latent

3.1

Harmonic Analysis on Sd−1

7

space Sd−1 and W (x, y) = 1〈x, y〉≥τ for some threshold τ ∈ (−1, 1) as in [12, 8]. From now on, assume
that W only depends on the distance between latent points, namely
∀x, y ∈ Sd−1 ,

W (x, y) = p(〈x, y〉)

where p : [−1, 1] → [0, 1] is an unknown function that is to be estimated. We refer to p as the “envelope”
function.

3.1. Harmonic Analysis on Sd−1
Let us start by providing a brief overview on Fourier analysis on Sd−1 . As pointed out above, in this
case the operator TW is a convolution (on the left) operator. Its spectral decomposition (6) satisfies that
the orthonormal basis (φk )k does not depend on p and the spectrum λ(TW ) is exactly described by the
Fourier coefficients (p?` )` of p, see [10, Lemma 1.2.3]. This remark remains true when the latent space S
is assumed a compact Lie group or a compact symmetric space, see Section 4 for further details.
In the spherical case, the orthonormal basis of eigenfunctions consists of the real spherical harmonics.
The following material can be found in [10]. Let us denote H` the space of real spherical harmonics of
degree ` with orthonormal basis (Y` j ) j∈[d` ] where
d` := dim(H` ) =


 

`+d−1
`+d−3
−
`
`−2

(8)

for ` ≥ 2 and d0 = 1, d1 = d. Note that d` is therefore of order `d−2 . In the sequel we identify
(φk )k≥1 = (Y` j )`≥0, j∈[d` ] so that the spectral decomposition (6) reads
∀x, y ∈ Sd−1 ,

W (x, y) = p(〈x, y〉) =

X
`≥0

p?`

d
 X̀


Y` j (x)Y` j ( y) ,

(9)

j=1

|

{z

Zonal Harmonic

}

Pd`
where λ? = {p?0 , p?1 , . . . , p?1 , . . . , p?` , . . . , p?` , . . .} and j=1
Y` j (x)Y` j ( y) is a zonal harmonic of degree `,
see [10, Chapter 2]. The eigenvalue p?` has multiplicity d` if the eigenvalues are all distinct. Furthermore,
it holds that
Z
c b  1
β
` d
?
p` :=
p(t)G` (t)wβ (t)d t,
d`
−1
β

where G` denotes the Gegenbauer polynomial of degree ` defined for
β=

d−1
,
2

wβ (x) := (1 − x 2 )β−1 ,

c` :=

2` + d − 2
d−2

and

bd :=

Γ ( d2 )
Γ ( 12 )Γ ( d2 − 21 )

,

with Γ the Gamma function, see [10, Chapter 2]. We recall that the Gegenbauer polynomials are
orthogonal polynomials on the interval [−1, 1] with respect to the weight function wβ . Besides, one can
recover p ∈ L2 ([−1, 1], wβ ) thanks to the identity
p=

X Æ
`≥0

d` p?`



 X
β
β
β
G` /kG` kL2 ([−1,1],wβ ) =
p?` c` G` .
|
{z
}
`≥0

(10)

Z`

p
Remark 1. Note that p?` is the eigenvalue of the operator TW associated to the eigenspace H` , ( d` p?` )`≥0
β

β

are the coordinates of p ∈ L2 ([−1, 1], wβ ) in the orthonormal basis (Z` )`≥0 , where Z` := G` /kG` kL2 ([−1,1],wβ ) .
Note that requiring W ∈ L2 (Sd−1 × Sd−1 , σ ⊗ σ) is equivalent to p ∈ L2 ([−1, 1], wβ ).

8

3

THE SPHERE EXAMPLE, PRELUDE OF SYMMETRIC COMPACT SPACES

Let R ≥ 0 and define
e :=
R

R
X


 

R+d−1
R+d−2
d` =
+
,
R
R−1
`=0

(11)

where the last equality is obtained with the telescoping sum using (8). Furthermore, we get that
e≤
R

2(R + d − 1)d−1
= O (Rd−1 ),
(d − 1)!

and this quantity is the dimension of Spherical Harmonics of degree less than R.

3.2. A Glimpse into Weighted Sobolev Spaces
Some of our result concern “smooth graphons” for which a regularity assumption is required. Following [27], we can define our approximation space defining the “Weighted Sobolev” space with the
eigenvalues of the Laplacian on the Sphere. More precisely, let s > 0 a regularity parameter and
P
β
f ∈ L2 ((−1, 1), wβ ) such that f = `≥0 f`? c` G` in L2 , we define
kf

k∗Z s ((−1,1))
w
β

=

∞
X
`=0

 21

d` | f`? |2 (1 + (`(` + 2β

+ 1)) )

k f k∗Z s

((−1,1))

s

and

Zws ((−1, 1)) = f ∈ L2 ((−1, 1), wβ ) :
β

wβ

<∞ .

Then, if p belongs to the Weighted Sobolev Zws ((−1, 1)) with smoothness s > 0, it holds
β

X
`>R

d` (p?` )2 =

X
`>R

d` (p?` )2

1 + (`(` + 2β + 1))s
≤ C(p, s, d)R−2s ,
1 + (`(` + 2β + 1))s

(12)

where C(p, s, d) > 0 is a constant that may depend on p, s or d.

3.3. Spectrum Consistency of the Matrix of Probabilities
Under this framework, Corollary 3 can be written as follows.
Proposition 4. There exists a universal constant C > 0 such that for all α ∈ (0, 1/3) and for all n3 ≥
e log(2R
e/α), it holds
R
δ2 (λ(T n ), λ? ) ≤ 2

X
`>R

d` (p?` )2

 21

+C

q

e(1 + log(R
e/α))/n
R

with probability at least 1 − 3α. Moreover, if p belongs to the Weighted Sobolev space Zws ((−1, 1)), then
β
for n large enough

 2s
n − 2s+(d−1)
E[δ22 (λ(T n ), λ? )] ≤ C 0
log n
where C 0 only depends on s, d and kpk∗Z s

wβ

((−1,1))

.

A proof can be found in Appendix A.7. These theoretical results show that the eigenvalues of T n converges
towards the unknown spectrum λ? .

3.4

Nonparametric Estimation of the Kernel Spectrum

9

3.4. Nonparametric Estimation of the Kernel Spectrum
Let us now define our estimation procedure. Recall that we observe a graph and then its n × n adjacency
matrix A, where Ai j are independent Bernoulli random variables. Our model is that
P{Ai j = 1} = (Θ0 )i j = W (X i , X j ) = p(〈X i , X j 〉),

1 ≤ i < j ≤ n,

where X 1 , . . . , X n are i.i.d. uniform variables on Sd−1 . Our aim is to recover the envelope function p
using only observations A, the variables X i being unobserved. The idea is to estimate the coefficients p?`
of p in the Gegenbauer polynomial basis, using that

λ? := p?0 , p?1 , . . . , p?1 , . . . , p?` , . . . , p?` , . . .
is close to λ(T n ) and this latter is close to the spectrum
b n)
λ := λ( T
b n = (1/n)A. Let us fix R ≥ 0 some resolution level, and denote
of our observable T

λ?R := p?0 , p?1 , . . . , p?1 , . . . , p?R , . . . , p?R
| {z }
|{z} | {z }
dR

d1

d0

the first coefficients of p, i.e., the first eigenvalues of TW —not necessarily the largest. In view of (9) and
e as in (11), we understand that the R
e first eigenvalues of TW belong to the convex set
defining R
©
¦
e
MR := ( u?0 , u?1 , . . . , u?1 , . . . , u?R , . . . , u?R ) ∈ RR .
| {z }
|{z} | {z }
d0

d1

(13)

dR

[0,1]
MR

Remark 2. Consider the convex set
of coefficients (u?0 , u?1 , . . . , u?1 , . . . , u?R , . . . , u?R ) corresponding to a
function between 0 and 1, namely
¦
e
[0,1]
MR
:= (u?0 , u?1 , . . . , u?1 , . . . , u?R , . . . , u?R ) ∈ RR s.t. there exists an extension (u?` )`>R
s.t. for a.e. t ∈ [−1, 1],

0≤

∞
X
`=0

[0,1]

Note that λ?R ∈ MR

©
β
u?` c` G` (t) ≤ 1 .

and that for all x ∈ MR
δ2 (PM [0,1] (x), λ?R ) ≤ δ2 (x, λ?R )
R

[0,1]

where PM [0,1] denotes the L2 -projection onto MR
R

. It follows that all the results presented applies if we

[0,1]
MR .

substitute MR by
But, since we do not use the fact that the coefficients (u?0 , u?1 , . . . , u?1 , . . . , u?R , . . . , u?R )
correspond to a function between 0 and 1 in our proofs and our numerical study, we choose to alleviate
[0,1]
presentation using MR instead of MR .
bR
e and we denote Sn the set of all permutation of [n]. We define the estimator λ
We assume that n ≥ R
as the closest sequence to λ which belongs to the set of “admissible” spectra MR as follows:
b R ∈ arg min min
λ
u∈MR

σ∈Sn

e
R
n
X
¦X
©
(uk − λσ(k) )2 +
λ2σ(k) .
k=1

(14)

e+1
k=R

b R , such that
b n . We denote p
bR` the stage values of λ
where we recall that λ denotes the spectrum of T
b R = (λ
bR, . . . , λ
b R ) = (b
bR1 , . . . , p
bR1 , . . . , p
bRR , . . . , p
bRR ).
λ
pR0 , p
1
e
R

10

3

THE SPHERE EXAMPLE, PRELUDE OF SYMMETRIC COMPACT SPACES

One can check that
bR`
p

è
1 X
=
λσ(k)
d`
Þ
k=`−1

where σ (that depends on R) is a permutation achieving the minimum in (14) and we use the notaÝ = 1. Furthermore, the true complexity of this estimator is not n! which
tion (11) with the convention −1
matches the complexity of Sn . The true computation complexity of our estimator is at most (R + 2)! as
shown by the next theorem.
e ≤ n. For any sequence of real numTheorem 5 (Computational Complexity). Let R ≥ 0 such that R
bers (λk )nk=1 such that λ1 ≥ λ2 ≥ . . . ≥ λn it holds that
∃HR ⊆ Sn s.t. ∀u ∈ MR , min

σ∈Sn

e
e
R
n
R
n
X
X
¦X
©
¦X
©
(uk − λσ(k) )2 +
λ2σ(k) = min
(uk − λσ(k) )2 +
λ2σ(k)
k=1

σ∈HR

e+1
k=R

k=1

e+1
k=R

where the set HR depends only on R and has size at most (R + 2)!.
A proof can be found in Appendix B.1. This proof is constructive and it gives the expression of HR .
Remark 3. Remark that the hypothesis λ1 ≥ λ2 ≥ . . . ≥ λn is not necessary and can be removed. Indeed, if
τ ∈ Sn a permutation such that λτ(1) ≥ λτ(2) ≥ . . . ≥ λτ(n) then it holds that
∃HR ⊆ Sn s.t. ∀u ∈ MR , min

σ∈Sn

e
e
R
n
R
n
X
X
¦X
©
¦X
©
(uk −λσ(k) )2 +
λ2σ(k) = min
(uk −λσ◦τ(k) )2 +
λ2σ◦τ(k)
k=1

σ∈HR

e+1
k=R

k=1

e+1
k=R

where the set HR depends only on R and has size at most (R + 2)!.
Remark 4. Interestingly the computational complexity of our estimateur depends linearly on the sample
size n which is important when observing large networks. However, it depends as R exp R in the complexity R
of the model. Hence, it is relevant for large networks and low degree R kernels. However, if the experimenter
knows that the eigenvalues are monotone (when sorting the eigenvalues so that the corresponding eigenspaces
have increasing dimensions) then the complexity is linear in R.
b R is a relevant estimator of the true first
Using Proposition 1 and Theorem 4 we can prove that λ
?R
eigenvalues λ as shown in the next theorem.
Theorem 6. There exists a universal constant κ0 > 0 such that the following holds. For all α ∈ (0, 1), if
e)3 ∨ R
e log(2R
e/α), with probability greater that 1 − 3α, it holds
n3 ≥ (2R
b R , λ?R ) ≤ 4δ2 (λ?R , λ? ) + κ0
δ2 (λ

Ç


e 1 + log R
e/α /n.
R

e then
Moreover, there exists a universal constant κ1 > 0 such that, if n ≥ 2R
¦
©
e
b R , λ?R )] ≤ κ1 δ2 (λ?R , λ? ) + R log n .
E[δ22 (λ
2
n
A proof can be found in Appendix A.8.
To go further we need to analyze the behavior of the bias term δ2 (λ?R , λ? ) as a function of R under some
regularity conditions on the envelope p. Indeed we can write
δ2 (λ?R , λ? )2 =

X
e
k>R

|λ?k |2 =

X
`>R

d` (p?` )2 .

3.5

Adaptation to the Smoothness of p

11

Assume that p belongs to the weighted Sobolev space Zws ((−1, 1)) of regularity s > 0 defined in
β

1

e = O (Rd−1 ), using (12) and setting Ropt = b(n/log n) 2s+d−1 c, we get
Section 3.2. Thus, since R
2s
e log n  n − 2s+(d−1)


R
b Ropt , λ? ) ≤ 2δ2 (λ?Ropt , λ? ) + 2 E δ2 (λ
b Ropt , λ?Ropt ) ® R−2s + opt
E δ22 (λ
®
.
2
2
opt
n
log n

Thus we recover a classical nonparametric rate of convergence for the estimation of a function with
smoothness s in a space of dimension d − 1, see [17] for instance. We also face a classical issue of
nonparametric statistics: how to choose R, given that the best theoretical choice Ropt depends on the unknown
smoothness s? This is the point of the next section.

3.5. Adaptation to the Smoothness of p
e max ≤ n. Following the GoldenshlugerLet us define R = {1, 2, . . . , Rmax } the possible values for R, with 2R
Lepski method [15], set
v
t e0
¦
©
0
0
bR , λ
b R ∧R ) − κ R log n ,
B(R) := max
δ
(
λ
(15)
2
R0 ∈R
n
where κ > 0 is a constant to be specified later. This function can be seen as an estimation of the (unknown)
b as a minimizer of an approximation of the
bias δ2 (λ?R , λ? ). Then we define our final resolution level R
risk as
v
te
¦
R log n ©
b ∈ arg min B(R) + κ
.
(16)
R
n
R∈R
b Rb , which depends on the choice of constant κ in (15) and (16). The following
The estimator of λ? is then λ
b R )R∈R , up to a constant C,
results shows that this estimator is as good as the best one of the collection (λ
provided that κ is large enough.
b Rb the estimator defined by (14), (15) and (16). There exist numerical constants C > 0
Theorem 7. Let λ
p
and κ0 > 0 (as in Theorem 6) such that , if κ ≥ κ0 11, with probability 1 − 3n−8
v
te
¦
R log n ©
b
?R
?
R
?
b
δ2 (λ , λ ) ≤ C min δ2 (λ , λ ) + κ
.
R∈R
n
p
Moreover, for κ ≥ κ0 5, there exists a numerical constant C 0 > 0 such that
¦
©
e
b Rb , λ? )] ≤ C 0 min δ2 (λ?R , λ? ) + κ2 R log n .
E[δ22 (λ
2
R∈R
n
p
A proof can be found in Appendix A.10. Thus we choose κ ≥ κ0 5 in (15) and (16), the practical choice
of the tuning constant κ will be tackled in Section 5. Note also that the interesting choice of R is such
1
that Ropt ∈ R which is the case for cn 2s+d−1 ≤ Rmax where c > 0 is a constant. A more simple choice
e max ≤ n where 0 < c < 1 is a constant. In these cases, we get the following rate
of Rmax may be cn ≤ 2R
of convergence.
Corollary 8. Assume that p belongs to the Weighted Sobolev space Zws ((−1, 1)). Then there exists a constant
β
C > 0 depending only on kpk∗Z s ((−1,1)) , s and d such that
wβ

b R , λ? )] ≤ C
E[δ22 (λ
b



n
log n

2s
− 2s+(d−1)

.

12

3

THE SPHERE EXAMPLE, PRELUDE OF SYMMETRIC COMPACT SPACES

b to the unknown smoothness s of p: it chooses a
This means that the algorithm automatically adapts R
b for irregular functions, that provides the
small resolution level for smooth functions and a greater R
best result in each case. Assuring that this is the optimal rate of convergence is beyond the scope of this
2s
paper but we believe that it cannot converge faster than n− 2s+(d−1) , since it is the usual rate for estimating
a function in a (d − 1)-dimensional context.
The final step is to define the following estimator of envelope p by
∀t ∈ [−1, 1],

bR (t) :=
p
b

b
R
X
`=0

β

bR` c` G` (t) .
p
b

(17)

3.6. Estimating the envelope function
Inferring from the estimation of λ? to the estimation of p, we face an identifiability problem. Indeed,
consider for instance the case d = 3, which implies β = 1, d` = 2` + 1, c` = 2` + 1. For µ > 0, let
1
β
β
β
β
β
c0 G0 + µc1 G1 + 0 × c2 G2 + 0 × c3 G3 + µc4 G4 ,
2
1
β
β
β
β
β
p b = c0 G0 + 0 × c1 G1 + µc2 G2 + µc3 G3 + 0 × c4 G4
2
pa =

Then the associated spectrum are
λ?a = (1/2, µ, µ, µ, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, µ, µ, µ, µ, µ, µ, µ, µ, µ)
{z
} |
| {z } | {z } |
{z
}
3

λ?b

5

7

9

= (1/2, 0, 0, 0, µ, µ, µ, µ, µ, µ, µ, µ, µ, µ, µ, µ, 0, 0, 0, 0, 0, 0, 0, 0, 0)
| {z } | {z } |
{z
}
{z
} |
3

5

7

9

p
which are indistinguishable in δ2 metric, although kpa − p b k2 = µ 24. Furthermore, note that, for
µ ≤ 1/24, these functions have values in [0, 1].
Remark 5. A natural question is then: Can we recover the right eigenvalues labels from the empirical
eigenvectors?
Under stronger requirements (RKHS-type assumptions), convergence of the eigenvectors of A/n towards
the eigenfunctions of the integral operator TW may be proved as in [33]. Essentially, it is possible to prove
that the orthogonal projections Π` onto eigenspaces of A/n are closed in operator norm to the n × n matrix
Pd`
with entries j=1
Y` j (X i )Y` j (X j ) given by the Zonal Harmonics. Unfortunately, this statistics depends on
the latent points and suffers from the “agnostic” error as explained in [19]. While possible theoretically, it
seems difficult in practice to use the information of the observed eigenvectors to uncover the right labels of
the eigenvalues.
Nevertheless we can state a result in the case of a finite spectrum of distinct eigenvalues.
Proposition 9. Assume that the envelope function p is polynomial of degree D, i.e., p?` = 0 for any ` > D
and p?D 6= 0. Assume also that all nonzeros p?` for ` ∈ {0, . . . , D} are distinct. If R ≥ D and n is large enough
then
e log n
R
kb
pR − pk22 ≤ 11κ20
,
n
with probability greater that 1 − 3n−8 where κ0 > 0 is the constant defined in Theorem 6. Furthermore, it
holds
e log n
R
,
E[kb
pR − pk22 ] ≤ (18 + 4κ20 )
n
for n large enough.

13
A proof can be found in Appendix A.11. Note that we uncover (up to a log factor) the parametric rate
of estimation. Let us now state what the adaptive procedure defined by (15) and (16) can do in this
polynomial case.
Corollary 10. Assume that the envelope function p is polynomial of degree D, i.e., p?` = 0 for any ` > D
and p?D 6= 0. Assume also that all nonzeros p?` for ` ∈ {0, . . . , D} are distinct. If Rmax ≥ D, there exists a
b ≥ D a.s. and
numerical constant C such that, if n large enough, then R
b
e
E[kb
pR − pk22 ] ≤ C D




log n
.
n

A proof can be found in Appendix A.12. Here again, the parametric rate of estimation is attained by the
adaptive procedure.

4. Extensions to Compact Symmetric Spaces

The aim of this section is to extend the previous result on spheres to numerous spaces such as compact
Lie groups and compact symmetric spaces. A useful reference might be the books [36, 9] or the nice
survey written in [25, Chapter 3] (see also [24] for a presentation of compact symmetric spaces) which
has been useful to polish this section.

4.1. Harmonic Analysis on Compact Symmetric Spaces
In this section, we consider that (S, γ) is a compact Lie group with an invariant Riemannian metric γ,
or more generally a compact symmetric space. The definitions will be given below when describing
Cartan’s Classification and, to be specific, this section focuses on (semi)simple connected compact Lie
groups (sscc in short) and simple simply connected compact symmetric spaces (ssccss in short). These
structures encompass spheres, projective spaces, Grassmannians, and orthogonal or unitary groups; and
one can handle explicit eigenvectors computations in this framework.
Consider again that the graphon W (g, h) depends only on (the cosine of) the distance γ(g, h) (normalized
so that the range of γ equals [0, π]) between points g, h ∈ S such that
W (g, h) = p(cos γ(g, h)) = p(cos γ(gh−1 , eS )) =: p(gh−1 )
where eS denotes the identity element and p(g) = p(cos γ(g, eS )). Also we assume that 0 ≤ W ≤ 1
since W defines a probability matrix. In particular, W is square-integrable on the compact S × S. Observe
that estimating W reduces to estimate p that reduces to estimate p and vice versa. By definition of the
distance, note that
• When S is a sscc Lie group, the function p is invariant by conjugation, namely p(hgh−1 ) = p(g)
for any latent points g, h ∈ S. We denote by L2 (S)S the space of square-integrable functions p on S
that are invariant by conjugation.
• When S = G/K is a ssccss, the function p is bi-K-invariant, namely p(k1 gk2 ) = p(g) for any
k1 , k2 ∈ K and g ∈ G. We denote by L2 (K \G/K) the space of square-integrable functions on G
that are bi-K-invariants.
In particular, Peter–Weyl’s decomposition (presented below) gives an L2 -decomposition of p in these
settings. The measure on S is the Haar measure (normalized to be a probability measure), denoted dg,
standardly defined for any compact topological group S. The harmonic analysis on S is based on the

14

4

EXTENSIONS TO COMPACT SYMMETRIC SPACES

Fourier transform of the space L2 (S, dg) of square integrable (complex valued) functions on S. This
space L2 (S, dg) is a Hilbert space for the scalar product
Z
〈 f1 , f2 〉 =

f1 (g) f2 (g)dg .

S

We define also the convolution product
( f1 ∗ f2 )(g) =

Z

f1 (gh−1 ) f2 (h)dh .

S

Now, recall that W defines a symmetric Hilbert-Schmidt operator TW on L2 (S, dg) and the spectral
theorem (6) gives
X
W (g, h) =
λ?k φk (g)φk (h) ,
k≥1

for an L (S, dg)-orthonormal basis (φi )i≥1 . Remark also that
Z
Z
2

(TW ( f ))(g1 ) =

W (g1 g2−1 , eS ) f

W (g1 , g2 ) f (g2 )dg2 =

S

(g2 )dg2 =

S

Z

p(g1 h−1 ) f (h)dh = (p ∗ f )(g1 )

S

for all f ∈ L (S, dg). We deduce that TW is the convolution on the left by p. We continue with a short
reminder on harmonic analysis on compact groups and compact quotients.
2

Representation of Compact Groups and Irreducible Characters The first ingredient is representations of any compact group S. It is defined by a finite dimensional complex vector space V and
by a continuous morphism of groups ρ : S → GL(V ) where GL(V ) denotes the group of isomorphisms of V . A linear representation (V, ρ) is irreducible if one cannot find a subspace W such that
0 ( W ( V and that is S-stable, i.e., for all w ∈ W and all g ∈ S, one has ρ(g)(w) ∈ W . If V is a
linear representation then one can always split it into irreducible components
M
V=
mr V r
b
r∈S

b is the countable set of isomorphism classes of irreducible representations r = (ρ r , V r )
where S
of S and mr ≥ 1. Furthermore, we denote by
chr (g) = tr(ρ r (g)) ,
the irreducible characters associated to the irreducible representation r = (ρ r , V r ) of S where tr
denotes the trace operator on EndC (V r ) the set of (complex) endomorphisms of V r . In particular,
since ρ r (g) is unitary, it holds
∀g ∈ S,

|chr (g)| ≤ dr = chr (eS ) ,

where dr is the dimension of V r . Also, note that
chr ∗ chs =

δrs r
ch ,
dr

where δrs denotes the Kroneker delta.
Peter–Weyl’s Decomposition The Peter–Weyl’s Decomposition shows that (chr )r∈Sb is an orthonormal
basis of L2 (S)S . It follows that
X
p=
〈p, chr 〉chr
b
r∈S

in L (S) . Using that TW is a left convolution operator by p, we find that (chr )r∈Sb is an eigenfunction
basis of TW associated to the eigenvalues (λ?r )r∈Sb given by
2

S

λ?r =
with multiplicity dr2 = dim(EndC (V r )).

〈p, chr 〉
,
dr

4.1

Harmonic Analysis on Compact Symmetric Spaces

15

Compact Gelfand Pairs and Zonal Spherical Functions There is an extension of this decomposition
to quotients S = G/K of a compact topological group G by a closed subgroup K. The most
convenient setting for this extension is the one of compact Gelfand pairs defined as follows.
Definition (Gelfand Pair). We say that (G, K) is a Gelfand pair if for any irreducible representation V r
of G, the space of K-fixed vectors
¦
©
V r,K = v ∈ V r : ∀k ∈ K , ρ r (k)(v) = v
has dimension at most one.
b K the set of
An irreducible representation V r is called spherical if dimC (V r,K ) = 1. We denote by G
K
r
b
spherical representations of the Gelfand pair (G, K). If r ∈ G then we denote by e a unit vector
vector in V r,K which is unique up to a multiplicative complex constant of modulus one. The zonal
spherical functions
Æ
zonr (g) = dr er , ρ r (g)(er ) V r
where dr is the dimension of V r . In particular, since ρ r (g) is unitary and er normalized, it holds
Æ
∀g ∈ G, |zonr (g)| ≤ dr = zonr (eG ) ,
(18)
where eG is the identity element of G. Also, note that
δrs
zonr ∗ zons = p zonr .
dr
Cartan’s Extension of Peter–Weyl’s Decomposition In the case of bi-K-invariant functions on G, an
extension of Peter–Weyl’s decomposition theorem shows that (zonr )r∈Gb K is an orthonormal basis
of L2 (K \G/K). It follows that
X
p=
〈p, zonr 〉zonr
bK
r∈G

in L (K \G/K). Using that TW is a left convolution operator by p, we find that (zonr ))r∈Gb K is an
eigenfunction of TW associated to the eigenvalue (λ?r )r∈Gb K given by
2

λ?r =

〈p, zonr 〉
.
p
dr

with multiplicity dr = dim(V r ). The reader may recognize here the case of the sphere studied in
the previous section.
Cartan’s Classification of sscc Lie Groups and ssccss Now, a crucial question is how explicit are these
decompositions. We begin with the notion of sscc Lie Groups that is based on Cartan’s criterion
for semisimplicity. It implies that a simply connected compact Lie group can always be written as
a direct product of simple simply connected compact Lie group (in short sscc Lie group). Here,
by simple we mean a Lie group S whose Lie algebra is simple, that is nonabelian and without
non-trivial ideal. Interestingly, Cartan’s classification of sscc Lie groups shows that any sscc Lie
group fall into one of the following infinite families:
Group type
•
•
•
•

Special unitary group SU(n + 1),
Odd spin group Spin(2n + 1),
Compact symplectic group USp(n),
Even spin group Spin(2n),

or, it is one of the five exceptional compact Lie groups.
The sscc Lie groups belong to a larger class of compact Riemannian manifolds called symmetric
spaces. Moreover, any simply connected compact symmetric space is isometric to a product of
simple simply connected compact symmetric spaces (in short ssccss), which cannot be split further.
A classification of all the ssccss S has been proposed by Cartan which shows that S is either of
Group type (see above) or one of the following objects

16

4

EXTENSIONS TO COMPACT SYMMETRIC SPACES

non-Group type In this case, S falls into one of the following infinite families:
• Real Grassmannians SO(p + q)/(SO(p) × SO(q)),
• Complex Grassmannians SU(p + q)/(SU(p) × SU(q)),
• Quaternionic Grassmannians USp(p + q)/(USp(p) × USp(q)),
• Space of real structures on a complex space SU(n)/SO(n),
• Space of quaternionic structures on an even complex space SU(2n)/USp(n),
• Space of complex structures on a quaternionic space USp(n)/U(n),
• Space of complex structures on an even real space SO(2n)/SU(n),
or, it is one of the twelve exceptional sscc symmetric spaces.
Remark that, for all the ssccss examples, the eigenfunctions of the spectral decomposition of TW
do not depend on TW and they are irreducible characters in the group case and zonal spherical
functions in the non-group case.
Weyl’s Highest Weight theorem and Cartan–Helgason’s Extension Given a ssccss, we can make exb in the group case, and the set G
b K in the non-group case thanks to the Weyl’s
plicit the set S
highest weight theorem and Cartan–Helgason’s extension, see [25, Chapter 3] for a short and well
written introduction. The highest weight theorem is completed by a formula for the irreducible
character chr of the module V r with highest weight r, see for instance [9, Chapter 22] and Weyl’s
integration formula [9, Chapter 17].
The same analysis can be lead in the non-group case. The only additional difficulty is the manipulation of zonal spherical functions. This issue will be handled by considering compact symmetric
spaces of rank 1 in the following.
Now, we are ready to extend the previous results on the sphere to other latent spaces S, namely the
compact symmetric spaces of rank 1.

4.2. Compact Symmetric Spaces of Rank One

We focus here on the interesting case of compact symmetric spaces of rank one for which the zonal
spherical functions can be explicitly computed. Indeed, one has the following classification of the compact
symmetric spaces of rank one and of the corresponding spherical representations, see [25, Chapter 3]
and [35] for instance. A compact symmetric space of rank one is ssccss that is 2-point homogeneous,
namely
• [Compact Symmetric Spaces of Rank One] Given two pairs of points (x 1 , x 2 ) and ( y1 , y2 ) such
that γ(x 1 , x 2 ) = γ( y1 , y2 ), there is an isometry of S that maps x 1 (resp. x 2 ) onto y1 (resp. y2 ).
The compact symmetric spaces of rank one are
•
•
•
•
•

the real spheres Sd−1 = SO(d)/SO(d − 1),
the real projective spaces RPd−1 = SO(d)/O(d − 1),
the complex projective spaces CPd−1 = SU(d)/U(d − 1),
the quaternionic projective spaces HPd−1 = USp(d)/(USp(d − 1) × USp(1)),
or the octonionic projective plane OP2 = F4 /Spin(9).

In the case of compact symmetric spaces of rank 1, one can explicitly described the spherical repreb K . The dimension d` := dimC (V `ω0 ) of the `-th spherical representation V `ω0 are given in
sentations G
Table 1. One can even describe the zonal spherical functions of these spaces, and thus compute the
eigenvalues p?` (recall that their multiplicities d` are given by Table 1).

4.2

Compact Symmetric Spaces of Rank One

17

For compact symmetric spaces of rank one, on can define
• a probability density function w(t) on [−1, 1] defined as the density of the pushforward measure
of the Haar measure by the map x 7→ t = cos(γ(x, e)),
• the pushforwards Z` on [−1, 1] of the zonal spherical functions, normalized so that they are an
orthonormal basis of L2 ([−1, 1], w), the space of square-integrable functions with respect to the
weight function w on [−1, 1].

S

e=
R

d`

X

d`

t = cos(γ(x, e))

Density w

xd

d−1
Beta( d−1
2 , 2 )

0≤`≤R

Sd−1

`+d−1
`



`+d−3
`−2

−

RPd−1

(6+d2 +8`(2`−3)+d(8`−5))Γ (d+2`−3)
Γ (d−1)Γ (1+2`)

CPd−1


2`+d `+d−1 2
d−1
d

−

2R+d−1 R+d−1
d−1
R+d−1





4R+d−1 2R+d−1
d−1
2R+d−1


2`+d−2 `+d−2 2
d−1
d


2R+d R+d−1 2
d−1
d

HPd−1

2(`+1)(d(4d2 −1)+2d(4d−1)`+(4d−1)`2 )Γ (2d+`−1)Γ (2d+`)

OP2

(4+`)(5+`)2 (6+`)

Γ (2d)Γ (2+2d)Γ (2+`)2

2R+2d+1
(2d+1)(R+1)
2R+11
385

924

2
x d2 −x 12 −···−x d−1




R+2d


R+2d−1

2d

2d−1


R+7


R+10

4

10

x 12 +···+x d2

1
Beta( d−1
2 , 2)

|x d |2 −|x 1 |2 −···−|x d−1 |2
|x 1 |2 +···+|x d |2

Beta(d − 1, 1)

|x d |2 −|x 1 |2 −···−|x d−1 |2
|x 1 |2 +···+|x d |2

Beta(2d − 2, 2)

|x 3 |2 −|x 1 |2 −|x 2 |2
|x 1 |2 +|x 2 |2 +|x 3 |2

Beta(8, 4)

TABLE 1
Review of the dimensions d` of the spherical representations, the distance cos(γ(x, e)) to the identity e, the weight function w(t) of the
compact symmetric spaces S of rank 1. These latter are respectively the density w and the orthonormal polynomials of the beta law
on [−1, 1] with shape parameters (α, β), see (19).

In Table 1, one hase the following standard parameterizations of latent space S:
• the real sphere Sd−1 is endowed with the coordinates x = (x 1 , . . . , x d ) such that ||x||2 = 1 and the
“north pole” is given by e = (0, . . . , 0, 1). We denote the “weight function” by w(x), it is the density
of the push forward measure of the Haar measure by the map x 7→ cos(γ(x, e)) where we recall
that γ(x, e) = arccos x d .
• the projective space FPd−1 (where F = R, C, H or O) is endowed with projective coordinates
[x 1 : x 2 : · · · : x d ] with the x i ’s in F, and the “north pole” is given by e = [0 : · · · : 0 : 1]. We denote
the “weight function” by w(x), it is the density of the push forward measure of the Haar measure
by the map x 7→ cos(γ(x, e)) where we recall that γ(x, e) = 2 arccos(|x d |/||x||2 ).
One can show that the Jacobi polynomials (resp. beta distributions on [−1, 1]) are the pushforward
zonal spherical functions Z` (resp. the Haar measure) with shape parameters (α, β) depending on the
base field and the dimension, see Table 1. In the case of real spheres, these Jacobi polynomials are the
Legendre/Gegenbauer polynomials seen in Section 3. We recall that for shape parameters (α, β) the
beta density distribution w is given by
w(t) =

Γ (α + β)
(1 − t)α−1 (1 + t)β−1 1[−1,1] (t) ,
2α+β−1 Γ (α)Γ (β)

(19)

where Γ is the Gamma function. In particular, recall that one has
p=

XÆ
`

d` p?` Z`

and

1
p?` = p 〈p, Z` 〉L2 ([−1,1],w) ,
d`

in L2 ([−1, 1], w). We further assume that there exists s > 0, a (Sobolev) regularity parameter, such that
X
∀R ≥ 1 ,
d` (p?` )2 ≤ C(p, s, S) R−2s .
`>R

for some constant C(p, s, S) > 0 and for dimensions (d` )`≥0 that depends only on S.

18

5

NUMERICAL EXPERIMENTS

Now, recall the definition of the set of models MR in (13) (the dimensions (d` )`≥0 are given by Table 1),
b
b R in (14), of the adaptation R
b in (16), of p
bR in (17), and of T n in (3). Our estimation
of the estimator λ
e and
procedure is the same as in the sphere example the only difference is that the dimensions (d` )`≥0 , R
the zonal spherical function Z` depend on the latent space under consideration, see Table 1.
Theorem 11. Let S be a compact symmetric space of rank one with Riemanian dimension d − 1. There
exist constants C0 , C1 , C2 , κ0 , κ1 > 0 such that the following holds. Let α ∈ (0, 1/3) and n, R ≥ 0 such that
e and n3 ≥ R
e log(2R
e/α) where R
e is given in Table 1. Then it holds,
n ≥ 2R
• [Convergence of the matrix of probabilities]
δ2 (λ(T n ), λ? ) ≤ 2

X
`>R

d` (p?` )2

 12

+ C0

q

e(1 + log(R
e/α))/n
R

with probability at least 1 − 3α and
E[δ22 (λ(T n ), λ? )] = O




2s
n − 2s+(d−1)
.
log n

• [Convergence of the matrix of finite rank approximation]
Ç

b R , λ?R ) ≤ 4δ2 (λ?R , λ? ) + κ0 R
e 1 + log R
e/α /n.
δ2 (λ
with probability at least 1 − 3α and
b R , λ?R )]
E[δ22 (λ

≤ κ1



δ22 (λ?R , λ? ) +


e log n
R
.
n

p
• [Convergence of the adaptation] For κ ≥ κ0 11, it holds that
v
te
¦
©
b
?R
?
R
?
b , λ ) ≤ C1 min δ2 (λ , λ ) + κ R log n ,
δ2 (λ
R∈R
n
p
with probability 1 − 3n−8 . Furthermore, for κ ≥ κ0 5, it holds that
¦
©
e
b Rb , λ? )] ≤ C2 min δ2 (λ?R , λ? ) + κ2 R log n .
E[δ22 (λ
2
R∈R
n
A proof can be found in Appendix A.13. Note that the same results as in Proposition 9 and Corollary 10
hold when S is a compact symmetric space of rank one. Namely, adaptive estimation of the envelope
function p is possible when p is a polynomial.

5. Numerical Experiments
5.1. Simulations
In this section we shall assess the performances of our estimation procedure by estimating numerous
envelope functions p. We consider the example of S = S2 , the unit sphere in dimension d = 3. The
β
functions G` turn to be the Legendre polynomials and the dimension of the space of spherical harmonics
of degree ` is d` = 2` + 1.
bR of p,
First, we shall explain how our algorithm works in practice to compute the adaptive estimator p
see (14) and (17). For sake of clarity, we deal with a simple example. Suppose we are given an adjacency
matrix A of size 20 × 20 and we set Rmax = 1. Thus n = 20, d0 = 1 and d1 = 3.
b

5.1

Simulations

19

Step 1 Compute the 20 eigenvalues of A and sort them in decreasing order λ(1) ≥ · · · ≥ λ(20) , see
Figure 1.
Step 2 Take 0 ≤ R ≤ Rmax . Generate SR+2 , the set of all permutation of {0, d0 , . . . , dR }, the set with
R + 2 elements. The factor +1 in R + 2 = (R + 1) + 1 is due to the “zeros” (represented by the
symbol 0) to be placed, see Step 3 for a proper definition. For instance, for R = 1, we have

SR+1 =





σ1 = [d1 ,







σ2 = [d1 ,






 σ3 = [d0 ,



σ4 = [d0 ,







σ5 = [0,






 σ6 = [0,

d0 ,

0]

0,

d0 ]

d1 ,

0]

0,

d1 ]

d0 ,

d1 ]

d1 ,

d0 ]

Step 3 For each permutation σi,i∈{1,...,6} of SR+2 , compute the following (e
pσi ,` )`∈{0,1,2} which are the
“stage means” of the λ(i),i∈{1,...,20} ’s according to the order of appearance of the d` ’s in the permutation σi . For instance, for σ1 = [d1 , d0 , 0] (see Figure 1), we get
3

eσ1 ,2 =
p
and for σ4 = [d0 ,

0,

1X
λ(`) ,
3 `=1

eσ1 ,1 = λ(4) ,
p

eσ1 ,0 = 0,
p

d1 ] one gets
eσ2 ,1 = λ(1) ,
p

20
1X
eσ2 ,2 =
p
λ(`) .
3 i=18

eσ2 ,0 = 0,
p

eσi ,0 = 0.
In Step 2, we have called “zeros” the fact that we always set p

e σ of size 20, containing the p
eσi ,`
Step 4 For each permutation σi , compute the corresponding vector λ
i
with multiplicity d` . Then compute the risk Score(σi ) for each σi . For example for σ1 = [d1 , d0 , 0]
(see Figure 1), one gets
e σ = (e
eσ1 ,2 , p
eσ1 ,2 , p
eσ1 ,1 , 0, . . . , 0 )
λ
pσ ,2 , p
1
| {z }
| 1
{z
} |{z}
d0 =1 n−d0 −d1 =16

d1 =3

and its risk is Score(σ1 ) =

20
X
eσ1 ,` )2 .
(λ(`) − p
`=1

Step 5 Select the permutation σmin such that σmin = arg min Score(σi ).
σi

b R defined by
Step 6 Get the estimate λ
b R = (e
eσ ,2 , p
eσmin ,2 , p
eσmin ,2 ) = (b
bR1 , p
bR1 , p
bR1 ) ,
λ
pσmin ,1 , p
pR0 , p
| {z } | min
{z
}
d0 =1

d1 =3

see (14).
b according to (16) and the adaptive
Step 7 Iterate Steps 2 to 6 for R = 0 to Rmax . Compute the level R
b
R
b (t) according to (17).
estimator p
b
bR (t) so as to it belongs to [0, 1].
Step 8 Troncate p

20

5

NUMERICAL EXPERIMENTS

0.7
Sorted Eigenvalues of A
λ̃σ(1)

0.6
0.5
0.4
0.3
0.2
0.1
0
-0.1
-0.2
0

5

10

15

20

e σ(1) .
FIGURE 1. Plot of the 20 sorted eigenvalues λ(i) of adjacency matrix A and the values of vector λ

Of course, the choice of level R is crucial and the estimation is sensitive to R. That is why we use our
selection method, as described in Section 3.5 (see Step 7 in the description of the algorithm above). As
almost all estimators selection methods, this Goldenshluger-Lepski method uses an hyper-parameter κ.
Our theoretical result ensures a good performance as soon as κ is large enough, but it is well known
that a more precise choice is better in practice. Heuristics exist to calibrate κ, but they are all based on
the behavior of the estimator for very large R (see for instance [3]). Hence these techniques are not
possible here, due to the computational cost of the estimation when R is large (we can hardly consider
larger than Rmax = 7 because of the complexity in (Rmax + 2)!). Fortunately, the stability of the estimation
allows us to choose here a fixed κ, namely κ = 0.25, and this choice ensures good selection of R̂ for a
wide range of functions p.
Now, let us deal with the estimation of the six following envelope functions p
p1 (t) =

 1 + t 4
2

,

p2 (t) = 1 t>0.7 ,
2

p3 (t) = e−(t−1) ,


p4 (t) = 0.5 + 0.5 sin πt/2 ,

1
1 
p5 (t) = +
35t 4 − 30t 2 + 3 ,
3 12
p6 (t) = t 10 1 t>0 .
We consider graphs of size n = 5000. We set Rmax = 4 and κ = 0.25 for the adaptive selection rule of R,
see (16).
Figure 2 presents our simulation results. For each envelope function p, we represent on the top side,
b
bR` and the true coefficients p?` with their multiplicity 2` + 1. On the bottom
the estimated coefficients p
b and the true p. Note that our procedure is not
side, we represent the estimated envelope function p
constrained by dealing with envelope functions p defining positive kernels W . Such an example is given
by the step function p2 as its Fourier coefficients p?2,` ’s can be negative, see Figure 2.
The estimation of all functions are good except for the step function p2 which is more demanding
due to its discontinuity. Despite that function p6 is not easy to be estimated because of its flatness,
our estimation is satisfying. Furthermore, it is interesting to remark that except for p2 , the estimated
coefficients are very close to the true ones.

5.1

Simulations

21

0.2

estimated coefficients
true coefficients

0.2

estimated coefficients
true coefficients

0.1

0.1
0
0
0

2

4

6

8

10

12

14

16

1

0

0.5

−0.5

0

0.5

1

estimated coefficients
true coefficients

0.4

2

4

40

−0.5

0

0.5

1

estimated coefficients
true coefficients

6

8

10

12

14

16

−0.2
0

2

4

6

8

10

12

14

16

1

estimated p4

true p3

0
−1

0.5

−0.5

0

0.5

1

0.4

true p4

0
−1

−0.5

0

0.5

1

0.05

estimated coefficients
true coefficients

0.2

estimated coefficients
true coefficients

0.04
0.03
0.02

0
5

10

15

20

25

5

10

15

20

25

estimated p6

5

−0.5

0.01
0
1

estimated p5
true p

0
−1

35

true p2

0
−1

estimated p3

0.5

30

0

1

1

25

0.2

0

0

20

0.4

0.2

0.5

15

estimated p2

true p1

0
−1

−0.2
0

10

1

estimated p1
0.5

5

0.5

0

0.5

1

0
−1

true p6

−0.5

FIGURE 2. Estimation of envelope functions p1 , . . . , p6 .

0

0.5

1

22

5

NUMERICAL EXPERIMENTS

5.2. Real data: Grévy’s zebras in Kenya
To depict our estimator on real datas, we use the dataset provided by the Koblenz Network Collection
(http://konect.uni-koblenz.de/). This dataset is presented as follows: “This undirected network contains
interactions between 27 Grévy’s zebras in Kenya. A node represents a zebra and an edge between two zebras
shows that there was an interaction between them during the study”. For further information about the
study, the reader may consult [30]. We display the undirected graph structure of this dataset on Figure 3.
18
●

25
●

22
23
●
●
17
●
13
15
●
●
12
●
21
●

20
●

11
●

16
●

24
●

1
●

10
●
9
●
8
●

27
●

4
●

5
●

2
●
3
●
7
6
●
●

26
●

14
●

●
19

FIGURE 3. Layout of the zebras’ network

We aim at estimating the envelop function p. We compute the adjacency matrix A and its eigenvalues
(see Figure 4). Considering that n is small, we may discard large d values (high dimensional spheres).
Furthermore, the spectrum of A displays two clear stages of size 1 and 3, hence we set d = 3 (since
d1 = d where d1 is the multiplicity of the eigenvalue λ1 ). Next we implement our adaptive estimation
procedure from Step 1 until Step 8 described in Section 5.1 with Rmax = 4 and κ = 0.25. The procedure
selects R̂ = 2.
0.5

0.8
Eigenvalues of A
Estimated Eigenvalues

0.4

Estimated p

0.7
0.6

0.3
0.5
0.2
0.4
0.1
0
-0.1
-0.2

0.3
9

18

27

0.2
0.1
0
-1

-0.5

0

0.5

1

FIGURE 4. Left panel: empirical (blue dots) and estimated (red crosses) spectra. Right panel: estimated envelop function.

Figure 4 shows that the estimated spectrum fits in a satisfying way the empirical one. It gives also the
b
bR . For this study, we may conclude that the zebras tend to interact with
estimated envelope function p
others which are moderately close to them but when they become too close, they less interact.
Acknowledgements: The authors would like to thank Pierre Loïc Méliot for many useful discussions on
compact symmetric spaces.

23
Appendix A: Proofs
A.1. Proof of Proposition 1
This result is a consequence of [2, Corollary 3.12] and [2, Remark 3.19] with X i j = Ai j − (Θ0 )i j a
e 2 = D 0 by definition, and observing that
centered but not symmetric random variable, " = 1/2 say, σ
2
e ∗ = maxi j ((Θ0 )i j ∨ (1 − (Θ0 )i j )) ≤ 1. It gives
σ

p
∀t > 0, P kA − Θ0 k ≥ 3 2D 0 + C t ≤ n exp(−t 2 ) ,
for some universal constant C > 0.

A.2. Proof of Theorem 2
Let R ≥ 1 and define

p
Φni := (1/ n)(φi (X 1 ), . . . , φi (X n )) ∈ Rn ,
KR := Diag(λ1 (TW ) . . . , λR (TW )) ∈ RR×R ,
ER,n := (〈Φni , Φnj 〉 − δi j )i, j∈[R] ∈ RR×R ,


X R,n := Φ1n · · · ΦRn ∈ Rn×R ,

 12
>
AR,n := X R,n
X R,n ∈ RR×R and note that A2R,n = IdR + ER,n ,
T R,n :=

R
X

>
λ r (TW )Φnr (Φnr )> = X R,n KR X R,n
∈ Rn×n ,

r=1

e R,n := ((1 − δi j )T R,n )i, j∈[n] ∈ Rn×n ,
T
T ?R,n := AR,n KR AR,n ∈ RR×R ,
and WR (x, y) :=

R
X

λi (TW )φi (x)φi ( y),

i=1

where the last identity holds point-wise. Observe that A2R,n = IdR + ER,n . It holds
δ2 (λ(TW ), λ(TWR )) =

X

 21
λ2r (TW ) .

(20)

r>R

Note the equalities between spectra λ(TWR ) = λ(KR ) and λ(T R,n ) = λ(T ?R,n ) where the last one follows
by using a SVD of X R,n . Hence, we deduce that
δ2 (λ(TWR ), λ(T R,n )) = δ2 (λ(KR ), λ(T ?R,n )) ≤ kT ?R,n − KR k F = kAR,n KR AR,n − KR k F ,
by Hoffman-Wielandt inequality, see [21, page 118] for instance. Equation (4.8) at [21, page 127] gives
that
p
p
δ2 (λ(TWR ), λ(T R,n )) ≤ 2kKR k F kER,n k = 2kWR k2 kER,n k ,
(21)
p
Actually, one can remove the constant 2 using Ostrowski’s theorem, see [7, Theorem A.2] for instance.
Also, by Hoffman-Wielandt inequality, we have
e R,n )) ≤ k T
e R,n − T R,n k F =
δ2 (λ(T R,n ), λ( T
and
e R,n ), λ(T n )) ≤ k T
e R,n − T n k F =
δ2 (λ( T

n
1 X
 12
2
W
(X
,
X
)
,
i
i
R
n2 i=1

 12
1 X
2
(W
−
W
)
(X
,
X
)
.
R
i
j
n2 i6= j

(22)

(23)

24

A

PROOFS

Invoke Lemma 12 to bound (21), Lemma 13 to bound (22) and Lemma 14 to bound (23).
PR
Lemma 12. Let R ≥ 1 and denote by ρ(R) := max(1, k r=1 φ r2 k∞ − 1) then it holds


P kER,n k ≥ t ≤ 2R exp −

∀t > 0,


n
t2
.
2ρ(R) 1 + t/(3n)

In particular, for all α ∈ (0, 1) and for n3 ≥ ρ(R) log(2R/α), it holds
v
¨
«
t ρ(R) log(2R/α)
P kER,n k ≥
≤ α.
n
Lemma 13. Let R ≥ 1 and α ∈ (0, 1) then, with probability at least 1 − α, it holds
v

n
t log(R/α)  2ρ(R)||W ||2
1 X 2
R
2
W (X i , X i ) ≤ 1 + max ||φ r ||∞
.
1≤r≤R
n2 i=1 R
2n
n
Lemma 14. It holds, for all α ∈ (0, 1),
(
)
v
t log(2/α)
X
X
1
2
2
2
P
≤ α.
(W − WR ) (X i , X j ) ≥
λ r (TW ) + kW − WR k∞
n(n − 1) i6= j
n−1
r>R
These lemmas are proven in Appendix A.3, Appendix A.4 and Appendix A.5. Collecting (20), (21), (22)
and (23), the triangular inequality gives the result.

A.3. Proof of Lemma 12
Pn
Observe that nER,n = i=1 (ZR (X i )ZR> (X i ) − IdR ) is a sum of independent centered symmetric matrices
where we denote by ZR (x) := (φ1 (x), . . . , φR (x)). In particular, ZR (X i )ZR> (X i ) are rank one matrices so
that it holds

kZR (X i )ZR> (X i ) − IdR k = 1 ∨ kZR (X i )k22 − 1
R
X

=1∨ (
φ r2 (X i ))2 − 1
r=1
R
X

≤1∨ k


φ r2 k∞ − 1 =: ρ(R) .

r=1

Moreover, one has

2
σR,n
: = nkE (ZR (X 1 )ZR> (X 1 ) − IdR )2 k

= nkE kZR (X 1 )k22 ZR (X 1 )ZR> (X 1 ) − 2ZR (X 1 )ZR> (X 1 ) − IdR k

= nkE kZR (X 1 )k22 ZR (X 1 )ZR> (X 1 ) − IdR k
≤n k

R
X


φ r2 k∞ E ZR (X 1 )ZR> (X 1 ) − IdR

r=1

=n k

R
X

φ r2 k∞ IdR − IdR

r=1

=n k

R
X
r=1

φ r2 k∞ − 1 ≤ nρ(R)

A.4

Proof of Lemma 13

25

PR
where we invoke that a.s. kZR (X 1 )k22 ZR (X 1 )ZR> (X 1 ) ´ (k r=1 φ r2 k∞ )ZR (X 1 )ZR> (X 1 ). It follows from the
matrix Bernstein inequality given in [34, Theorem 6.1.1]
∀t > 0,



P kER,n k ≥ t ≤ 2R exp −


t2
n
.
2ρ(R) 1 + t/(3n)

Indeed, we have used [34, Theorem 6.1.1] with
X k ← ZR (X i )ZR> (X i ) − IdR ,
R ← ρ(R),
2

σ ≤ n||E

X 12

Y ← nER,n ,

2
|| ← σR,n
,
t ← nt,

according to the notation of [34] on the left hand side and our notation on the right hand side. It proves
the lemma.

A.4. Proof of Lemma 13
Observe that
R
n
n
2
1 X 2
1 X X
W
(X
,
X
)
=
λ r (TW )φ r2 (X i )
i
i
R
2
2
n i=1
n i=1 r=1

=

n
X

1 X
φ r2 (X i )φs2 (X i )
λ
(T
)λ
(T
)
r
W
s
W
2
n r,s∈[R]
i=1

= x > Ax ≤ ||A||||x||22
Pn
p
p
with x = (λ1 (TW )/ n, . . . , λR (TW )/ n) and A = ((1/n) i=1 φ r2 (X i )φs2 (X i )) r,s . Note that A is an
irreducible and aperiodic matrix since its coefficients are positive. It follows by Perron-Frobenius theorem
that
R X
n
X
1
||A|| ≤ max (
φ 2 (X i )φs2 (X i ))
n 1≤r≤R s=1 i=1 r
Now, this last quantity can be upper bounded as follows
R
n
n
R
X
1 XX 2
1X 2
φ r (X i )φs2 (X i ) =
φ r (X i )(
φs2 (X i )),
n s=1 i=1
n i=1
s=1
n

≤(

1X 2
φ (X i ))(1 + ρ(R)).
n i=1 r

Using the bound
φ r2 (X 1 ) ≤ max ||φ r2 ||∞ =: aR ,
1≤r≤R

and Hoeffding inequality [6, page 34], we deduce that
¨
∀t > 0,

P

n

1X 2
φ r (X i ) > E φ r2 (X 1 ) + t
n i=1

«
≤ exp −

2nt 2 
.
aR2


Observe that E φ r2 (X 1 ) = 1. Let α ∈ (0, 1), choosing t 2 = aR2 log(R/α)/(2n) and taking an union bound,
it holds that
«
¨
1
n
aR log 2 (R/α)
1X 2
P ∀r ∈ [R],
φ (X i ) ≤ 1 +
≥1−α
p
n i=1 r
2n

26

A

It results in

PROOFS

«
1
(1 + ρ(R)) log 2 (R/α) 
P ||A|| ≤ 1 +
(1 + ρ(R)) ≥ 1 − α
p
2n
¨



On this event, we deduce that
n
1 X 2
W (X i , X i ) ≤ ||A||||x||22 ,
n2 i=1 R
1

aR log 2 (R/α)  (1 + ρ(R))||WR ||2
≤ 1+
,
p
n
2n

which gives the result.

A.5. Proof of Lemma 14
By a standard inequality of Hoeffding [18], for a bounded kernel h, for all α ∈ (0, 1),
(
)
v
t log(2/α)
X
1
P
h(X i , X j ) − E (h(X 1 , X 2 )) > khk∞
≤α
n(n − 1) i6= j
n−1
Applying this result for h = (W − WR )2 and noticing that
• E (h(X 1 , X 2 )) = kW − WR k22 =
• khk∞ = kW − WR k2∞ ,

P

2
r>R λ r (TW ),

the result follows.

A.6. Proof of Corollary 3

The symmetric kernel h := (W − WR )2 − E (W − WR )2 is σ-canonical, see [11, Definition 3.5.1] for
a definition. The following important improvement of Hoeffding’s inequalities for canonical kernels
was proved by [1], it holds that there exists two universal constants C1 > 0 and C2 > 0 such that for all
α ∈ (0, 1),
(
)
X
log(C2 /α)
1
P
h(X i , X j ) > C1 khk∞
≤ α.
n(n − 1) i6= j
n
We deduce that it holds, for all α ∈ (0, 1),
(
)
X
log(C
/α)
1
2
P
(W − WR )2 (X i , X j ) ≥ kW − WR k22 + C1 kW − WR k2∞
≤ α,
n(n − 1) i6= j
n
which proves the corollary substituting Lemma 14 by the aforementioned inequality.

A.7. Proof of Proposition 4
Define
∀t ∈ [−1, 1],

pR (t) :=

R
X
`=0

β

p?` c` G` (t) .

A.7

Proof of Proposition 4

27

We apply Corollary 3 to the kernel as follows.
∀x, y ∈ Sd−1 ,

WRe (x, y) :=

R
X
`=0

β

p?` c` G` (〈x, y〉) = pR (〈x, y〉) ,

First, note that
kW − WRe k2 = kp − pR k2 =

X
`>R

d` (p?` )2

 21

.

(24)

Next, invoke [10, Corollary 1.2.7] to get that
∀` ≥ 0,

d
X̀

Y`2j = d` .

j=1

e) of Theorem 2 simplifies to ρ(R
e) ≤ R
e. Furthermore, it holds
It follows that the quantity ρ(R
∀x ∈ Sd−1 ,

WRe (x, x) =

R
X
`=0

β

p?` c` G` (1) =

R
X
`=0

d` p?` ,

(25)

since G`λ (1) = d` /c` . Then by Hoffman-Wielandt inequality, we have
e Re,n )) ≤ k T
e Re,n − T Re,n k F =
δ2 (λ(T Re,n ), λ( T

R
n
1 X
 12
1 X
2
d` p?` ,
=
W
(X
,
X
)
p
i
i
n2 i=1 Re
n `=0

almost surely. And we use this bound instead of the one of Lemma 13. The following result follows:
δ2 (λ(TWRe ), λ(T n )) ≤

R
X
`=0

d` (p?` )2

 21  R
e log(2R
e/α)  21
n

R
 C log(C /α)  12
1 X
1
2
+p
d` p?` + kp − pR k2 + kp − pR k∞
n
n `=0

(26)

with probability at least 1 − 3α.
Let us study the various terms appearing in (26). First, by orthonormality
R
X
`=0

d` |p?` |2 = kpR k22 ≤ kpk22 ≤ 2

since pR is the orthogonal projection of p, and |p| ≤ 1. Next, using Cauchy-Schwarz inequality
R
X
`=0

d` p?`


≤

R
X

d`

`=0

Now kp−pR k∞ ≤ 1+kpR k∞ , with kpR k∞ ≤
and Theorems 7.32.1 and 7.33.1 of [31] so
kpR k∞ ≤

1/2 

R
X
`=0

R
X
`=0

d` |p?` |2

1/2
≤

Æ

e.
2R

β
β
?
`=0 |p` c` |kG` k∞ . But kG` k∞

PR

|p?` c` |G`λ (1) =

R
X
`=0

|p?` |d` ≤

Æ

β

= G` (1) by Formula (4.7.1)

e.
2R

Finally, (26) becomes
p
e log(2R
e/α)  12
e
p R
2R
δ2 (λ(TWRe ), λ(T n )) ≤ 2
+ p
n
n
Æ  C log(C /α)  1
X
 21 
2
1
2
e
+
d` (p?` )2 + 1 + 2R
n
`>R

28

A

PROOFS

e ≥ 1 and log n ≤ n, there exists a numerical constant C > 0 such that, with probability at
Hence, since R
least 1 − 3α
v
te
X
 12
e/α))
R(1 + log(R
δ2 (λ(TWRe ), λ(T n )) ≤
d` (p?` )2 + C
.
(27)
n
`>R
Adding (24) gives the first statement of Proposition 4.
Now let us denote by Ω the set with probability larger than 1 − 3α such that the previous inequality is
true. One has
δ2 (λ(T n ), λ? ) = δ2 (λ(T n ), λ? )1Ω + δ2 (λ(T n ), λ? )1Ωc .
Observe that each |λk (T n )| is bounded by ρ(T n ) the spectral radius of T n . Since T n := (1/n)Θ0 , it holds
b n ) ≤ kΘ0 /nk F ≤ 1. Then
that ρ( T
δ2 (λ(T n ), λ? ) ≤ δ2 (λ(T n ), 0) + δ2 (0, λ? ) ≤
which entails δ22 (λ(T n ), λ? ) ≤ (1 +

p

n + kpk2

(28)

p 2
2) n. Hence, using this bound and previous inequality,


p
E δ22 (λ(T n ), λ? ) = E δ22 (λ(T n ), λ? )1Ω + (1 + 2)2 n P(Ωc )
X

e(1 + log(R
e/α))
p
R
≤8
d` (p?` )2 + 2C 2
+ 3α(1 + 2)2 n
n
`>R
e log(2R
e/α). We choose α = n−2 , and assume n ≥ 2R
e. Then
as soon as n3 ≥ R
e log(2R
e/α) = R
e log(2R
e n2 ) ≤
R

n
log(n3 ) ≤ n3 ,
2

and
X

e(1 + log(R
e n2 ))

p
R
E δ22 (λ(T n ), λ? ) ≤ 8
+ 3(1 + 2)2 n−1
d` (p?` )2 + 2C 2
n
`>R
≤8


Rd−1 log n
d` (p?` )2 + C 0
n
`>R

X

e = O (Rd−1 ). Now we assume that p belongs to the Weighted Sobolev Z s ((−1, 1)). Then,
since R
wβ
e, it holds
using (12), for all R such that n ≥ 2R

Rd−1 log n
E δ22 (λ(T n ), λ? ) ≤ 8C(p, s, d)R−2s + C 0
n
1

To conclude it is sufficient to choose R = b(n/log n) 2s+d−1 c.

A.8. Proof of Theorem 6

We use the notation of the previous proofs and, in particular, the notation of Appendix A.7. The heart of
the proof lies in the following proposition, proved in Appendix A.9.

A.9

Proof of Proposition 15

29

b R , λ?R ) ≤ 4δ2 (λ(TW ), λ(T n ))+
e ≤ n. It holds δ2 (λ
Proposition 15. Let R ≥ 0 such that 2R
e
R

p

ek T
b n − T n k.
2R

Now, using inequality (4), we know that with probability at least 1 − α it holds
p
log(n/α)
3
b
k T n − T n k ≤ p + C0
.
n
2n
e log(2R
e/α),
Moreover, by (27) in proof of Proposition 4, for all n3 ≥ R
v
te
 12
X
e/α))
R(1 + log(R
δ2 (λ(TWRe ), λ(T n )) ≤
d` (p?` )2 + C
.
n
`>R
Thus there exists a numerical constant κ0 > 0 such that, with probability at least 1 − 3α

b R , λ?R ) ≤ 4
δ2 (λ

X
`>R

d` (p?` )2

 12

v
te
e/α))
R(1 + log(R
.
+ κ0
n

e)3 ∨ R
e log(2R
e/α), that gives the first statement of Theorem 6.
if n ≥ (2R
3

Now let us denote by Ω the set with probability larger than 1 − 3α such that the previous inequality is
true. One has
b R , λ?R ) = δ2 (λ
b R , λ?R )1Ω + δ2 (λ
b R , λ?R )1Ωc
δ2 (λ
As for (28), we can prove the coarse bound
b R , λ?R ) ≤
δ2 (λ

Æ

e + kpk2 ≤ (1 +
R

p Æ
e.
2) R

Hence, using this bound and previous inequality,


p
b R , λ?R ) = E δ2 (λ
b R , λ?R )1Ω + (1 + 2)2 R
e P(Ωc )
E δ22 (λ
2



X
e 1 + log(R
e/α)
p
R
? 2
2
e,
+ 3α(1 + 2)2 R
≤ 32
d` (p` ) + 2κ0
n
`>R
e)3 ∨ R
e log(2R
e/α). We choose α = n−1 , and assume n ≥ 2R
e. Then R
e log(2R
e/α) ≤ n3
as soon as n3 ≥ (2R
and



X
e 1 + log(R
e n)
e

p
R
R
b R , λ?R ) ≤ 32
E δ22 (λ
d` (p?` )2 + 2κ20
+ 3(1 + 2)2
n
n
`>R


X
e log n
R
≤ 32
d` (p?` )2 + (6κ20 + 18)
.
n
`>R
This completes the proof.

A.9. Proof of Proposition 15
◦

Define ∆R as follows
e
2R

∀x, y ∈ R ,

∆2R (x,

e
2R
¦X
©
y) := min
(x k − yσ(k) )2 ,

e].
where S2Re denotes the set of permutations on [2R

σ∈S2Re

k=1

30

A

PROOFS

Once again, using Hardy-Littlewood rearrangement inequality [16, Theorem 368], it holds that
∀x, y ∈ R2R s.t. x 1 ≥ . . . ≥ x 2Re and y1 ≥ . . . ≥ y2Re ,
e

∆2R (x, y) :=

e
2R
X
(x k − yk )2 .
k=1

e zeros, we denote also
Completing with R
e
b R := ( p
b0 , p
b ,...,p
b ,...,p
b ,...,p
b , 0, . . . , 0) ∈ R2R ,
Λ
| R {z }R | {z }
|{z}
| 1 {z }1
d0

and Λ

?R

:=

dR

d1

e
R

(p?0 , p?1 , . . . , p?1 , . . . , p?R , . . . , p?R , 0, . . . , 0)

∈ R 2R .
e

b R , λ?R ) = ∆R (Λ
b R , Λ?R )
b` := p
bR` . Observe that δ2 (λ
Since R does not vary in this proof, we have denoted p
using the property described in (7) and Hardy-Littlewood rearrangement inequality [16, Theorem 368]
again.
◦ Recall that it holds λ(TWRe ) = {0, p?0 , p?1 , . . . , p?1 , . . . , p?R , . . . , p?R } where zero is the only eigenvalue with
infinite multiplicity. In particular, remark that the vector (p?0 , p?1 , . . . , p?1 , . . . , p?R , . . . , p?R ) belongs to MR .
We begin by defining
(p0 , . . . , pR , . . . , pR ) ∈ arg min min

u∈MR σ∈Sn

e
R
n
X
©
¦X
(uk − λσ(k) (T n ))2 +
λσ(k) (T n )2 ,

(29)

e+1
k=R

k=1

where Sn denotes the set of permutation on [n]. Also, define
∀x, y ∈ Sd−1 ,

W Re (x, y) =

R
X
`=0

β

p` c` G` (〈x, y〉) ,

and observe that λ(TW e ) = {0, p0 , p1 , . . . , p1 , . . . , pR , . . . , pR } where zero is the only eigenvalue with
R
infinite multiplicity. Denote σ ∈ Sn the permutation that achieves the minimum in (29). We have the
following intermediate result.
Lemma 16. It holds
δ22 (λ(TW e ), λ(T n )) =
R

e
R
n
X
X
(pk − λσ(k) (T n ))2 +
λσ(k) (T n )2 ≤ δ22 (λ(TWRe ), λ(T n )) ,
e+1
k=R

k=1

where (p` )` is defined by (29).
e nonzero eigenvalues. Using again Hardy-Littlewood reProof. Observe that λ(TW e ) has at most R
R
arrangement inequality [16, Theorem 368] and (7), one may deduce that δ22 (λ(TW e ), λ(T n )) reads
R
PRe
Pn
2
2
(p
−
λ
(T
))
+
λ
(T
)
for
some
permutation
σ
∈
S
.
Taking
the
infimum
leads to
e+1 σ(k)
σ(k)
n
n
n
k=1 k
k=R
the left hand side equality.
e nonzero eigenvalues. Using again Hardy-Littlewood rearThen, observe that λ(TWRe ) has at most R
rangement inequality [16, Theorem 368] and (7), one may deduce again that δ22 (λ(TW e ), λ(T n )) reads
R
PRe
Pn
?
2
2
(p
−
λ
(T
))
+
λ
(T
)
for
some
permutation
σ
∈
S
.
Furthermore,
recall that
e+1 σ(k)
σ(k)
n
n
n
k=1
k=R
k
(p?0 , p?1 , . . . , p?1 , . . . , p?R , . . . , p?R ) belongs to MR and, hence, it is admissible to Program (29). In particular,
the value of the objective at this point is always greater than the minimal value. This gives the right
hand side inequality.
◦

b ) a point that achieves the minimum in (14). Now, consider
Similarly, denote ((b
p` ), σ
e]) ∪ σ
e]) ,
b ([R
S := σ([R

e ≤ n.
and S c := [n] \ S, and define s := #S ≤ 2R

A.9

Proof of Proposition 15

31

On can check that
è
1 X
b` =
p
λσb (k)
d`

and

Þ
k=`−1

è
1 X
p` =
λσ(k)
d`
Þ
k=`−1

Ý = 1.
with the convention −1
◦ Denote by SS,n the set of permutation σ ∈ Sn such that σ([s]) = S, SS the set of bijections from [s]
onto S and Ss the set of permutations of [s]. It is clear that SS ' Ss . Observe that
(b
p` ) = arg min min

u∈MR σ∈Sn

e
R
n
X
¦X
©
(uk − λσ(k) )2 +
λ2σ(k)
e+1
k=R

k=1
e
R
¦X

= arg min min

u∈MR σ∈SS,n

n
X

(uk − λσ(k) )2 +

λ2σ(k)

©

e+1
k=R

k=1

since one of the permutation σ ∈ Sn that achieves the minimum in the first row satisfies σ ∈ SS,n and it
e,
follows that (b
p` ) is the arg minimum of the second program. Now, separating the terms λ2σ(k) for k > R
we obtain
(b
p` ) = arg min min

u∈MR σ∈SS,n

u∈MR σ∈SS

s
X

(uk − λσ(k) )2 +

λ2σ(k) +

s
X

(uk − λσ(k) )2 +

X

λ2t

©

t∈S c

e+1
k=R

k=1
e
R
¦X

u∈MR σ∈SS

t∈S c

e+1
k=R

k=1

e
R
¦X

= arg min min

= arg min min

e
R
s
X
X ©
¦X
(uk − λσ(k) )2 +
λ2σ(k) +
λ2t

©
λ2σ(k) .

e+1
k=R

k=1

Similarly, one can check that
(p` ) = arg min min

u∈MR σ∈SS

◦

e
R
s
X
¦X
©
(uk − λσ(k) (T n ))2 +
λσ(k) (T n )2 .
e+1
k=R

k=1

˙ R of ∆R to Rs defined as follows
Consider the restriction ∆
˙ 2 (x, y) := min
∆
R

∀x, y ∈ Rs ,

σ∈Ss

s
¦X
©
(x k − yσ(k) )2 .
k=1

Using (5) and Weyl’s inequality [4, page 63] and by abuse of notation, note that
X
 21 p
˙ R ((λk (T n ))k∈S , (λk )k∈S ) ≤
b n − T nk .
∆
(λk − λk (T n ))2 ≤ sk T
k∈S

Moreover, using (30) and by abuse of notation, remark that
˙ 2 ((b
∆
R p` ), (λk )k∈S ) = min

σ∈SS

≤ min

σ∈SS

=

¦

min

u∈MR

e
R
s
X
X
©
(uk − λσ(k) )2 +
λ2σ(k) .
e+1
k=R

k=1

e
R
¦X

(pk − λσ(k) )2 +

k=1

s
X

©
λ2σ(k) .

e+1
k=R

˙ 2 ((p` ), (λk )k∈S )
∆
R

e zeros.
b1 , . . . , p
b1 , . . . , p
bR , . . . , p
bR , 0, . . . , 0) ∈ Rs completing with s − R
where (b
p` ) = (b
p0 , p

(30)

32
◦

A

PROOFS

Using (29), Lemma 16 and by abuse of notation, observe that
˙ 2 ((p` ), (λk (T n ))k∈S ) = min
∆
R

σ∈SS

≤ min

σ∈SS

= min

σ∈Sn

=
=

e
R
s
X
©
¦X
(pk − λσ(k) (T n ))2 +
λσ(k) (T n )2 .
e+1
k=R

k=1
e
R
¦X

s
X

(pk − λσ(k) (T n ))2 +

λσ(k) (T n )2 +

e
R
¦X

n
X

(pk − λσ(k) (T n ))2 +

©
λ t (T n )2 .

t∈S c

e+1
k=R

k=1

X

©
λσ(k) (T n )2 ,

e+1
k=R

k=1

e
R
X

n
X

k=1

e+1
k=R

(pk − λσ(k) (T n ))2 +

λσ(k) (T n )2

δ22 (λ(TW e ), λ(T n ))
R

≤ δ22 (λ(TWRe ), λ(T n ))
e zeros.
where we denote by (p` ) = (p0 , p1 , . . . , p1 , . . . , pR , . . . , pR , 0, . . . , 0) ∈ Rs completing with s − R
◦

˙ R is a semi-distance—in particular the triangular inequality holds, one deduces
Using that ∆
˙ R ((b
˙ R ((b
˙ R ((λk )k∈S , (λk (T n ))k∈S ) + ∆
˙ R ((λk (T n ))k∈S , (p` ))
∆
p` ), (p` )) ≤ ∆
p` ), (λk )k∈S ) + ∆
p
b n − T nk ,
≤ 2δ2 (λ(TW ), λ(T n )) + sk T
e
R

combining the aforementioned inequalities.
R

e zeros, and remark that
Define Λ := (p0 , p1 , . . . , p1 , . . . , pR , . . . , pR , 0, . . . , 0) ∈ R2R completing with R
Æ
˙ R ((b
ek T
b n − T nk .
b R , ΛR ) ≤ ∆
∆R (Λ
p` ), (p` )) ≤ 2δ2 (λ(TWRe ), λ(T n )) + 2R
e

R

R

◦ It remains to bound ∆R (Λ?R , Λ ). Note that ∆R (Λ?R , Λ ) = δ2 (λ(TWRe ), λ(TW e )). Then, invoke
R
Lemma 16 to get that
R

∆R (Λ?R , Λ ) ≤ δ2 (λ(TWRe ), λ(T n )) + δ2 (λ(T n ), λ(TW e )) ≤ 2δ2 (λ(TWRe ), λ(T n )) .
R

Finally we obtain the following bound:
b R , λ?R ) ≤ 4δ2 (λ(TW ), λ(T n )) +
δ2 (λ
e
R

Æ

ek T
b n − T nk
2R

(31)

e.
for all sample size n ≥ 2R

A.10. Proof of Theorem 7
In this proof we denote D(R) =
R ∈ R. First decompose

Æ


b R0 , λ
b R0 ∧R ) − κD(R0 ) . Fix some
e log n/n, so that B(R) = maxR0 ∈R δ2 (λ
R

b R , λ? ) ≤ δ2 (λ
bR, λ
b R∧R ) + δ2 (λ
b R∧R , λ
b R ) + δ2 (λ
b R , λ? ).
δ2 (λ
b

b

b

b

b) it holds that
Using the definition of B(R) and B(R
b R , λ? ) ≤ B(R) + κD(R
b R , λ? ).
b) + B(R
b) + κD(R) + δ2 (λ
δ2 (λ
b

A.10

Proof of Theorem 7

33

b Rb , λ? ) ≤ 2B(R) + 2κD(R) + δ2 (λ
b R , λ? ). The last term can be
b to write δ2 (λ
We now use the definition of R
R
?
R
?R
?R
?
b
b
split in δ2 (λ , λ ) ≤ δ2 (λ , λ ) + δ2 (λ , λ ). Thus,
b Rb , λ? ) ≤ 2B(R) + 2κD(R) + δ2 (λ
b R , λ?R ) + δ2 (λ?R , λ? ).
δ2 (λ

(32)

We shall now control the term B(R). Denote a+ = max(a, 0) the positive part of any real a. Let us write
0

0

bR , λ
b R ∧R ) − κD(R0 )}
B(R) = max
{δ2 (λ
0
R ∈R

b R0 , λ
b R ) − κD(R0 )}+
max {δ2 (λ

≤

R0 ∈R,R0 ≥R

b R , λ?R ) + δ2 (λ?R , λ?R ) + δ2 (λ?R , λ
b R ) − κD(R0 )}+
max {δ2 (λ
0

≤

Now

0
δ22 (λ?R , λ?R )

e0
R
X

=

0

0

R0 ∈R,R0 ≥R

|λ?k |2 ≤ δ22 (λ?R , λ? ). Then

e+1
k=R

B(R) ≤

b R0 , λ?R0 ) − κD(R0 )}+ + δ2 (λ?R , λ? ) + δ2 (λ?R , λ
bR) .
max {δ2 (λ

R0 ∈R,R0 ≥R

Finally, combining this with (32),
b R , λ? ) ≤ 2
δ2 (λ

b R , λ?R ) − κD(R0 )}+ + 2κD(R) + 3δ2 (λ
b R , λ?R ) + 3δ2 (λ?R , λ? ) ,
max {δ2 (λ
0

b

≤5

0

R0 ∈R,R0 ≥R

b R0 , λ?R0 ) − κD(R0 )}+ + 3δ2 (λ?R , λ? ) + 5κD(R) .
max {δ2 (λ

R0 ∈R,R0 ≥R

e max )3 ∨ R
e max log(2R
e max /α) then,
Now, we invoke Theorem 6 and a union bound to insure that, if n3 ≥ (2R
with probability greater that 1 − 3|R|α, it holds
v 
 
u e0
tR
0
0
0
Re0
0
R
?R
?R
?
b
∀R ∈ R ,
δ2 (λ , λ ) ≤ 4δ2 (λ , λ ) + κ0
1 + log
n
α
e max log(2R
e max /α) = R
e max log(2R
e max nq+1 ) ≤ n log(nq+2 )/2 < 0.1(q + 2)n3
We choose α = n−1−q , then R

−2
e
since x log x ≤ 0.09 and also note that 1 + log R/α ≤ (q + 3) log n. If q + 2 ≤ 10 then it holds that
e max log(2R
e max /α) and with probability 1 − 3n−q
n3 > R
p
b R0 , λ?R0 ) ≤ 4δ2 (λ?R0 , λ? ) + κ0 q + 3D(R0 )
∀R0 ∈ R ,
δ2 (λ
p
Then, with probability 1 − 3n−q , provided that κ ≥ κ0 q + 3
b Rb , λ? ) ≤ 5
δ2 (λ

max {4δ2 (λ?R , λ? )}+ + 3δ2 (λ?R , λ? ) + 5κD(R)
0

R0 ∈R,R0 ≥R

≤ 23δ2 (λ?R , λ? ) + 5κD(R)
Since it holds for any R, the first inequality of Theorem 7 is proved by choosing q = 8.
The second statement will follow by the same roadmap as in the end of proof A.8. Let us denote by Ω
the set with probability larger than 1 − 3n−q such that the previous
inequality is true, and let us find a
p p
2 bR
?
R
?R
b
e for all R, see (28). Furthermore
coarse bound on δ (λ , λ ). Remind that δ2 (λ , λ ) ≤ (1 + 2) R
2

δ2 (λ?R , λ? ) =

X
`>R

d` (p?` )2

 12

≤ kpk2 ≤

p
2.

Hence, using this bound and previous inequality, for all R ∈ R,




p
b Rb , λ? ) ≤ E δ2 (λ
b Rb , λ? )1Ω + (1 + 2 2)2 R
e max P(Ωc )
E δ2 (λ
2

provided that κ ≥ κ0

2

p
e max 3n−q
≤ 2(23)2 δ22 (λ?R , λ? ) + 2(5)2 κ2 D2 (R) + (1 + 2 2)2 R

≤ 2(23)2 δ22 (λ?R , λ? ) + κ2 D2 (R) + n1−q

p

q + 3. The conclusion follows, choosing for instance q = 2.

34

A

PROOFS

A.11. Proof of Proposition 9
P
P
Note that δ22 (λ?R , λ? ) = k>Re |λ?k |2 = `>R d` |p?` |2 and this quantity vanishes when R ≥ D. From
e)3 ∨ R
e log(2R
e/α), we derive that, for R ≥ D, it holds
Theorem 6 and assuming that n3 ≥ (2R
Ç

b R , λ?R ) ≤ κ0 R
e/α /n
e 1 + log R
δ2 (λ
PR
β
with probability at least 1−3α. Remark also that pR = p as soon as R ≥ D, where pR (t) := `=0 p?` c` G` (t).
We now work on the set with probability 1 − 3α given by Theorem 6.
We denote
δ :=

min

0≤i6= j≤D; p?i 6=0

|p?i − p?j | ∧ |p?i | > 0 ,

b R , λ?R ) < δ/2. Then there exists a permutation σ? ∈ Sn
and note that, for n large enough, it holds δ2 (λ
b R ? − λ?R | < δ/2. Now, observe that
such that for all k ∈ [n], |λ
k
σ (k)
bR = ( p
bR , . . . , p
bR , 0, . . . ),
bR0 , p
bR , . . . , p
bR , . . . , p
bR , . . . , p
bR , . . . , p
λ
| D {z D}
| R {z }R
|{z}
| 1 {z }1
d0

λ

?R

p?0

=(
|{z} |
d0

dD

d1

dR

, p?1 , . . . , p?1 , . . . , p?D , . . . , p?D , 0, . . . ).
{z
d1

}

|

{z
dD

}

b R , λ?R ) < δ/2 then for all h, i, j, k, ` such that p? 6= 0 it holds
We deduce that if δ2 (λ
h
If |b
pRk − p?h | ∨ |b
pR` − p?h | ≤ δ/2 (resp. |b
pRk − p?i | ∨ |b
pRk − p?j | ≤ δ/2)
bRk = p
bR` (resp. p?i = p?j ) .
then p

(33)

bR` cannot be at the same time at a distance less than δ/2 to some p?i 6= 0 and at a distance
Indeed, one p
less that δ/2 to some p?j since these latter are both at a distance of δ. Necessarily the permutation σ? is
bRi
such that the group of eigenvalues p?i 6= 0 of multiplicity di matches with the group of eigenvalues p
with the same multiplicity—recall that the multiplicities d` are pairwise different since the sequence d`
is increasing. Thanks to (33) it holds
X
X
b R , λ?R ) =
δ22 (λ
dh (b
pRh − p?h )2 +
d` (b
pR` )2 = ||b
pR − p||22 ,
h; p?h 6=0

`; p?` =0

PR

d` (b
pR` − p?` )2 . It follows that if
Ç

e)3 ∨ R
e log(2R
e/α) and 2κ0 R
e 1 + log R
e/α /n <
n3 ≥ (2R

noticing that kb
pR − pR k22 =

`=0

min

0≤i6= j≤D; p?i 6=0

|p?i − p?j | ∧ |p?i |

q

e/α /n with probability at least 1 − 3α. Again, we choose α = n−1−q ,
e 1 + log R
then ||b
pR − p||2 ≤ κ0 R
e log(2R
e/α) = R
e log(2R
e nq+1 ) ≤ n log(nq+2 )/2 < 0.1(q + 2)n3 since x −2 log x ≤ 0.09 and also note
then R
e
e log(2R
e/α). Now, if
that 1 + log(R/α) ≤ (q + 3) log n. With q = 8, it holds that n3 > R
q
e and 2κ0 11R
e log(n)/n <
n ≥ 2R
min ? |p?i − p?j | ∧ |p?i |
0≤i6= j≤D; pi 6=0

then ||b
pR − p||2 ≤ κ0

Æ

e log(n)/n with probability 1 − 3n−8 , as claimed.
11R

For the second statement, let us denote by Ω the set with probability larger than 1 − 3n−q such that
the previous inequality is true, and let us find a coarse bound on ||b
pR − p||22 , for instance ||b
pR − p||2 ≤
p p
e. Hence, using this bound and previous inequality, it holds
(1 + 2) R
e log n


p
p
κ2 (q + 3) R
e P(Ωc ) ≤ 0
e n−q
E ||b
pR − p||22 ≤ E ||b
pR − p||22 1Ω + (1 + 2)2 R
+ 3(1 + 2)2 R
n
e/α) ≤ (q + 3) log n. The conclusion follows, choosing q = 1.
recalling that 1 + log(R

A.12

Proof of Corollary 10

35

A.12. Proof of Corollary 10
From Theorem 7, with probability 1 − 3n−8
!
!!
v
v
te
te
R
log
n
R
log
n
b Rb , λ? ) ≤ C min min δ2 (λ?R , λ? ) + κ
δ2 (λ
, min κ
R<D
R≥D
n
n
! v
!
v
te
te
R log n
D log n
≤ C min min δ2 (λ?R , λ? ) + κ
,κ
R<D
n
n
Then, with probability 1 − 3n−8 ,
v
te
D log n
δ2 (λ , λ? ) ≤ Cκ
−→ 0.
n→∞
n
Thus, reasonning as in proof A.11, it holds
X
b
b
b Rb , λ? ) = ||b
δ22 (λ
pR − p||22 =
d` (b
pR` − p? )2 ,
b Rb

`

b
?R

b Rb , λ? ) cannot tend to 0. Thus
b < D, then δ2 (λ , λ? ) ≥ d D |p? |2 > 0 and then δ2 (λ
If (by contradiction) R
D
b R̂ , λ? ) = ||b
b ≥ D.Moreover, since δ2 (λ
necessarily R
pR̂ − p||2 , with probability 1 − 3n−8
2

2

||b
pR̂ − p||22 ≤ C 2 κ2

e log n
D
.
n

Finally we can write




p
b
b
e max P(Ωc )
E ||b
pR − p||22 ≤ E ||b
pR − p||22 1Ω + (1 + 2)2 R
≤ C 2 κ2

e log n
e log n
p
D
D
e max n−8 ≤ (C 2 κ2 + 9)
+ 3(1 + 2)2 R
.
n
n

A.13. Proof of Theorem 11
The proof follows the same guidelines as in the sphere example. The only difference is that we do
not have Gegenbauer polynomials but normalized Jacobi polynomials Z` now. In particular, we have
previously used the fact that Gegenbauer polynomials are bounded. Here, the same result holds in virtue
of (18).
To be specific, when S is a compact symmetric space, note that

•

R
X
r=1

φ r2

=

R−1 Æ
X

r

dr zon (eS ) =

r=0

• we define p (t) :=

à
e when invoking Lemma 12
dr = R
− 1 and we get that ρ(R) ≤ R

r=0

or Theorem 2;
R

R−1
X

R Æ
X
`=0

d` p?` Z` (t) and we get that
WRe (x, y) = pR (cos(γ(x, y)))
WRe (x, x) =

R Æ
X
`=0

d` p?` Z` (1)

=

R
X
`=0

d` p?` ,

by (18). This identity can be used in place of (25).
Using these inequalities and following the same guidelines as in the sphere example, one can prove the
result.

36

B

COMPUTATIONAL CONSIDERATIONS

Appendix B: Computational Considerations

B.1. Proof of Theorem 5

Without loss of generality, assume that λ1 ≥ λ2 ≥ . . . ≥ λn . Similarly, let u ∈ MR and remember that we
can group the coordinates of u in groups of sizes d` for ` = 0, . . . , R. Reordering by decreasing order,
there exists τ ∈ SR+1 such that
= . . . = uτ(q)
uτ(1)−1+1
= . . . = uτ(1)
ß ≥ . . . ≥ uτ(q)−1+1
ß ≥0>
ä
å
{z
}
|
|
{z
}
dτ(1)

dτ(q)

uτ(q+1)−1+1
= . . . = uτ(q+1)
= . . . = uτ(R+1)
ä ≥ . . . ≥ uτ(R)−1+1
å
å
å,
{z
}
|
|
{z
}
dτ(R+1)

dτ(q+1)

for some q ∈ N. We may consider that q = 0 and respectively q = R + 1 in degenerate cases when all the
e
e
coefficients are negative and respectively non negative. Remember that u ∈ RR and set uk = 0 for k > R
n
such that, completing with zeros, consider that u ∈ R . One has
uτ(1)−1+1
= . . . = uτ(1)
= . . . = uτ(q)
e+1 = . . . = un = 0 >
ß ≥ . . . ≥ uτ(q)−1+1
ß ≥ uR
ä
å
{z
}
|
{z
}
|
{z
} |
dτ(1)

e
n−R

dτ(q)

uτ(q+1)−1+1
= . . . = uτ(q+1)
= . . . = uτ(R+1)
ä ≥ . . . ≥ uτ(R+1)−1+1
å
å
å .
{z
}
|
{z
}
|
dτ(R+1)

dτ(q+1)

Note that
e
R
n
n
X
¦X
©
¦X
©
2
min
(uk − λσ(k) )2 +
λ2σ(k) = δ22 ((λk )nk=1 , (uk )nk=1 ) = min
(u
,
0 (k) − λ k )
σ
0

σ∈Sn

σ ∈S n

e+1
k=R

k=1

(34)

k=1

taking σ0 = σ−1 . Using Hardy-Littlewood rearrangement inequality [16, Theorem 368], it is standard to
observe that
2
(34) = (uτ(1)−1+1
− λ1 )2 + · · · + (uτ(1)
ß − λdτ(1) ) + · · ·
å
|
{z
}
dτ(1)

2
+ (uτ(q)−1+1
− λdτ(1) +···+dτ(q−1) +1 )2 + · · · + (uτ(q)
ß − λdτ(1) +···+dτ(q) )
ä
{z
}
|
dτ(q)

+ λ2d +···+d +1
τ(1)
τ(q)
|

+ · · · + λ2d +···+d +n−Re
τ(1)
τ(q)
{z

}

e
n−R

2
+ (uτ(q+1)−1+1
− λdτ(1) +···+dτ(q) +n−Re+1 )2 + · · · + (uτ(q+1)
e)
ä − λdτ(1) +···+dτ(q+1) +n−R
å
|
{z
}
dτ(q+1)

+ ···
2
+ (uτ(R+1)−1+1
− λdτ(1) +···+dτ(R) +n−Re )2 + · · · + (uτ(R+1)
å
å − λn ) .
|
{z
}
dτ(R+1)

B.1

Proof of Theorem 5

37

Hence a permutation σ0 achieving the minimum in (34) is given by



k




1


..


.



dτ(1)



..

.



 d
τ(1) + · · · + dτ(q−1) + 1



..

.



σ−1 = σ0 = 
dτ(1) + · · · + dτ(q)



 dτ(1) + · · · + dτ(q) + 1


..

.




e
 dτ(1) + · · · + dτ(q) + n − R


..

.



 d
e
 τ(1) + · · · + dτ(R) + n − R

..


.


n

σ (k)
0




å
τ(1)
−1+1 


..


.



ß
τ(1)



..

.



å
τ(q) − 1 + 1 



..

.



ß

τ(q)



e+1

R


..

.




n



..

.



å
τ(R + 1) − 1 + 1 


..


.


å
τ(R
+ 1)

Remark that this permutation can be explicitly written given τ ∈ SR+1 and q ∈ [0, R]. It follows that
the set of permutations σ0 achieving the minimum in the right hand side of (34) is in one to one
correspondence with a subset of SR+2 . Since σ = σ0−1 in (34) the same result holds true for the
permutation σ achieving the minimum of the left hand side of (34), proving the result. We define HR
has the set of permutation σ achieving the minimum of the left hand side of (34). The proof given here
is constructive and it gives an explicit expression of HR .

38

REFERENCES

References

[1] M. A. Arcones and E. Giné. Limit theorems for U-processes. The Annals of Probability, pages
1494–1542, 1993.
[2] A. S. Bandeira, R. van Handel, et al. Sharp nonasymptotic bounds on the norm of random matrices
with independent entries. The Annals of Probability, 44(4):2479–2506, 2016.
[3] J.-P. Baudry, C. Maugis, and B. Michel. Slope heuristics: overview and implementation. Statistics
and Computing, 22(2):455–470, Mar 2012.
[4] R. Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[5] B. Bollobás. Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge
University Press, Cambridge, second edition, 2001.
[6] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of
independence. OUP Oxford, 2013.
[7] M. L. Braun. Accurate error bounds for the eigenvalues of the kernel matrix. Journal of Machine
Learning Research, 7(Nov):2303–2328, 2006.
[8] S. Bubeck, J. Ding, R. Eldan, and M. Z. Rácz. Testing for high-dimensional geometry in random
graphs. Random Structures & Algorithms, 2016.
[9] D. Bump. Lie groups, volume 225. Springer Science & Business Media, 2013.
[10] F. Dai and Y. Xu. Approximation theory and harmonic analysis on spheres and balls. Springer, 2013.
[11] V. De la Pena and E. Giné. Decoupling: from dependence to independence. Springer Science &
Business Media, 2012.
[12] L. Devroye, A. György, G. Lugosi, F. Udina, et al. High-dimensional random geometric graphs and
their clique number. Electronic Journal of Probability, 16:2481–2508, 2011.
[13] P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int.
Közl., 5:17–61, 1960.
[14] J. Ferreira, V. A. Menegatto, and A. Peron. Integral operators on the sphere generated by positive
definite smooth kernels. Journal of complexity, 24(5):632–647, 2008.
[15] A. V. Goldenshluger and O. V. Lepski. General selection rule from a family of linear estimators.
Theory Probab. Appl., 57(2):209–226, 2013.
[16] G. H. Hardy, J. E. Littlewood, and G. Pólya. Inequalities. Cambridge university press, 1952.
[17] R. Hasminskii and I. Ibragimov. On density estimation in the view of Kolmogorov’s ideas in
approximation theory. Ann. Statist., 18(3):999–1010, 09 1990.
[18] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American statistical association, 58(301):13–30, 1963.
[19] O. Klopp, A. B. Tsybakov, N. Verzelen, et al. Oracle inequalities for network models and sparse
graphon estimation. The Annals of Statistics, 45(1):316–354, 2017.
[20] E. D. Kolaczyk. Statistical analysis of network data. Springer Series in Statistics. Springer, New
York, 2009. Methods and models.
[21] V. Koltchinskii and E. Giné. Random matrix approximation of spectra of integral operators. Bernoulli,
pages 113–167, 2000.
[22] L. Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
[23] C. Matias and S. Robin. Modeling heterogeneity in random graphs through latent space models: a
selective review. ESAIM: Proceedings and Surveys, 47:55–74, 2014.
[24] P.-L. Méliot. The cut-off phenomenon for brownian motions on compact symmetric spaces. Potential
Analysis, 40(4):427–509, 2014.
[25] P.-L. Méliot. Techniques d’analyse harmonique et résultats asymptotiques en théorie des probabilités.
Habilitation à Diriger des Recherches, 2017.
[26] M. E. J. Newman. The structure and function of complex networks. SIAM Rev., 45(2):167–256,
2003.
[27] S. Nicaise. Jacobi polynomials, weighted sobolev spaces and approximation results of some
singularities. Mathematische Nachrichten, pages 117–140, 2000.
[28] M. Penrose. Random geometric graphs, volume 5 of Oxford Studies in Probability. Oxford University
Press, Oxford, 2003.

REFERENCES

39

[29] L. Rosasco, M. Belkin, and E. D. Vito. On learning with integral operators. Journal of Machine
Learning Research, 11(Feb):905–934, 2010.
[30] S. R. Sundaresan, I. R. Fischhoff, J. Dushoff, and D. I. Rubenstein. Network metrics reveal
differences in social organization between two fission–fusion species, Grevy’s zebra and onager.
Oecologia, 151(1):140–149, Feb 2007.
[31] G. Szegő. Orthogonal polynomials. American Mathematical Society, Providence, R.I., fourth edition,
1975. American Mathematical Society, Colloquium Publications, Vol. XXIII.
[32] M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, C. E. Priebe, et al. A nonparametric two-sample
hypothesis testing problem for random graphs. Bernoulli, 23(3):1599–1630, 2017.
[33] M. Tang, D. L. Sussman, C. E. Priebe, et al. Universally consistent vertex classification for latent
positions graphs. The Annals of Statistics, 41(3):1406–1430, 2013.
[34] J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational
mathematics, 12(4):389–434, 2012.
[35] V. V. Volchkov and V. V. Volchkov. Harmonic analysis of mean periodic functions on symmetric spaces
and the Heisenberg group. Springer Science & Business Media, 2009.
[36] J. A. Wolf. Harmonic analysis on commutative spaces. Number 142 in Mathematical Surveys and
Monographs. American Mathematical Soc., 2007.
[37] P. J. Wolfe and S. C. Olhede. Nonparametric graphon estimation. arXiv preprint arXiv:1309.5936,
2013.

