Spectral methods for data science:

A statistical perspective

Yuxin Chen, Statistics & Data Science, UPenn

Summer school on theoretical stats., PKU BICMR & Math, 2023
“Spectral methods for data science: a statistical perspective,” Yuxin Chen, Yuejie
Chi, Jianqing Fan, Cong Ma, Foundations and Trends in Machine Learning, 2021
 Part 1: Introduction

• Motivating applications
◦ community detection
◦ matrix/tensor completion
◦ ranking
• A general recipe for spectral methods
Motivating application: community detection
 Graph clustering / community detection

Community structures are common in many social networks

figure credit: The Future Buzz figure credit: S. Papadopoulos

Goal: partition users into several clusters based on their

friendships / similarities

Spectral methods 1-3

An idealistic model: stochastic block model (SBM)

xi = 1: 1st community xi = −1: 2nd community

• n nodes {1, · · · , n}
• 2 communities
• n unknown variables: x1 , · · · , xn ∈ {1, −1}
◦ encode community memberships

Spectral methods 1-4

An idealistic model: stochastic block model (SBM)

G
• observation: a (random) graph G
(
p, if i and j are from same community
(i, j) ∈ G with prob.
q, else
◦ p > q (i.e. more within-cluster edges than between-cluster edges)

Spectral methods 1-5

An idealistic model: stochastic block model (SBM)

G
• observation: a (random) graph G
(
p, if i and j are from same community
(i, j) ∈ G with prob.
q, else
◦ p > q (i.e. more within-cluster edges than between-cluster edges)
• goal: recover community memberships of all nodes, i.e. {x?i }

Spectral methods 1-5

 Key structure of adjacency matrix

The adjacency matrix A ∈ {0, 1}n×n of G:

(
1, if (i, j) ∈ G
Ai,j =
0, else

Spectral methods 1-6

 Key structure of adjacency matrix

A = E[A] + A − E [A]
| {z }
rank 2

WLOG, suppose x?1 = · · · = x?n/2 = 1, x?n/2+1 = · · · = x?n = −1:

Spectral methods 1-7

 Key structure of adjacency matrix

A = E[A] + A − E [A]
| {z }
rank 2

WLOG, suppose x?1 = · · · = x?n/2 = 1, x?n/2+1 = · · · = x?n = −1:

   
p11> q11> p+q > p−q 1  > 
E[A] = = 11 + 1 , −1>
| 2 {z } 2
q11> p11> −1
| {z }
uninformative bias =: x? =[x? ]
i 1≤i≤n

Spectral methods 1-7

 Spectral clustering

A = E[A] + A − E [A]
| {z }
rank 2

1. computing leading eigenvector u = [ui ]1≤i≤n of A − p+q

2 11
>
(
1, if ui > 0
2. rounding: output xi =
−1, if ui < 0

Spectral methods 1-8

 edge densit
1 >
Empirical clustering accuracy
11
empirical success rate edge density di↵erence :
0
2
0.1 0.2 0.3 0.4 0.5
=

2
1.0
11>

empirical success rate

0.9
11>

0.8


0.7
permutation
column/row

0.6
=

empirical success rate edge density di↵erence :

0 0.1 0.2 0.3 0.4 0.5

empirical success rate mean di↵erence :
A

1+δ 1−δ
0 0.1 0.2n = 100,0.3
p= 2 , =
q0.4 2 0.5

Spectral methods 1-9

1.0
Rationale: spectral clustering is reliable if A − E[A] is “small”
| {z }
perturbation
• if A − E[A] = 0, then
" #
1
u ∝ ± =⇒ perfect clustering
−1

What we’ll demonstrate: effect of perturbation A − E[A] on u

Spectral methods 1-10

Motivating application: matrix/tensor completion
 ? ? ? ?

? ? ? ?

? ? ? ?

? ? ?

figure credit: Candes et al.

• Netflix challenge: Netflix provides highly incomplete ratings from

0.5 million users for & 17,770 movies
• How to predict unseen user ratings for movies?
Spectral methods 1-12
 Matrix completion

In general, we cannot infer missing ratings

 
X ? ? ? X ?
 
? ? X X ? ?
 
X ? ? X ? ? 
 
 ? ? X ? ? X
 
X ? ? ? ? ? 
 
 
? X ? ? X ?
? ? X X ? ?

— an underdetermined system (more unknowns than observations)

Spectral methods 1-13

 Matrix completion

. . . unless rating matrix has other structure

? ? ? ?

? ? ? ?

? ? ? ?

? ? ?

A few factors explain most of the data

Spectral methods 1-14

 Matrix completion

. . . unless rating matrix has other structure

? ? ? ?

? ? ? ?

? ? ? ?

? ? ?

A few factors explain most of the data −→ low-rank approximation

Spectral methods 1-14

 Matrix completion

. . . unless rating matrix has other structure

? ? ? ?

? ? ? ?

? ? ? ?

? ? ?

A few factors explain most of the data −→ low-rank approximation

How to exploit (approx.) low-rank structure in prediction?

Spectral methods 1-14

 Model: low-rank matrix completion

 
X ? ? ? X ?
? ? X X ? ?
 
X ? ? X ? ?
? ? ? ?
 
? ? X ? ? X
  ? ? ? ?

X
 ? ? ? ? ?
? X ? ? X ?
? ? ? ?

? ? X X ? ? ? ? ?

• ground truth: rank-r matrix M ? = U ? ? ?>

| Σ{zV } ∈ R
n1 ×n2

rank-r SVD
• each entry Mi,j
? is observed independently with prob. p

• goal: fill in unseen entries of M ?

Spectral methods 1-15

 Model: low-rank matrix completion

 
X ? ? ? X ?
? ? X X ? ?
 
X ? ? X ? ?
? ? ? ?
 
? ? X ? ? X
  ? ? ? ?

X
 ? ? ? ? ?
? X ? ? X ?
? ? ? ?

? ? X X ? ? ? ? ?

• ground truth: rank-r matrix M ? = U ? ? ?>

| Σ{zV } ∈ R
n1 ×n2

rank-r SVD
• each entry Mi,j
? is observed independently with prob. p

• goal: fill in unseen entries of M ?

• intermediate step: estimate U ? , V ? , Σ?

Spectral methods 1-15

 Spectral method for matrix completion

1. construct a rescaled zero-filled matrix M = [Mi,j ] ∈ Rn1 ×n2 as

(
1 ?
p Mi,j , if Mi,j
? is observed
∀(i, j) : Mi,j =
0, else

◦ rationale: ensures E[M ] = M ?

2. compute rank-r SVD U ΣV > of M , and return M

c = U ΣV >

Spectral methods 1-16

 sampling rat
0 0.1 0.2 0.3 0.4 0.5
Empirical matrix estimation accuracy
1.0

0.9

relative estimation error

0.8

0.7

0.6

0.8

0.7

0.6

relative estimation error sampling rate : p

n = 200, r = 5

Spectral methods 1-17

 sampling rat
0 0.1 0.2 0.3 0.4 0.5
Empirical matrix estimation accuracy
1.0

0.9

relative estimation error

0.8

0.7

0.6

0.8

0.7

0.6

relative estimation error sampling rate : p

n = 200, r = 5

What we’ll see: effect of sampling rate p upon estimation accuracy

Spectral methods 1-17

 Extension: tensor data

computational genomics dynamic MRI

— fig. credit: Schreiber et al. 19 — fig. credit: Liu et al. 17

Spectral methods 1-18

 Extension: low-rank
low-ranktensor
tensorcompletion
Extension: completionKey to enabling
— exploitin
Key to enabling
= reconstruction
Key reliable
+reliable reconstructio
to enabling from incom
— exploiting—low
exploiting
CP-ranklow
structure
CP-rank struct
observed tensor: T true tensor rank-1
true tensor
tensor
rank-1 tensor

• ground truth: rank-1 tensor T ? ∈ Rn×n×n

• each entry Ti,j,k
? is observed independently with prob. p
• goal: fill in unseen entries of T ?

Spectral methods: Part 1 1-19

r
ÿ
Spectral methods T = 1-19 uıiT¢
ı
 Extension: low-rank
low-ranktensor
tensorcompletion
Extension: completionKey to enabling
— exploitin
Key to enabling
= reconstruction
Key reliable
+reliable reconstructio
to enabling from incom
— exploiting—low
exploiting
CP-ranklow
structure
CP-rank struct
observed tensor: T true tensor rank-1
true tensor
tensor
rank-1 tensor

• ground truth: rank-1 tensor T ? = u? ⊗ u? ⊗ u? ∈ Rn×n×n

• each entry Ti,j,k
? is observed independently with prob. p
• goal: fill in unseen entries of T ?

Spectral methods: Part 1 1-19

r
ÿ
Spectral methods T = 1-19 uıiT¢
ı
 Extension: low-rank
low-ranktensor
tensorcompletion
Extension: completionKey to enabling
— exploitin
Key to enabling
= reconstruction
Key reliable
+reliable reconstructio
to enabling from incom
— exploiting—low
exploiting
CP-ranklow
structure
CP-rank struct
observed tensor: T true tensor rank-1
true tensor
tensor
rank-1 tensor

• ground truth: rank-1 tensor T ? = u? ⊗ u? ⊗ u? ∈ Rn×n×n

• each entry Ti,j,k
? is observed independently with prob. p
• goal: fill in unseen entries of T ?

Can we exploit low-rank tensor structure in prediction?

Spectral methods: Part 1 1-19

r
ÿ
Spectral methods T = 1-19 uıiT¢
ı
Spectral method for low-rank
A bit tensor
more details completion
about initialization
A bit more details about initiali

A unfold
bit more details about initialization
unfold
Step 1.1: estimating span{ui }1ÆiÆr :
ı

Step 1.1:Aestimating
• matricizition: = unfold Tspan{ui }1ÆiÆr :
! " ı
!! " € "
T • matricizition:
• estimate Aof= Punfold
rank-r subspace off-diag TAA (diagonal delet
! "
estimate
Step 1.1: estimating•span{u ırank-r: subspace of Poff-diag AA
i }1ÆiÆr
€ (dia
1. construct a rescaled zero-filled tensor
! " T = [Ti,j,k ] ∈ Rn×n×n as
• matricizition: A = unfold T
( ! "
• estimate rank-r1 Tsubspace
? , if of AA€ (diagonal deletion)
is observed
T ?Poff-diag
Ti,j,k = p i,j,k i,j,k
0, else
◦ rescaling ensures E[T ] = T ?


2. matricizition: A = unfold T

Spectral methods 1-20

Spectral method for low-rank
A bit tensor
more details completion
about initialization
A bit more details about initiali

A unfold
bit more details about initialization
unfold
Step 1.1: estimating span{ui }1ÆiÆr :
ı

Step 1.1:Aestimating
• matricizition: = unfold Tspan{ui }1ÆiÆr :
! " ı
!! " € "
T • matricizition:
• estimate Aof= Punfold
rank-r subspace off-diag TAA (diagonal delet
! "
estimate
Step 1.1: estimating•span{u ırank-r: subspace of Poff-diag AA
i }1ÆiÆr
€ (dia
3. compute spectral estimates (after !diagonal
" deletion):
• matricizition: A = unfold T
! "
estimate
u ← •leading rank-r subspace of Poff-diag AA
eigenvector
(diagonal deletion)
€
of Poff-diag AA> (remove diagonal)
λ ← leading eigenvalue

4. return Tb = λu ⊗ u ⊗ u

We will explain special treatments for diagonals

Spectral methods 1-20

Motivating application: ranking
 Ranking
A fundamental problem in a wide range of contexts
• web search, recommendation systems, admissions, sports
competitions, voting, ...

PageRank
figure credit: Dzenan Hamzic
Spectral methods 1-22
 Ranking from pairwise comparisons

pairwise comparisons for ranking tennis players

figure credit: Bozóki, Csató, Temesi
Spectral methods 1-23
 Parametric models

1
score
preferencescore
wii :: preference
P1,2
• P2,1
⇤
w
i: rank •

i: rank wi : preference score

• n items to be ranked
• assign a latent score {wi? }1≤i≤n to each item, so that

item i  item j if wi? > wj?

• rank items in accordance with score estimates

Spectral methods 1-24

 Bradley-Terry-Luce (logistic) model

1
score
preferencescore
wii :: preference
P1,2
• P2,1
⇤
w
i: rank •

i: rank wi : preference score

• each pair of items (i, j) is compared independently

wj?
P {item j beats item i} =
wi? + wj?

Spectral methods 1-24

 Bradley-Terry-Luce (logistic) model

1
score
preferencescore
wii :: preference
P1,2
• P2,1
⇤
w
i: rank •

i: rank wi : preference score

• each pair of items (i, j) is compared independently

wj?
P {item j beats item i} =
wi? + wj?

wj?
ind.
1, with prob. wi? +wj?
⇐⇒ yi,j =
0, else
Spectral methods 1-24
 Spectral ranking

Key idea: consider a probability transition matrix P ? ∈ Rn×n :

 ?
 1 · ?wj ? , if i 6= j
n wi +wj
Pi,j =
?
1 − P P? , if i = j
l:l6=i i,l

Spectral methods 1-25

 Spectral ranking

Key idea: consider a probability transition matrix P ? ∈ Rn×n :

 ?
 1 · ?wj ? , if i 6= j
n wi +wj
Pi,j =
?
1 − P P? , if i = j
l:l6=i i,l

• stationary distribution π ? of P ? : π ? = P1w? w?

| {z } l l
leading left eigenvector of P ?
◦ can be seen from detailed balance property: wi? Pi,j
?
= wj? Pj,i
?

Spectral methods 1-25

 Spectral ranking

Key idea: consider a probability transition matrix P ? ∈ Rn×n :

 ?
 1 · ?wj ? , if i 6= j
n wi +wj
Pi,j =
?
1 − P P? , if i = j
l:l6=i i,l

• stationary distribution π ? of P ? : π ? = P1w? w?

| {z } l l
leading left eigenvector of P ?
◦ can be seen from detailed balance property: wi? Pi,j
?
= wj? Pj,i
?

True ranks are revealed by leading left eigenvector of P ?

Spectral methods 1-25

 Spectral ranking

1. construct a surrogate matrix P obeying

(
1
n yi,j , if i 6= j
Pi,j = P
1− l:l6=i Pi,l , if i = j

2. compute leading left eigenvector π of P as score estimate

3. rank in accordance with π

— closely related to PageRank

Spectral methods 1-26

 decouple dependency

if the (i, j)-th entry is obs

|S| |S|

empirical success rate score separation :

1
Empirical accuracy in finding top-ranked item
0 b(s,a)

if i 6= j,
l:l6=i Pi,l , if i = j.
2 (s,a)
(1 ) 1 1 leave-one-out P r

r(s,a)
?
,j ,
prior work
if the (i, j)-th entry is observed, decouple dependency

decouple dependency

1
MDP specification

else.
Q-value iteration

1
|S| |S| 0
rewards perturb

|S|
leave-one-out Pb(s,a) 1

prior work
(
score separation :

)2

1
wj? (1 1

wi? +wj? ,
1
· if i 6= j, prior work
wi? +wj? ,
1
2n (
1
=

wj?
P

)2
|S| |S|
if the (i, j)-th entry is observed,
1 Pi,l ,1 Mifi,j
?i = j.
,

P
else.
0

|S|
l:l6=i p
score

Mi,j = (1 )2 1
score

·
latent score

l success rate score0,separation : else.

2n
(

(1

1
1 ?
if the (i, j)-th entry is observed,

(
p Mi,j ,
:preference

(
ii :i: preference

? M =

p Mi,j ,

Pi,j =
w i,j
1 j
· w? +w? , if i 6= j, else.
0,
?
Pi,j = 2n P
P1,2

i j
(

0,
wj? 1
1 l:l6=i Pi,l , if i = j. 2n · w? +w? , if i 6= j,
1
(

1
• Prate

Mi,j = Pi,j = Pi j
⇤?
2,1

empirical success rate score separation :1 Pi,l , if i = j.

ww

l:l6=i
rank• w
empirical success

empirical success rate score separation :

rank wwi?i : latent
i: rank preference
scorescore
i: rank

n = 200

Spectral methods 1-27

1
 decouple dependency

if the (i, j)-th entry is obs

|S| |S|

empirical success rate score separation :

1
Empirical accuracy in finding top-ranked item
0 b(s,a)

if i 6= j,
l:l6=i Pi,l , if i = j.
2 (s,a)
(1 ) 1 1 leave-one-out P r

r(s,a)
?
,j ,
prior work
if the (i, j)-th entry is observed, decouple dependency

decouple dependency

1
MDP specification

else.
Q-value iteration

1
|S| |S| 0
rewards perturb

|S|
leave-one-out Pb(s,a) 1

prior work
(
score separation :

)2

1
wj? (1 1

wi? +wj? ,
1
· if i 6= j, prior work
wi? +wj? ,
1
2n (
1
=

wj?
P

)2
|S| |S|
if the (i, j)-th entry is observed,
1 Pi,l ,1 Mifi,j
?i = j.
,

P
else.
0

|S|
l:l6=i p
score

Mi,j = (1 )2 1
score

·
latent score

l success rate score0,separation : else.

2n
(

(1

1
1 ?
if the (i, j)-th entry is observed,

(
p Mi,j ,
:preference

(
ii :i: preference

? M =

p Mi,j ,

Pi,j =
w i,j
1 j
· w? +w? , if i 6= j, else.
0,
?
Pi,j = 2n P
P1,2

i j
(

0,
wj? 1
1 l:l6=i Pi,l , if i = j. 2n · w? +w? , if i 6= j,
1
(

1
• Prate

Mi,j = Pi,j = Pi j
⇤?
2,1

empirical success rate score separation :1 Pi,l , if i = j.

ww

l:l6=i
rank• w
empirical success

empirical success rate score separation :

rank wwi?i : latent
i: rank preference
scorescore
i: rank

n = 200

What we will demonstrate: efficacy of spectral ranking

Spectral methods 1-27

1
A unified recipe for spectral methods
 A unified recipe

identify key matrix M ? (unobserved)

ify key matrix M ? (unobserved)

1. identify a key matrix M ? — typically unobserved — whose

eigenvectors or singular vectors encode crucial information

Spectral methods 1-29

 A unified recipe
surrogage matrix M = M ? + E (observed)

identify key matrix M ? (unobserved)

inspire
identify key matrix M ? (unobserved) surrogage matrix M = M ? + E (observed)
ify key matrix M ? (unobserved)surrogage matrix M = M ? + E (observed)
identify key matrix M ? (unobserved)
identify key matrix M ? (unobserved)

1. identify a key matrix M ? — typically unobserved — whose

eigenvectors or singular vectors encode crucial information

2. construct a surrogate matrix M of M ? using data samples

Spectral methods 1-29

 A unified recipe
surrogage matrix M = M ? + Esurrogage
(observed)
matrix M = M ? + E (observed
?
identify key matrix M ? (unobserved) surrogage matrix M = M + E (observed)
surrogage matrixkey
identify M matrix ME? (observed)
= M?? + (unobserved)
surrogage matrix M = M + E (observed)
identify key matrix M ? (unobserved)
inspire identify compute M?? (unobserved)
key matrix eigenvectors/singular vectors of M
identify key matrix M ? (unobserved)
identify key matrix M ? (unobserved) surrogage
surrogage matrix matrix
M = MM ? = M + E (observed)
+E compute eigenvectors singular vectors of M
(observed)
compute eigenvectors singular vectors of M
ify key matrix M ? (unobserved)surrogage matrix M = M ? + E (observed)
compute eigenvectors singular vectors of M
identify
identify key matrix
key matrix M ? (unobserved)
M ? (unobserved)
identify key matrix M ? (unobserved)
estimate eigenvectors singular vectors of M

1. identify a key matrix M ? — typically unobserved — whose

eigenvectors or singular vectors encode crucial information

2. construct a surrogate matrix M of M ? using data samples

3. compute corresponding eigenvectors or singular vectors of M

Spectral methods 1-29

 Key factors

A few factors that dictate the performance of spectral methods:

• proximity of M and M ? (e.g. kM − M ? k)

• spectrum (e.g. eigenvalues, singular values) of M ?
• ...

Spectral methods 1-30

 Key factors

A few factors that dictate the performance of spectral methods:

• proximity of M and M ? (e.g. kM − M ? k)

• spectrum (e.g. eigenvalues, singular values) of M ?
• ...

Aim of this tutorial: quantify influences of these factors

Spectral methods 1-30

 (Non)-

(large-scale)
(large-scale) optimization optimization
(high-dimensional) (high-dimensional) statistics
statistics

matrix perturbation high-dimensional statistics

(large-scale) optimization (high-dimensional)
theory statistics probabi
nonconvex optimization high-dimensional
high-dimensional statistics probabil
statistics probability

• algebraic tools: matrix perturbation theory (Part 2)

• statistical & probabilistic tools:

◦ matrix concentration bounds (Part 3: `2 analysis)
◦ leave-one-out analysis (Part 4: fine-grained analysis)

Spectral methods 1-31

 Asymptotic notation used in this tutorial
• f (n) . g(n) or f (n) = O(g(n)) means
|f (n)|
lim ≤ const
n→∞ |g(n)|

• f (n) & g(n) means

|f (n)|
lim ≥ const
n→∞ |g(n)|

• f (n)  g(n) means

|f (n)|
const1 ≤ lim ≤ const2
n→∞ |g(n)|
• f (n) = o(g(n)) means
|f (n)|
lim = 0
n→∞ |g(n)|
Spectral methods 1-32
 Part 2: Matrix perturbation theory

• Eigen-space perturbation theory

◦ Distances and angles between two subspaces
◦ The Davis-Kahan sin Θ theorem
• Singular subspace perturbation theory (Wedin’s theorem)
• Eigenvector perturbation for probability transition matrices
Eigen-space perturbation theory
 Setup and notation

Consider 2 symmetric matrices M ? , M = M ? + E ∈ Rn×n with

eigen-decompositions
n
" #" #
X Λ? U ?>
M = ?
λ?i u?i u?>
i = [U ?
, U⊥? ]
i=1
Λ?⊥ U⊥?>
n
" #" #
X Λ U>
M= λi ui u> = [U , U⊥ ]
i=1
i
Λ⊥ U⊥>

• eigenvalues: λ?1 ≥ · · · ≥ λ?n , λ1 ≥ · · · ≥ λn

• U = [u1 , · · · , ur ] ∈ Rn×r , Λ = diag ([λ1 , · · · , λr ]) ∈ Rr×r , · · ·

Spectral methods 2-3

 Setup and notation

h i
M= u1 ··· ur ur+1 ··· un
| {z }| {z }
U =: U⊥
 
λ1  
 ..  u> 

.
1



 .. 
 λr  .  =: U >

 |  
 {z }   u> r 
 =: Λ  
·  
 λr+1  
 ..   u>
r+1 
 .  ..  =: U >
 
  . 

⊥
 λn  
| {z } u> n
=: Λ⊥

Spectral methods 2-4

 Setup and notation

• Or×r : set of all r × r orthonormal matrices

• kM k: spectral norm (largest singular value of M )

q qP
• kM kF : Frobenius norm (kM kF = tr(M > M ) = 2 )
Mi,j
i,j

Spectral methods 2-5

 Eigen-space perturbation theory

Main focus: how does perturbation matrix E affect “distance”

between U ? and U ?

Question #0: how to define distance between two subspaces?

Spectral methods 2-6

 Eigen-space perturbation theory

Main focus: how does perturbation matrix E affect “distance”

between U ? and U ?

Question #0: how to define distance between two subspaces?

• kU − U ? kF and kU − U ? k are not appropriate, since they fall

short of accounting for global orthonormal transformation
| {z }
∀ orthonormal R∈Rr×r , U and U R represent same subspace

Spectral methods 2-6

Distances and angles between two subspaces
 Two valid choices of distance metrics

Key: taking care of global orthonormal transformation

• Distance modulo optimal rotation: adjust for rotation before

computing distance:


dist U , U ? := min UR − U? (2.1)
R∈Or×r

Spectral methods 2-8

 Two valid choices of distance metrics

Key: taking care of global orthonormal transformation

• Distance modulo optimal rotation: adjust for rotation before

computing distance:


dist U , U ? := min UR − U? (2.1)
R∈Or×r

• Distance using projection matrices: replace U (resp. U ? )

with its associated projection matrix before computing distance:


distp U , U ? := U U >} − U ? U ?>
| {z (2.2)
projection onto subspace U

Spectral methods 2-8

 (Near)-equivalence of two distance metrics

dist U , U ? := min UR − U?
R∈Or×r


distp U , U ? := U U − U ? U ?>
>

Lemma 2.1
Suppose [U , U⊥ ], [U ? , U⊥? ] are square orthonormal matrices. Then


√

distp U , U ? ≤ dist U , U ? ≤ 2 distp U , U ?

• dist(·, ·) and distp (·, ·) are orderwise equivalent

• proof: see Section 2.6.3 of Chen et al. 21

Spectral methods 2-9

 An alternative expression for distp (·, ·)

As it turns out, distp (·, ·) has several equivalent expressions:

Lemma 2.2
Recall that [U , U⊥ ], [U ? , U⊥? ] are square orthonormal matrices. Then
distp (U , U ? ) = kU > U⊥? k = kU ?> U⊥ k

Spectral methods 2-10

 An alternative expression for distp (·, ·)

As it turns out, distp (·, ·) has several equivalent expressions:

Lemma 2.2
Recall that [U , U⊥ ], [U ? , U⊥? ] are square orthonormal matrices. Then
distp (U , U ? ) = kU > U⊥? k = kU ?> U⊥ k

• sanity check: if U = U ? , then dist(U , U ? ) = kU > U ? k = 0

• proof: see Slide 2-15

Spectral methods 2-10

 ( 1, if ui > 0
1, if u > 0 x̂ =
x̂i = Principal angles between two1, subspaces
i i
if ui < 0
1, if ui < 0
r 
r
In addition to “distance”,
 p q
one might also be interested in1“angles”
p q 1 û =
û = 2 1
2 1
✓i
✓

We can quantify the similarity between two lines (represented resp. by

unit vectors u and u? ) by an angle between them

θ = arccoshu, u? i

Spectral methods 2-11

 Principal angles between two eigen-spaces

For r-dimensional subspaces, one needs r angles

Specifically, given kU > U ? k ≤ 1, write the SVD of U > U ? ∈ Rr×r as

 
cos θ1
U >U ? = X 
 ..
.
 >
Y =: X cos Θ Y
>

cos θr
| {z }
=: cos Θ

• X, Y ∈ Rr×r : square orthonormal matrices

• {θ1 , · · · , θr } are called the principal angles between U and U ?

Spectral methods 2-12

 Relations between principal angles and distance

As expected, principal angles and distances are closely related

Lemma 2.3
Suppose [U , U⊥ ], [U ? , U⊥? ] are square orthonormal matrices. Then
kU > U⊥? k = k sin Θk = max{| sin θ1 |, · · · , | sin θr |}

Lemmas 2.2 and 2.3 taken collectively give

distp (U , U ? ) = max{| sin θ1 |, · · · , | sin θr |} (2.3)

Spectral methods 2-13

 Proof of Lemma 2.3

1
kU > U⊥? k = U > U⊥? U⊥?> U 2
| {z }
=I−U ? U ?>
1
= U > U − U > U ? U ?> U 2

1
= I − X cos2 Θ X > 2
(since U > U ? = X cos Θ Y > )
1
= I − cos2 Θ 2

= k sin Θ2 k 2
1

= k sin Θk

Spectral methods 2-14

 Proof of Lemma 2.2
We first claim that the SVD of U⊥ U can be written as
> ?

U =X
> ?
U⊥ f sin Θ Y > (2.4)

for some orthonormal X

f (to be proved later). Armed w/ this claim, one has
 >   
U X cos Θ Y >
U ? = [U , U⊥ ] > U ?
= [U , U⊥ ] f sin Θ Y >
U⊥ X
" # 
X cos2 Θ X > X cos Θ sin Θ X
f> U>
=⇒ U U ? ?>
= [U , U⊥ ]
f cos Θ sin Θ X >
X Xf sin2 Θ Xf> >
U⊥

As a consequence,
U U > − U ? U ?>
" # 
I − X cos2 Θ X > −X cos Θ sin Θ X
f> U>
= [U , U⊥ ]
−Xf cos Θ sin Θ X > −Xf sin2 Θ Xf> >
U⊥

Spectral methods 2-15

 Proof of Lemma 2.2 (cont.)
This further gives

U U > − U ? U ?>
   
X sin2 Θ − cos Θ sin Θ X>
= f
X − cos Θ sin Θ − sin2 Θ f>
X
 
sin2 Θ − cos Θ sin Θ
= (k · k is rotationally invariant)
− cos Θ sin Θ − sin2 Θ
| {z }
each block is a diagonal matrix
 
sin2 θi − cos θi sin θi
= max
1≤i≤r − cos θi sin θi − sin2 θi
 
sin θi − cos θi
= max sin θi
1≤i≤r − cos θi − sin θi
= max | sin θi | = k sin Θk
1≤i≤r

Spectral methods 2-16

 Proof of Lemma 2.2 (cont.)

It remains to justify (2.4). To this end, observe that

U = U ?> U ? − U ?> U U > U ?

> ?
U ?> U⊥ U⊥
= I − Y cos2 Θ Y >
= Y sin2 Θ Y >

and hence the right singular space (resp. singular values) of U ?> U⊥ is given
by Y (resp. sin Θ). This immediately implies (2.4).

Spectral methods 2-17

Summary: four (almost) equivalent distance metrics

1) U U > − U ? U ?>
2) sin Θ
3) U⊥> U ? = U > U⊥?
4) min UR − U?
R∈Or×r

Spectral methods 2-18

Summary: four (almost) equivalent distance metrics

1) U U > − U ? U ?>
2) sin Θ
3) U⊥> U ? = U > U⊥?
4) min UR − U?
R∈Or×r

Near-equivalence of these metrics continue to hold if k · k is replaced

by k · kF

Spectral methods 2-18

The Davis-Kahan sin Θ theorem
Warm-up example (0 <  < 1):
" # " # " #
1+ 0 −  1 
M = ?
, E= , M=
0 1−    1

Spectral methods 2-20

Warm-up example (0 <  < 1):
" # " # " #
1+ 0 −  1 
M = ?
, E= , M=
0 1−    1

• leading eigenvectors of M ? and M :

" # " #
1 1 1 1
u?1 = , u1 = √ =⇒ u1 u> ? ?>
1 − u1 u1 =√
0 2 1 2
2

— eigenvector distance is large regardless of size of  (or size of kEk)

Spectral methods 2-20

Warm-up example (0 <  < 1):
" # " # " #
1+ 0 −  1 
M = ?
, E= , M=
0 1−    1

• leading eigenvectors of M ? and M :

" # " #
1 1 1 1
u?1 = , u1 = √ =⇒ u1 u> ? ?>
1 − u1 u1 =√
0 2 1 2
2

— eigenvector distance is large regardless of size of  (or size of kEk)

Diagonsis: eigen-gap λ?1 − λ?2 = 2 also small (proportional to kEk)

— both perturbation size and eigen-gap might play important roles

Spectral methods 2-20

 Davis-Kahan sin Θ Theorem: a simple case

— recall the setup in Page 2-3

Chandler Davis William Kahan

Theorem 2.4
√
Suppose M ?  0 and has rank r. If kEk < (1 − 1/ 2)λ?r , then
√ √

2kEU ? k 2kEk
distp U , U = U⊥ U = k sin Θk ≤
? > ?
≤
λ?r λ?r

Spectral methods 2-21

 Interpretations

√
Suppose M ?  0 and has rank r. If kEk < (1 − 1/ 2)λ?r , then
√ √
?
2kEU ? k 2kEk
distp U , U ≤ ?
≤
λr λ?r

Key factors: 1. eigen-gap: λ?r = λ?r − λ?r+1

| {z }
=0
2. perturbation size: kEk
3. signal-to-noise ratio (SNR): λ?r
kEk

• the bound w/ kEU ? k is sometimes useful (e.g. for `∞ analysis)

Spectral methods 2-22

 Proof of Theorem 2.4

We intend to control U⊥ U by studying their interactions through E:

> ?

 
>
U⊥ EU ? = U⊥ >
U ΛU > + U⊥ Λ⊥ U⊥>
−U ? ? ?>
Λ U U?
| {z } | {z ? }
M ? +E M

= Λ⊥ U⊥
> ? > ? ?
U − U⊥ U Λ (since U⊥ U = U⊥
?> ? >
U = 0)
> ? ?
≥ U⊥ > ?
U Λ − Λ⊥ U⊥ U (triangle inequality)
≥ > ?
U⊥ U λ?r − > ?
U⊥ U kΛ⊥ k (2.5)

Weyl’s Theorem gives kΛ⊥ k ≤ kEk, which combined with (2.5) yields
>
U⊥ EU ? kU⊥ k · kEU ? k kEU ? k
> ?
U⊥ U ≤ ≤ =
λ?r − kEk λ?r − kEk λ?r − kEk
√
This together with assumption kEk ≤ (1 − 2/2)λ?r and Lemmas 2.2-2.3
completes the proof

Spectral methods 2-23

 Davis-Kahan’s sin Θ theorem: general case
— eigenvalues(A): set of eigenvalues of A

Theorem 2.5 (Davis-Kahan’s sinΘ theorem: general version)

Assume that
eigenvalues(Λ? ) ⊆ (−∞, α − ∆] ∪ [β + ∆, ∞); (2.6a)
eigenvalues(Λ?⊥ ) ⊆ [α, β]. (2.6b)
√
for some eigengap ∆ > 0. Suppose kEk ≤ (1 − 2/2)∆. Then

√
√ 2kEU ? k 2kEk
dist U , U ? ≤ 2 distp U , U ? = 2 k sin Θk ≤ ≤
∆ ∆

Spectral methods 2-24

 Davis-Kahan’s sin Θ theorem: general case
— eigenvalues(A): set of eigenvalues of A

Theorem 2.5 (Davis-Kahan’s sinΘ theorem: general version)

Assume that
eigenvalues(Λ? ) ⊆ (−∞, α − ∆] ∪ [β + ∆, ∞); (2.6a)
eigenvalues(Λ?⊥ ) ⊆ [α, β]. (2.6b)
√
for some eigengap ∆ > 0. Suppose kEk ≤ (1 − 2/2)∆. Then

√
√ 2kEU ? k 2kEk
dist U , U ? ≤ 2 distp U , U ? = 2 k sin Θk ≤ ≤
∆ ∆

• conclusion remains valid if Assumption (2.6) is reversed

• proof: see Section 2.3.4 of Chen et al. ’21

Spectral methods 2-24

Singular subspace perturbation theory
 Setup and notation

Consider 2 matrices M ? , M = M ? + E ∈ Rn1 ×n2 (n1 ≤ n2 ) w/ SVD

" #" #
n1
X h i Σ? 0 0 V ?>
M? = σi? u?i vi?> = U ? U⊥?
i=1
0 Σ?⊥ 0 V⊥?>
" #" #
n1
X h i Σ 0 0 V>
M= σi ui vi> = U U⊥
i=1
0 Σ⊥ 0 V⊥>

• σ1 ≥ · · · ≥ σn1 : singular values of M

• σ1? ≥ · · · ≥ σn? 1 : singular values of M ?


• U = [u1 , . . . , ur ] ∈ Rn1 ×r , Σ = diag λ1 , . . . , λr ∈ Rr×r , . . .

Spectral methods 2-26

 Wedin’s sin Θ theorem

Davis-Kahan’s theorem generalizes to singular subspace perturbation:

Theorem 2.6 (Wedin’s sinΘ theorem)

√
If kEk < (1 − 1/ 2)(σr? − σr+1
?
), then one has
| {z }
spectral gap


√ 


max dist U , U ? , dist V , V ? ≤ 2 max distp U , U ? , distp V , V ?

2 max kE > U ? k, kEV ? k 2kEk
≤ ? ≤ ? ?
σr − σr+1
? σr − σr+1

• both EV ? and E > U ? matter

Spectral methods 2-27

 Proof of Theorem 2.6
Similar to proof of Davis-Kahan theorem, we concentrate on U⊥> U ? :


U⊥> U ? = U⊥> U ? Σ? V ?> V ? Σ?−1
 
= U⊥> M − E − U⊥? Σ?⊥ V⊥?> V ? Σ?−1
| {z }
=M ?
  ? ?−1
= U⊥> U 
ΣV >
+ U⊥ Σ⊥ V⊥> − E − 
U⊥? 
Σ
?
V
⊥ ⊥
?>
V Σ
| {z }
=M
= > ? ?−1
Σ⊥ V⊥ V Σ − U⊥> EV ? Σ?−1
Applying triangle inequality and Weyls’ inequality yields
U⊥> U ? ≤ kΣ⊥ k · V⊥> V ? · kΣ?−1 k + kU⊥> k · EV ? · kΣ?−1 k
1 1
= σr+1 · V⊥> V ? · ? + EV ? · ?
σr σr
σ ? + kEk EV ?
≤ r+1 ? V⊥> V ? + (2.7)
σr σr?
Spectral methods 2-28
 Proof of Theorem 2.6 (cont.)

Repeating the same argument yields

?
σr+1 + kEk kE > U ? k
V⊥> V ? ≤ U⊥
> ?
U + (2.8)
σr? σr?

Combine inequalities (2.7) and (2.8) to obtain


 max E > U ? , EV ?
max U⊥> U ? , V⊥> V ? ≤
σr?
?
σr+1 + kEk 
+ max U⊥> U ? , V⊥> V ?
σr?
√
Rearrange terms and utilize kEk < (1 − 2/2)(σr? − σr+1
? ) and

Lemma 2.1 to arrive at desired result

Spectral methods 2-29

 Eigenvector perturbation for
probability transition matrices
 Eigen-decomposition for asymmetric matrices

Eigen-decomposition for asymmetric matrices is more tricky:

1. both eigenvalues & eigenvectors might be complex-valued
2. eigenvectors might not be orthogonal to each other

Spectral methods 2-31

 Eigen-decomposition for asymmetric matrices

Eigen-decomposition for asymmetric matrices is more tricky:

1. both eigenvalues & eigenvectors might be complex-valued
2. eigenvectors might not be orthogonal to each other

Let us look at a special case: probability transition matrices

Spectral methods 2-31

 1 log n
kXi,j k  max Mi,j . := B
• Take matrix Bernstein inequality to yield: if ppn log3 n/n, the
p i,j

Probability transition matrices

• Take matrix Bernstein p log13 n/n, th
kM̂ inequality
M k . vto logyield:
n + Biflog
p n⌧
p
kM̂ M k . v log n + B log n ⌧ 1
1
• P2,1 P1,2 6
• P22,1 P1,2 ... 5
3 4

Consider a Markov chain {Xt }t≥0

• n states
• transition probability P{Xt+1 = j | Xt = i} = Pi,j
• transition matrix P = [Pi,j ]1≤i,j≤n
• stationary distribution π = [πi ]1≤i≤n obeys

π ≥ 0, 1> π = 1, and π>P = π>

◦ leading left eigenvector of P with eigenvalue 1
Spectral methods 2-32
 Reversible Markov chains

Markov chain {Xt }t≥0 with transition matrix P and stationary

distribution π is said to be reversible if

πi Pi,j = πj Pj,i for all i, j

— detailed balance condition

• If P represents reversible chain, then all eigenvalues of P are real

Spectral methods 2-33

 Setup and notation

• P ? : probability transition matrix of a reversible Markov chain

• P = P ? + E: (perturbed) probability transition matrix
• π ? (resp. π): leading left eigenvectors of P ? (resp. P )

Question: how does perturbation E affect leading left eigenvector?

Additional notation: for any probability vector π = [πi ]1≤i≤n > 0:

qP
• vector norm: kxkπ := 2 with x = [xi ]1≤i≤n
i π i xi

• matrix norm: kAkπ := supkxkπ =1 kAxkπ with A = [Ai,j ]1≤i,j≤n

Spectral methods 2-34

 Eigenvector perturbation for transition matrices

Theorem 2.7 (Chen, Fan, Ma, Wang ’19)

Suppose P ? represents a reversible Markov chain, whose stationary

distribution vector π ? is strictly positive. Assume
√   
kEkπ? < (1 − 1/ 2) 1 − max λ2 (P ? ), −λn (P ? )

Then one has

√
? 2 kπ ?> Ekπ?
kπ − π kπ? ≤ 
1 − max λ2 (P ? ), −λn (P ? )

• similar to Davis-Kahan theorem


• eigengap: 1 − max λ2 (P ? ), −λn (P ? ) since 1 = λ1 (P ? )
• perturbation size: π ?> E π?
Spectral methods 2-35
 Part 3: Application of `2 perturbation theory

• Matrix tail bounds

• Community detection
• Matrix completion
• Ranking from pairwise comparisons
Matrix tail bounds
 A hammer: matrix Bernstein inequality


Consider a sequence of independent random matrices Xl ∈ Rd1 ×d2
• E[Xl ] = 0 • kXl k ≤ B for each l
• variance statistic:
n hX i hX i o
v := max E Xl Xl> , E Xl> Xl
l l

Theorem 3.8 (Matrix Bernstein inequality)

For all τ ≥ 0, !
n X o −τ 2 /2
P Xl ≥ τ ≤ (d1 + d2 ) exp
l v + Bτ /3

Spectral methods 3-3

 A hammer: matrix Bernstein inequality

!
n X o −τ 2 /2
P Xl ≥ τ ≤ (d1 + d2 ) exp
l v + Bτ /3

• moderate-deviation regime (τ is small):

— sub-Gaussian tail behavior exp(−τ 2 /2v)

• large-deviation regime (τ is large):

— sub-exponential tail behavior exp(−3τ /2B) (slower decay)

• user-friendly form (exercise): with prob. 1 − O((d1 + d2 )−10 )

X q
Xl . v log(d1 + d2 ) + B log(d1 + d2 ) (3.9)
l

Spectral methods 3-4

Another hammer: spectral norm of random matrices
w/ independent entries

Consider a symmetric random matrix X = [Xi,j ]1≤i,j≤n with

independent entries s.t. ∀(i, j):
• E[Xi,j ] = 0 • Var(Xi,j ) ≤ σ 2 • |Xi,j | ≤ B

Theorem 3.9 (Bandeira, van Handel ’16)

With probability exceeding 1 − O(n−10 ),

√ p

kXk ≤ 4σ n + O B log n

• often tighter than matrix Bernstein by some log factor

Spectral methods 3-5

Community detection
 Recap: spectral clustering for SBMs

xi = 1: 1st community xi = −1: 2nd community

• n nodes {1, · · · , n} • 2 communities
• community memberships to recover: x = [xi ]1≤i≤n ∈ {1, −1}n
• observed: an adjacency matrix A of a random graph s.t.
(

p, if xi = xj
P Ai,j = 1 =
q, else
Spectral methods 3-7
 Recap: spectral clustering for SBMs

A = E[A] + A − E [A]
| {z }
= p+q
2
11> + p−q
2
xx>

1. computing leading eigenvector u = [ui ]1≤i≤n of A − p+q

2 11
>
(
1, if ui > 0
2. rounding: output xi =
−1, if ui < 0

Spectral methods 3-8

 Analysis via Davis-Kahan’s theorem
Let us apply Davis-Kahan to analyze accuracy of spectral clustering:
p+q >
• take M ? = E[A] − 11
| {z 2 }
= p−q
2
xx>

◦ leading eigenvector (resp. value) u? = √1 x?

n
(resp. λ? = (p−q)n
2 )
• take M = A − p+q
2 11
> w/ leading eigenvector u
• Theorem 2.4 yields

2kM − M ? k 2kA − E[A]k

dist(u, u? ) ≤ ? = (p−q)n
(3.10)
λ1
2

Spectral methods 3-9

 Analysis via Davis-Kahan’s theorem
Let us apply Davis-Kahan to analyze accuracy of spectral clustering:
p+q >
• take M ? = E[A] − 11
| {z 2 }
= p−q
2
xx>

◦ leading eigenvector (resp. value) u? = √1 x?

n
(resp. λ? = (p−q)n
2 )
• take M = A − p+q
2 11
> w/ leading eigenvector u
• Theorem 2.4 yields

2kM − M ? k 2kA − E[A]k

dist(u, u? ) ≤ ? = (p−q)n
(3.10)
λ1
2

Question: how to bound kA − E[A]k?

Spectral methods 3-9

 Bounding kA − E[A]k

Lemma 3.10
log n
Consider SBM with p > q & n . Then with prob. 1 − O(n−10 ),
√
kA − E[A]k . np (3.11)

(
p(1 − p) if xi = xj
proof: note that • Var(Ai,j ) = ≤ p =: σ 2
q(1 − q) else
• Ai,j ≤ 1 =: B
log n
Applying Theorem 3.9 and using p & n conclude the proof

Spectral methods 3-10

 Statistical accuracy of spectral clustering

Substitute (3.11) into (3.10) to reach

√
2kA − E[A]k np
dist(u, u ) ≤
?
.
(p−q)n (p − q)n
2
√
provided that (p − q)n  np

Thus, under condition p−q

√  √1 , with high prob. one has
p n

dist(u, u? )  1 =⇒ almost exact clustering

Spectral methods 3-11

 Statistical accuracy of spectral clustering

p−q 1
√ √ =⇒ almost exact clustering (3.12)
p n

• dense regime: if p  q  1, then this condition reads

1
p−q  √
n
α log n β log n
• “sparse” regime: if p = n and q = n for α, β  1, then
1
α−β  √
log n

This condition is information-theoretically optimal (up to log factor)

— Mossel, Neeman, Sly ’15, Abbe ’18
Spectral methods 3-12
Matrix completion
 Recap: spectral method for matrix completion
 
X ? ? ? X ?
? ? X X ? ?
 
X ? ? X ? ?
? ? ? ?
 
? ? X ? ? X
  ? ? ? ?

X
 ? ? ? ? ?
? X ? ? X ?
? ? ? ?

? ? X X ? ? ? ? ?

• ground truth: M ? = u? v ?> ∈ Rn×n (a simple case)

1 1 indep.
u? = e
u, v? = ve, e v
u, e ∼ N (0, In )
kuk
e 2 kvek2

• each entry Mi,j

? is observed independently with prob. p

• goal: fill in unseen entries of M ?

Spectral methods 3-14
 Recap: spectral method for matrix completion

1. construct a rescaled zero-filled matrix M = [Mi,j ] ∈ Rn1 ×n2 as

(
1 ?
p Mi,j , if Mi,j
? is observed
∀(i, j) : Mi,j =
0, else

◦ rationale: ensures E[M ] = M ?

2. compute rank-1 SVD σuv > of M , and return M

c = σuv >

How does sampling rate p affect estimation accuracy?

Spectral methods 3-15

 Statistical accuracy of spectral estimate
√
? √
2
From Wedin’s Theorem: if kM − M ? k ≤ 1 − 2 σ1 = 1 − 22 , then

2kM − M ? k
max {dist(u, u? ), dist(v, v ? )} ≤  kM − M ? k
σ1?
s
log2 n
. (3.13)
np

where last inequality is a consequence of:

Lemma 3.11
log n
Suppose p  n . Then with high prob.,
s
log2 n
kM − M ? k . = o(1) (3.14)
np

Spectral methods 3-16

 Sample complexity

For rank-1 matrix completion, (3.13) implies

log2 n
p =⇒ nearly accurate estimates of u? & v ?
n
=⇒ nearly accurate estimates of M ?

To yield reliable spectral estimates, it suffices to have sample size

n2 p  n log2 n
| {z }
optimal up to log factor

Spectral methods 3-17

 Proof of inequality (3.14)

• First, based on Gaussianity, we have

1 log n
max |Mi,j
?
|. =: B (check)
p i,j pn
• Next,

1−p ? 2 log2 n
max Var Mi,j = max(Mi,j ) . 2 =: σ 2
i,j p i,j n p
 
Applying Theorem 3.9 w/ dilation trick kAk = A>
A
gives

√ p log n log3/2 n log n

kM − M ? k . σ n + B log n  √ +  √
np np np

Spectral methods 3-18

Ranking from pairwise comparisons
 Recap: spectral ranking for BTL model

1
score
preferencescore
wii :: preference
P1,2
• P2,1
⇤
w
i: rank •

i: rank wi : preference score

• n items with latent scores w1? , . . . , wn?

• each pair of items (i, j) is compared independently

wj?
ind.
1, with prob. wi +wj?
yi,j =
?
⇐⇒
0, else

• estimate w? = [wi? ]1≤i≤n (and rank items)

Spectral methods 3-20
 Recap: spectral ranking for BTL model
A key probability transition matrix P ? ∈ Rn×n :
 ?
 1 · ?wj ? , if i 6= j
n wi +wj
Pi,j =
?
1 − P P? , if i = j
l:l6=i i,l

1. construct a surrogate matrix P obeying

(
1
n yi,j , if i 6= j
Pi,j = P
1− l:l6=i Pi,l , if i = j

2. compute leading left eigenvector π of P as score estimate

3. rank in accordance with π

Can we characterize the accuracy of spectral estimates?

Spectral methods 3-21

 Analysis of spectral ranking

Apply Theorem 2.7 to yield

π ?> E π?
kπ − π ? kπ? .
1 − max {λ2 (P ? ), −λn (P ? )}

with E = P − P ? , provided that

√   
kEkπ? ≤ (1 − 1/ 2) 1 − max λ2 (P ? ), −λn (P ? )

Spectral methods 3-22

 Analysis of spectral ranking

Apply Theorem 2.7 to yield

π ?> E π?
kπ − π ? kπ? .
1 − max {λ2 (P ? ), −λn (P ? )}

with E = P − P ? , provided that

√   
kEkπ? ≤ (1 − 1/ 2) 1 − max λ2 (P ? ), −λn (P ? )

— need to understand spectral gap and noise size

Spectral methods 3-22

 Analysis of spectral ranking (cont.)
max1≤i≤n wi?
condition number: κ :=
min1≤i≤n wi?

Lemma 3.12 (spectral gap)

 1
1 − max λ2 (P ? ), −λn (P ? ) ≥
2κ2

• proof is based on comparison between two reversible Markov

chains; see Section 3.6.4 of Chen et al. ’21

Lemma 3.13 (noise size)

With probability at least 1 − O(n−8 ), s

√ κ log n
kEkπ? ≤ κ kEk .
n
Spectral methods 3-23
 Analysis of spectral ranking (cont.)
Recall perturbation bound

π ?> E π?
kπ − π ? kπ? ≤
1 − max {λ2 (P ? ), −λn (P ? )} − kEkπ?
≤ 4κ2 π ?> E π?
(provided that n  κ5 log n)

Note that for any v, one has

p 1
kvkπ? ≤ ?
πmax kvk2 , and kvk2 ≤ p ? kvkπ?
πmin
As a result, one has
1 4κ2
kπ − π ? k2 ≤ p ? kπ − π ?
k π ? ≤ p ?>
? kπ Ekπ
?
πmin πmin
≤ 4κ2.5 kπ ?> Ek2 ≤ 4κ2.5 kEk kπ ? k2

Spectral methods 3-24

 Analysis of spectral ranking (cont.)

Assuming κ = O(1), we arrive at

s
log n ?
kπ − π k2 .
?
kπ k2
n

• vanishingly small error as n → ∞

• optimal error up to log factor

— Negahban, Oh, Shah ’16, Chen, Fan, Ma, Wang ’19

Spectral methods 3-25

 Proof of Lemma 3.13
By construction of P and P ? , we see that
1

Ei,j = Pi,j − Pi,j
?
= yi,j − E[yi,j ]
n
for any i 6= j. In addition, for all 1 ≤ i ≤ n, it follows that
X 1 X

Ei,i = Pi,i − Pi,i
?
=− Ei,j = − yi,j − E[yi,j ]
j:j6=i
n j:j6=i

We shall decompose E into three parts: upper triangular, diagonal,

and lower triangular parts:

kEk ≤ kEupper k + kEdiag k + kElower k

— we will upper bound kEupper k

Spectral methods 3-26
 Proof of Lemma 3.13 (controlling kEdiag k)

Observe that
1 X

kEdiag k = max |Ei,i | = max yi,j − E[yi,j ]
1≤i≤n 1≤i≤n n
j:j6=i
| {z }
=:Xj

To invoke Bernstein’s inequality, note that

• |Xj | ≤ 1 =: B
P 2 P
• j:j6=i E[Xj ] = j:j6=i Var(yi,j ) ≤ n =: v
Bernstein’s inequality + union bound reveal that: with high prob.
s
1 p log n
max |Ei,i | . ( v log n + B log n) 
i n n

Spectral methods 3-27

 Proof of Lemma 3.13 (controlling kEupper k)

1 1
• n |yi,j | ≤ n =: B


• Var n1 yi,j ≤ n12 =: σ2

 
Applying Theorem 3.9 w/ dilation trick kAk = A>
A
gives
√
√ p 1 log n 1
kEupper k . σ n + B log n  √ + √
n n n

— same bound holds for kElower k

Spectral methods 3-28

 Part 4: `∞ and `2,∞ perturbation theory

• Motivation
◦ exact community recovery
◦ top-K ranking
• Leave-one-out analysis: an illustrative example
• `∞ eigenvector perturbation theory (rank-1)
• Application: exact recovery in community detection
• `2,∞ eigen-space perturbation theory (rank-r)
Motivation: exact community recovery
 Revisiting spectral clustering for SBMs

1. computing the leading eigenvector u = [ui ]1≤i≤n of A − p+q

2 11
>
(
1, if ui ≥ 0
2. rounding: output xi =
−1, if ui < 0

Spectral methods 4-3

 Revisiting spectral clustering for SBMs

log n
It has been shown in (3.12) that: if p  q  n , then
√
log n
δ := p − q  =⇒ almost exact recovery
n

• Almost exact recovery means

( )
1X n
 1X n

min 1 xi 6= x?i , 1 xi 6= −x?i = o(1)
n i=1 n i=1

Spectral methods 4-4

 edge density di↵erence
1

1
1
2
Exact recovery of all community memberships?

1
=


#

1 > 1
2
When δ := p − q increases, exact recovery becomes possible:
n/2

11 +
1n/2 1>

 P | {z }
Pn
min edge
empirical success rate 1{x 6=x },
n di↵erence : ? 1
1 density
1{xi 6=−x?i } =0
2
n i=1 i i n i=1
0 0.1 0.2 0.3 0.4 0.5
=

2
n/2
1n/2 1>

1.0
11>

empirical success rate

else.

0.9
11>
"
after column/row permutation

0.8

0,

0.7
permutation
column/row

0.6
=
=

empirical success rate edge density di↵erence :

0 0.1 0.2 0.3 0.4 0.5

empirical success rate mean di↵erence :
A

0 0.1 0.2 0.3 0.4 0.5

A

1.0
Spectral methods 4-5
 edge density di↵erence
1

1
1
2
Exact recovery of all community memberships?

1
=


#

1 > 1
2
When δ := p − q increases, exact recovery becomes possible:
n/2

11 +
1n/2 1>

 P | {z }
Pn
min edge
empirical success rate 1{x 6=x },
n di↵erence : ? 1
1 density
1{xi 6=−x?i } =0
2
n i=1 i i n i=1
0 0.1 0.2 0.3 0.4 0.5
=

2
n/2
1n/2 1>

1.0
11>

empirical success rate

else.

0.9
11>
"
after column/row permutation

0.8

0,

0.7
permutation
column/row

0.6
=
=

empirical success rate edge density di↵erence :

0 0.1 0.2 0.3 0.4 0.5

empirical success rate mean di↵erence :
A

0 0.1 0.2 0.3 0.4 0.5

`2 perturbation theory alone falls short of explaining exact recovery
A

1.0 — calls for more fine-grained analysis

Spectral methods 4-5
 Exact recovery ← `∞ theory

exact recovery means ui u?i > 0, ∀i (or ui u?i < 0, ∀i)

Spectral methods 4-6

 Exact recovery ← `∞ theory

exact recovery means ui u?i > 0, ∀i (or ui u?i < 0, ∀i)

√ √
ku − u? k∞ < 1/ n or ku + u? k∞ < 1/ n

Spectral methods 4-6

 Exact recovery ← `∞ theory

exact recovery means ui u?i > 0, ∀i (or ui u?i < 0, ∀i)

√ √
ku − u? k∞ < 1/ n or ku + u? k∞ < 1/ n

`∞ eigenvector perturbation theory

Spectral methods 4-6

Motivation: top-K ranking
 Top-K ranking

Goal: identify the set of top-K ranked items

Typical ranking procedure:

• estimate latent scores
• return top-K items in accordance with score estimates

Spectral methods 4-8

 Top-K ranking for BTL model

1. construct a surrogate matrix P obeying

(
1
n yi,j , if i 6= j
Pi,j = P
1− l:l6=i Pi,l , if i = j

2. compute leading left eigenvector π of P as score estimate

3. return K items associated with largest score estimate πi
Spectral methods 4-9
true scorei: ⇤rankscore estimates
true
w : preference
⇤ score ⇤score estimates
⇤ score true ⇤ ⇤
w2w1⇤ wscore score⇤ estimates ⇤ ⇤w
i
wfigure
1 w
credit:
1 w
Opydo
2 3w1 w3w2 wK w2 ww K3 w wK+1
3 wK K
Controlling w w w entrywise
⇤
1 w w zw w
1
⇤
2 2 westimation
}| ⇤
3 w3 {
w ⇤
K z Kerror
z }|
}|
⇤
K+1 { {
K+1

true score score i: rank wi⇤ : preference

estimates score |{z}
true score
true
score estimates
score
i: rank
figure credit: score
Opydo
K
estimates
wi⇤ : preference score
z figure
}| credit:
{ Opydo
1 ⇡⇡2?2? ⇡score
?? ?? ? ? ??? ?⇤ ? 1 ? ⇤?
⇡31?3?⇡1?score w⇡⇤2K+1w2 w⇤ 3⇤ w3 ⇤wK ⇤ ⇤
i: rank
i: rank wiw
K
figure
<
credit:
: ⇤⇡
⇤ ⇡
preference
i1:1 preference
K K
2Opydo
Opydo
··· ⇡⇡K ⇡2⇡3 ⇡⇡⇡3K+1
2K
K K+1
⇡wK1⇡Kw1 ⇡K+1
<z }| · · · {
2 w1K w1 w2 w2 w3 w3 wK z wK ⇤
}| wK+1
w
wK wK+1 { wK+1
⇤ K+1
figure credit:
⇤ ⇤
⇡⇡11 ⇡⇤⇡22 ⇤⇡⇡313⇡⇤1⇡⇡⇡K 2K⇡true
2⇡3 ⇡ ⇡3K+1K⇡K
⇡K+1
⇤score
⇡K+1
⇤score
⇡estimates
K+1 |{z}
true scores score estimates
ww1 1 w1w1w2 ww ww3 w w 3 ⇤ wK wwtruew ⇤score w score
⇤
estimates
? ? 2⇡
2
??? ⇡2⇡ ??? ⇡3⇡
? ?? w ?? K
3 ? K+1
K w wK
? K ? K+1 +1 wK +1
⇡ ??
⇡ ⇡ ⇡ ⇡ ⇡ ⇡ ⇡ ?⇡?
⇡ ⇡ ⇡ ⇡ ⇡
true score 1 1 estimates
score 22
true score score estimates
1
33 1 1
KK2 2 3 K+13 K
K+1 K K+1
true scores score estimates
K+1
z }| z { }| {
K ⇡< ⇡2⇡2 ⇡
⇡1 2 ·1}|2K· ·⇡⇡2K3}|{⇡K+1
K⇡3⇡z13 ⇡⇡⇡K
⇡ ⇡3K<
⇡⇡K+1 ⇡ 1⇡K+1
{K
⇡ ··· |{z} |{z}
1 z |{z} KK+1
2 |{z}
1 1
K
K
K < 2 K
K < 2 K

exact top-K ranking

2kπ − π ? k∞ < ∆K := π(K)

? ?
− π(K+1)

`∞ eigenvector perturbation theory

Spectral methods 4-10
 Leave-one-out analysis : an illustrative example
| {z }
from random matrix theory, stat. physics, etc
 Setup and algorithm

• Ground truth: M ? = λ? u? u?> ∈ Rn×n , with λ? > 0

p
◦ ku? k2 = 1, ku? k∞ = µ/n (µ: incoherence parameter)
• Observation: M = M? +E
◦ E: symmetric, entries in upper triangular part are i.i.d. N (0, σ 2 )
• Estimate u? using leading eigenvector u of M

Question: can we characterize entrywise estimation error of u, i.e.


dist∞ u, u? := min ku − u? k∞ , ku + u? k∞

Spectral methods 4-12

 `2 guarantees

Davis-Kahan’s sin Θ theorem together with Theorem 3.9 gives

√
2kEk 10σ n
dist(u, u ) ≤
?
≤
λ? λ?
√
√ 1−1/ 2 ?
with high prob., as long as σ n ≤ 5 λ

• as an immediate (but very crude) consequence

√
σ n
dist∞ (u, u ) ≤ dist(u, u ) . ?
? ?
(4.15)
λ

Spectral methods 4-13

 `∞ guarantees for matrix denoising

Theorem 4.14
√
Suppose that σ n ≤ c0 λ? for some sufficiently small constant
c0 > 0. Then with high prob.,
√ √
?
σ( log n + µ)
dist∞ u, u .
λ?

• When µ . log n (i.e. energy of u? is spread out):

√
?
σ log n
dist∞ u, u .
λ?
p
• Much sharper (i.e. n/ log n times better) than (4.15)

Spectral methods 4-14

 Technical hurdle: statistical dependency

Let’s take close inspection of l-th entry ul of u:

• Given that u is an eigenvector of M , we have

M u = λu,
1 1
=⇒ ul = [M ]l,: u = [M ? + E]l,: u
λ λ
• challenge: u is statistically dependent on E (in a complicated
way)!

How to decouple complicated dependency between u and E?

Spectral methods 4-15

Decomposition w/ the aid of an independent proxy

Suppose we have access to a proxy u(l) independent of El,: , then

El,: u = El,: u(l) + El,: u − u(l)
| {z } | {z } | {z }
a term of interest =: J1 =: J2

• J1 : controllable using independence btw u(l) & El,:

• J2 : small if u(l) ≈ u

How to construct a useful proxy?

Spectral methods 4-16

 Leave-one-out auxiliary estimates
For each 1 ≤ l ≤ n, construct an auxiliary matrix M (l)

M (l) := λ? u? u?> + E (l) ,

where the noise matrix E (l) is generated according to

(
(l) Ei,j , if i 6= l and j 6= l
Ei,j := (removing l-th row/col)
0, else . ..
. .... ...... ······ ·· · nnnn
1 2 3 11411 22l22 33..33 44·4·4·ll lln
1 2. 3 4 l .. · · · n .
.
l . ··· n
1 2 3 4 as 1 2 3 4 l .. · · ·
.
as 1 2 3 4 l .. · · · n
..
M M (l) leave one row/column out

n
1 2 3 4 l . ··· n
M M (l) leave one row/column out

. ···
..
1 2 3 4 l . ··· n

3 14 2l 3.. 4· · ·l n
..
. .
2 3 4 l .. ··· n 1 2 3 4 l .. ··· n
as 1 2 3 4 l
..
. ··· n

.
M M (l) M M (l)
Spectral methods 4-17
 Leave-one-out auxiliary estimates
For each 1 ≤ l ≤ n, construct an auxiliary matrix M (l)

M (l) := λ? u? u?> + E (l) ,

where the noise matrix E (l) is generated according to

(
(l) Ei,j , if i 6= l and j 6= l
Ei,j := (removing l-th row/col)
0, else

leave-one-out estimates: u(l) (resp. λ(l) ) is leading eigenvalue

(resp. eigenvector) of M (l)
• key property: u(l) is independent of El,:

Spectral methods 4-17

 Intuition

WLOG, suppose u> u? > 0 and u(l)> u? > 0 . . .

• proximity of u(l) and u: since u(l) is obtained by dropping only

a tiny fraction of data, we expect u ≈ u(l)
(l)
• proximity of ul and u?l : by construction,

(l) 1 (l) (l) 1 ? (l) λ? ? ?> (l)

ul = M u = M u = u u u
λ(l) l,·
λ(l) l,·
λ(l) l
≈ u?l

Spectral methods 4-18

Proof of Theorem 4.14
 What we have learned from `2 analysis

√ √
kEk ≤ 5σ n kE (l) k ≤ kEk ≤ 5σ n
√ √
10σ n (l) 10σ n
dist(u, u ) ≤
?
dist(u , u ) ≤
?
λ? λ?
√ (l) √
|λ − λ | ≤ 5σ n
?
|λ − λ | ≤ 5σ n
?
√ √
max |λj (M )| ≤ 5σ n max |λj (M (l) )| ≤ 5σ n
j:j≥2 j:j≥2

Spectral methods 4-20

 Addressing ambiguity

WLOG, assume

ku − u? k2 = dist(u, u? ),
u(l) − u? 2
= dist(u(l) , u? ), 1≤l≤n

√
A useful byproduct: if c0 σ n < λ? for some small constant c0 > 0,
then one necessarily has (exercise)


u − u(l) 2
= dist u, u(l) , 1≤l≤n

Spectral methods 4-21

 Key steps

To bound ul − u?l (1 ≤ l ≤ n), we see from triangle inequality that

(l) (l)
ul − u?l ≤ ul − u?l + u − u(l) ∞
≤ ul − u?l + u − u(l) 2

Spectral methods 4-22

 Key steps

To bound ul − u?l (1 ≤ l ≤ n), we see from triangle inequality that

(l) (l)
ul − u?l ≤ ul − u?l + u − u(l) ∞
≤ ul − u?l + u − u(l) 2

• control u − u(l) 2
(Davis-Kahan)
(l) (l)
• control ul − u?l (ul is independent from El,: )

Spectral methods 4-22

 Bounding proximity ku − u(l) k2

Key: view M as perturbation of M (l) , apply Davis-Kahan

(l) 2k M − M (l) u(l) k2 4k M − M (l) u(l) k2
u−u 2
≤ (l)
≤
λ − max λj M (l) λ?
j≥2

as long as
√ 

kM − M (l) k ≤ (1 − 1/ 2) λ(l) − max λj M (l) ,
j≥2
(l) (l)

λ − max λj M ≥ λ /2?
j≥2

Spectral methods 4-23

 Bounding k(M − M (l) )u(l) k2

By design,

(l)
M − M (l) u(l) = el El,· u(l) + ul (E·,l − El,l el ),

which together with triangle inequality yields

(l)
k M − M (l) u(l) k2 ≤ El,· u(l) + E·,l 2
· ul
| {z }
El,· and u(l) are independent
p

≤ 5σ log n + E·,l 2 ul + u − u(l) ∞
p √ √
≤ 5σ log n + 5σ nkuk∞ + 5σ n u − u(l) 2

Spectral methods 4-24

 Bounding ku − u(l) k2 (cont.)

Combining previous bounds, we arrive at

√ √ √
(l) 20σ log n + 20σ nkuk∞ + 20σ n u − u(l) 2
u−u 2 ≤
√ √ λ?
20σ log n + 20σ nkuk∞ 1
≤ + u − u(l) 2
λ? 2
√
provided that 40σ n ≤ λ?

Rearranging terms and taking union bound give: with high prob.
√ √
(l) 40σ log n + 40σ nkuk∞
u−u 2 ≤ 1≤l≤n
λ?

Spectral methods 4-25

 Analyzing leave-one-out iterates

Recall that
(l) 1 (l) (l) 1 ? (l) λ? ? ?> (l)
ul = M u = M u = u u u
λ(l) l,· λ(l) l,· λ(l) l
This implies
 λ? 
(l)
ul − u?l = u?l (l)
u?> u(l) − u?> u?
λ
 λ? − λ(l) 

= u?l u?> u(l) + u?l u?> u(l) − u?
λ(l)

Spectral methods 4-26

 Analyzing leave-one-out iterates (cont.)

Triangle inequality gives

(l) λ? − λ(l)
ul − u?l ≤ u?l · (l)
· ku? k2 · ku(l) k2
λ
+ u?l · ku? k2 · u(l) − u? 2
√ √
10σ n 10σ n
?
≤ ul · ?
+ ul ·
?

√ λ λ?
20σ n ?
≤ u ∞
λ?

Spectral methods 4-27

 Putting all pieces together
Now we come to conclude that
n o
(l)
u − u? ∞
= max ul − u?l ≤ max ul − u?l + u − u(l) 2
l l
√ √ √
20σ n ? 40σ log n + 40σ nkuk∞
≤ u ∞
+
λ? λ?
One more triangle inequality gives
√ √
40σ log n + 60σ n ku? k∞ 1
?
u−u ∞ ≤ + u − u? ∞
λ? 2
√
provided that 80σ n ≤ λ? . Rearranging terms yields
√ √ √ √
80σ log n + 120σ n ku? k∞ 80σ log n + 120σ µ
?
u−u ∞ ≤ =
λ? | {zλ
?
}
from definition of µ

Spectral methods 4-28

`∞ eigenvector perturbation theory (rank-1)
 Setup and algorithm

• Ground truth: M ? = λ? u? u?> ∈ Rn×n , with λ? > 0

p
◦ ku? k2 = 1, ku? k∞ = µ/n (µ: incoherence parameter)
• Observation: M = M? + E with symmetric E
• Estimate u? using leading eigenvector u of M

Question: can we accommodate more general noise distributions

beyond Gaussian?

Spectral methods 4-30

 Noise assumptions

Entries in lower triangular part of E = [Ei,j ]1≤i,j≤n are independently

generated obeying
2
E[Ei,j ] = 0, E[Ei,j ] ≤ σ2, |Ei,j | ≤ B, for all i ≥ j

Further, assume that

B
cb := p = O(1)
σ n/(µ log n)

• in general, B is allowed to be significantly larger than σ

Spectral methods 4-31

 `∞ perturbation theory

Theorem 4.15
With high prob, there exists z ∈ {1, −1} such that
√ √
σ µ + σ log n
zu − u ∞ .
?
(4.18a)
λ? q
√ √ 3
1 σ µ σ 2 n log n + σB µ log n
zu − ? M u ?
. ? + (4.18b)
λ ∞ λ (λ? )2
√
provided σ n log n ≤ cσ λ? for some small enough constant cσ > 0

√
• estimation error is delocalized (recall that dist(u, u? ) . σ n)

Spectral methods 4-32

 First-order expansion

Theorem 4.15 reveals tightness of first-order approximation

Mu M u? M ? u?
u= ≈ ≈ = u?
λ λ? λ?

• (4.18b) often leads to tighter approximation than (4.18a)

• important in certain applications such as SBM

Spectral methods 4-33

Application: exact recovery in community detection
 Exact recovery using spectral methods

Consider the case where

α log n β log n
p= , q=
n n

Theorem 4.16
Fix any constant ε > 0. Suppose α > β > 0 are large enougha and
√ p
2
α − β ≥ 2 (1 + ε)

With probability 1 − o(1), spectral method achieves exact recovery

a
this assumption can be removed

Spectral methods 4-35

 Optimality of spectral method

Lower bound: if
√ p
2
α− β ≤ 2 (1 − ε) (4.19)

for any constant ε > 0, then no method can achieve exact recovery

• taking this w/ Theorem 4.16 reveals information-theoretic

optimality of spectral method

√ √
2 √ √
2
What is the operational meaning of α− β or p− q ?

Spectral methods 4-36

 Squared Hellinger distance

Definition 4.17
Consider two distributions P and Q over a finite alphabet Y. The
squared Hellinger distance H2 (P, Q) between P and Q is
1X q q 2
H2 (P, Q) := P (y) − Q(y)
2 y∈Y

• squared Hellinger distance between Bern(p) and Bern(q):

1 √ √
2 1 p p
2
H2 Bern(p), Bern(q) := p− q + 1−p− 1−q
2 2

1 √ √
2
= 1 + o(1) p− q
2
when p = o(1) and q = o(1)
Spectral methods 4-37
 Optimality of spectral method (cont.)

Theorem 4.16 and lower bound (4.19) reveal sharp phase transition:

log n
spectral method works if H2 Bern(p), Bern(q) ≥ (1 + ε)
n
2
log n
no algorithm works if H Bern(p), Bern(q) ≤ (1 − ε)
n
for arbitrarily small constant ε > 0

Spectral methods 4-38

 Fine-grained analysis of spectral clustering

WLOG, assume x?1 = . . . = x?n/2 = 1 and x?n/2+1 = . . . = x?n = −1,

and recall that
p + q > p − q ? ?>
M ? := E[A] − 11 = x x
2 2

These imply

λ? = n(p−q)
2 , µ = 1,
B = 1, σ 2 ≤ max{p, q} = p

Spectral methods 4-39

 Applying `∞ perturbation theory

`∞ perturbation bound (4.18b) yields: for some constant C > 0,

√
σ 2 n log n σB log3/2 n
?
zλ u − M u ?
∞
.σ+ +
λ? λ?
√ √
√ p log n p log3/2 n 
≤C p+ √ + =: ∆
n(p − q) n(p − q)
(4.20)

It boils down to characterizing entrywise behavior of M u?

√ √
— what happens at phase transition point ( α − β)2 = 2?

Spectral methods 4-40

 Bounding entries in M u?

Lemma 4.18
√ √
2
Suppose that α − β ≥ 2 (1 + ε) for some constant ε > 0.
Then with prob. 1 − o(1),

η log n n η log n n
Ml,· u? ≥ √ for all l ≤ , Ml,· u? ≤ − √ for all l >
n 2 n 2
√ √
where η > 0 obeys ( α − β)2 − η log(α/β) > 2

key message: √entries of M u? are bounded away from 0 with correct

√
signs if ( α − β)2 > 2

Spectral methods 4-41

 Completing the picture

Combine Lemma 4.18 with (4.20) leads to a claim: if

η log n
√ >∆ (4.21)
n

then it follows that

zul u?l > 0 for all 1 ≤ l ≤ n =⇒ exact recovery

Spectral methods 4-42

 Proof of relation (4.21)

Lemma 4.18 and (4.20) tell us that: it suffices to show

√ √
η log n √ p log n p log3/2 n 
√ ≥C p+ √ +
n n(p − q) n(p − q)

q
√ log n log n
• 1st term: p n  η√
n
√ q
p log n log n log n
• 2nd term: √
n(p−q)
 n  η√
n
• 3rd term: divide discussion into two cases α/β ≤ 2, and α/β ≥ 2

Spectral methods 4-43

 Comparing two sets of Bernoulli r.v.s

Lemma 4.19
Suppose α > β, {Wi }1≤i≤n/2 are i.i.d. Bern( α log
n ), and {Zi }1≤i≤n/2
n

are i.i.d. Bern( β log

n ), which are independent of Wi . For any t > 0,
n

 
Xn/2 n/2
X √ √ 2
P  Wi − Zi ≤ t log n ≤ n−( α− β) /2+t log(α/β)/2
i=1 i=1

Spectral methods 4-44

 Comparing two sets of Bernoulli r.v.s

Lemma 4.19
Suppose α > β, {Wi }1≤i≤n/2 are i.i.d. Bern( α log
n ), and {Zi }1≤i≤n/2
n

are i.i.d. Bern( β log

n ), which are independent of Wi . For any t > 0,
n

 
Xn/2 n/2
X √ √ 2
P  Wi − Zi ≤ t log n ≤ n−( α− β) /2+t log(α/β)/2
i=1 i=1

• roughly speaking,
 
Xn/2 n/2
X √ √ 2
P  Wi − Zi ≤ 0 ≤ n−( α− β) /2
i=1 i=1

Spectral methods 4-44

 Comparing two sets of Bernoulli r.v.s

Lemma 4.19
Suppose α > β, {Wi }1≤i≤n/2 are i.i.d. Bern( α log
n ), and {Zi }1≤i≤n/2
n

are i.i.d. Bern( β log

n ), which are independent of Wi . For any t > 0,
n

 
Xn/2 n/2
X √ √ 2
P  Wi − Zi ≤ t log n ≤ n−( α− β) /2+t log(α/β)/2
i=1 i=1

√ √ Pn/2 Pn/2

• ( α − β)2 > 2 guarantees P i=1 Wi − i=1 Zi ≤ 0 < n
−1

◦ probability of error o(n−1 ) is crucial, since in M u? we have n

independent groups of {Wi } and {Zi } (need union bound)

Spectral methods 4-44

 Proof of Lemma 4.18

Note that M u? = (A − 2 11 )u
p+q > ? = Au? . Hence
 
n/2
1 X Xn
M1,: u? = A1,: u? = √  A1,j − A1,j 
n j=1 j=n/2+1

Apply Lemma
√ √ 2
4.19 to obtain with probability at least
1−n −( a− b) /2+η log(a/b)/2 = 1 − o(n−1 )

η log n
M1,: u? ≥ √
n

Invoke union bound to complete proof

Spectral methods 4-45

 Proof of Lemma 4.19
We apply the Laplace transform method: for any λ < 0
 
n/2 n/2
X X
P  Wi − Zi ≤ t log n
i=1 i=1

   
n/2 n/2
X X
= P exp λ  Wi − Zi  ≥ exp (λt log n)
i=1 i=1
h  P Pn/2 i
E exp λ
n/2
i=1 Wi − i=1 Zi
≤
exp (λt log n)
By independence, one has
   
n/2 n/2 n/2
X X Y
E exp λ
   Wi − Zi  = E [exp (λWi )] E [exp (−λZi )]
i=1 i=1 i=1

Spectral methods 4-46

 Proof of Lemma 4.19 (cont.)
By definition and using 1 + x ≤ ex , one has
 
α log n α log n
E [exp (λWi )] = exp (λ) + 1 −
n n
 
α log n α log n
≤ exp exp (λ) −
n n
Similarly, for Zi one has
 
β log n β log n
E [exp (−λWi )] ≤ exp exp (−λ) −
n n
Combine these two to see that

E [exp (λWi )] E [exp (−λZi )]

 
log n
≤ exp (α exp (λ) + β exp (−λ) − α − β)
n
Spectral methods 4-47
 Proof of Lemma 4.19 (cont.)

Combine previous two pages to see

 
n/2 n/2
X X
log P  Wi − Zi ≤ t log n
i=1 i=1
n log n

≤ −λt log n + α exp (λ) + β exp (−λ) − α − β
2 n
Set λ = − log (α/β) /2 to obtain
s
r
β α √ p
2
α exp (λ)+β exp (−λ)−α−β = α +β −α−β = − α− β
α β

thus concluding the proof

Spectral methods 4-48

`2,∞ eigen-space perturbation theory (rank-r)
 Setup and algorithm
• Ground truth: M ? = U ? Σ? V ?> ∈ Rn1 ×n2 , with singular values
σ1? ≥ σ2? ≥ · · · ≥ σr? > 0 (assume n1 ≤ n2 )
• Observation: M = M ? + E
• Convenient notation:
σ1?
κ := , n := n1 + n2
σr?
• Estimate U ? (resp. V ? ) using rank-r leading left (resp. right)
singular subspace U (resp. V ) of M

Question: can we characterize entrywise estimation error of U , i.e.

dist2,∞ U , U ? := min kU R − U ? k2,∞
R∈Or×r

Spectral methods 4-50

 Assumptions
Noise assumptions: entries of E = [Ei,j ]1≤i≤n1 ,1≤j≤n2 are
independent obeying
2
E[Ei,j ] = 0, E[Ei,j ] ≤ σ2, |Ei,j | ≤ B, for all i, j

and it is assumed that

B
cb := p = O(1)
σ n1 /(µ log n)

Spectral methods 4-51

 Assumptions
Noise assumptions: entries of E = [Ei,j ]1≤i≤n1 ,1≤j≤n2 are
independent obeying
2
E[Ei,j ] = 0, E[Ei,j ] ≤ σ2, |Ei,j | ≤ B, for all i, j

and it is assumed that

B
cb := p = O(1)
σ n1 /(µ log n)

Incoherence parameter of orthonormal matrix U ? ∈ Rn×r is

nkU ? k22,∞
µ(U ? ) :=
r
and for M ? = U ? Σ? V ?> we define µ := max{µ(U ? ), µ(V ? )}
Spectral methods 4-51
 `2,∞ distance between U and U ?

Need to take into account rotational ambiguity

— which rotation matrix to use?

Spectral methods 4-52

 `2,∞ distance between U and U ?

Need to take into account rotational ambiguity

— which rotation matrix to use?

Definition 4.20
For any square matrix Z with SVD Z = UZ ΣZ VZ> , define

sgn(Z) := UZ VZ> (4.22)

to be matrix sign function of Z (solution to Procrustes problem)

Let us employ sgn(U > U ? ) and look at

kU sgn(U > U ? ) − U ? k2,∞

Spectral methods 4-52

 `2,∞ eigen-space perturbation theory

Theorem 4.21
With probability at least 1 − O(n−5 ), one has
n o
max kU sgn(U > U ? ) − U ? k2,∞ , kV sgn(V > V ? ) − V ? k2,∞
√ q √

σ r κ nn21 µ + log n
.
σr?
√
provided that σ n log n ≤ c1 σr? for some small constant c1 > 0

Spectral methods 4-53

 Entrywise matrix reconstruction error

Recall M = |U ΣV
{z } + U⊥ Σ⊥ V⊥
> >

rank r approx.

Corollary 4.22
√
In addition, if σκ n log n ≤ c2 σr? for some small enough constant
c2 > 0, then the following holds with probability at least 1 − O(n−5 ):
s
2 (n2 /n1 ) log n
kU ΣV >
− M k∞ . σκ µr
?
n1

Spectral methods 4-54

 De-localization of estimation error

For simplicity, let us consider the case where µ, κ, n2 /n1 = O(1).

Davis-Kahan theorem results in the following `2 estimation guarantees
√
√ σ nr
distF (U , U ) ≤ r dist(U , U ) .
? ?
σr?

In comparison, the `2,∞ bound derived in Theorem 4.21 simplifies to

√
σ r log n
min U R − U 2,∞ ≤ U sgn(U U ) − U 2,∞ .
? > ? ?
R ∈Or×r σr?

Spectral methods 4-55

 De-localization of estimation error (cont.)

For the matrix reconstruction error, one has

√
kU ΣV > − M ? k ≤ 2kM − M ? k . σ n,
√
which implies kU ΣV > − M ? kF . σ nr

In comparison, one has

s
log n
kU ΣV >
− M k∞ . σr
?
n

Spectral methods 4-56

Concluding remarks
 Concluding remarks: spectral methods

• A powerful family that permeates data science applications

◦ community detection
◦ matrix/tensor completion
◦ ranking
◦ phase retrieval
◦ (joint) graph matching
◦ robust PCA
◦ clustering in mixture models
◦ ...

• Simple yet efficient; sometimes optimal (in some weak sense)

• Commonly used to initialize nonconvex optimization algorithms

— see overview article Chi, Lu, Chen ’19

Spectral methods 5-2

 Concluding remarks: leave-one-out analysis

A power fine-grained analysis framework that proves effective for

problems far beyond spectral methods

• robust M-estimation (e.g. El Karoui et al. ’13, El Karoui ’18)

• generalized power methods (e.g. Zhong, Boumal ’18)
• likelihood ratio test in logistic regression (e.g. Sur et al. ’19)
• nonconvex optimization (e.g. Ma et al. ’20, Chen et al. ’19, Cai
et al. ’22)
• convex relaxation (e.g. Chen et al. ’19, ’20, ’21)
• reinforcement learning (e.g. Agarwal et al. ’19, Pananjady et
al. ’20, Li et al. ’23)
• ...
Spectral methods 5-3
 References: general

• “Spectral methods for data science: A statistical perspective,”

Y. Chen, Y. Chi, J. Fan, C. Ma, Foundations and Trends in Machine
Learning, 2021.
• “Inference, estimation, and information processing, EE 378B lecture
notes,” A. Montanari, Stanford University.
• “COMS 4772 lecture notes,” D. Hsu, Columbia University.
• “Spectral algorithms,” R. Kannan, S. Vempala, Foundations and
Trends in Theoretical Computer Science, 2009.
• “Principal component analysis for big data,” J. Fan, Q. Sun, W. Zhou,
Z. Zhu, arXiv:1801.01602, 2018.
• “Nonconvex optimization meets low-rank matrix factorization: An
overview,” Y. Chi, Y. M. Lu, Y. Chen, IEEE Transactions on Signal
Processing, 2019.

Spectral methods 5-4

 References: matrix perturbation theory

• “The rotation of eigenvectors by a perturbation,” C. Davis, W. Kahan,

SIAM Journal on Numerical Analysis, 1970.
• “Perturbation bounds in connection with singular value
decomposition,” P. Wedin, BIT Numerical Mathematics, 1972.
• “Matrix perturbation theory,” G. W. Stewart, J. Sun, 1990.
• “A useful variant of the Davis-Kahan theorem for statisticians,” Y. Yu,
T. Wang, R. J. Samworth, Biometrika, vol. 102, no. 2, pp. 315-323,
2015.
• “Spectral method and regularized MLE are both optimal for top-K
ranking,” Y. Chen, J. Fan, C. Ma, K. Wang, Annals of Statistics, 2019.

Spectral methods 5-5

 References: matrix tail bounds

• “An introduction to matrix concentration inequalities,” J. Tropp,

Foundations and Trends in Machine Learning, 2015.
• “Sharp nonasymptotic bounds on the norm of random matrices with
independent entries,” A. S. Bandeira, R. van Handel, Annals of
Probability, 2016.
• “High-dimensional probability: An introduction with applications in
data science,” R. Vershynin, 2018.
• “High-dimensional statistics: a non-asymptotic viewpoint,”
M. Wainwright, Cambridge University Press, 2019.

Spectral methods 5-6

 References: applications

• “Community detection and stochastic block models,” E. Abbe,

Foundations and Trends in Communications and Information Theory,
2018.
• “Consistency thresholds for the planted bisection model,” E. Mossel,
J. Neeman, A. Sly, ACM Symposium on Theory of Computing, 2015.
• “Exact recovery in the stochastic block model,” E. Abbe,
A. S. Bandeira, G. Hall, IEEE Transactions on information theory,
vol. 62, no. 1, pp. 471-487, 2015.
• “Exact matrix completion via convex optimization,” E. Candes,
B. Recht, Foundations of Computational Mathematics, 2019.
• “Matrix completion from a few entries,” R. Keshavan, A. Montanari,
S. Oh, IEEE Transactions on Information Theory, 2010.
• “Low-rank matrix completion using alternating minimization,” P. Jain,
P. Netrapalli, S. Sanghavi, Symposium on Theory of computing, 2013.
Spectral methods 5-7
 References: applications

• “Implicit regularization in nonconvex statistical estimation: Gradient

descent converges linearly for phase retrieval and matrix completion,”
C. Ma, K. Wang, Y. Chi, Y. Chen, Foundations of Computational
Mathematics, 2020.
• “Inference and uncertainty quantification for noisy matrix completion,”
Y. Chen, J. Fan, C. Ma, Y. Yan, Proceedings of the National Academy
of Sciences, vol. 116, no. 46, pp. 22931-22937, 2019.
• “Spectral algorithms for tensor completion,” A. Montanari, N. Sun,
Communications on Pure and Applied Mathematics, vol. 71, no. 11,
pp. 2381-2425, 2018.
• “Nonconvex low-rank tensor completion from noisy data,” C. Cai,
G. Li, H. V. Poor, Y. Chen, Operations Research, vol. 70, no. 2, 2022.
• “The PageRank citation ranking: bringing order to the web,” L. Page,
S. Brin, R. Motwani, T. Winograd, 1999.

Spectral methods 5-8

 References: applications

• “Rank centrality: ranking from pairwise comparisons,” S. Negahban,

S. Oh, D. Shah, Operations Research, 2017.
• “Heteroskedastic PCA: Algorithm, optimality, and applications,”
A. Zhang, T. Cai, Y. Wu, Annals of Statistics, 2022.
• “Normal approximation and confidence region of singular subspaces,”
D. Xia, Electronic Journal of Statistics, vol. 15, no. 2, pp. 3798-3851.
• “Phase retrieval via Wirtinger flow: Theory and algorithms,”
E. J. Candes, X. Li, M. Soltanolkotabi, IEEE Transactions on
Information Theory, vol. 61, no. 4, pp. 1985-2007, 2015.
• “Solving random quadratic systems of equations is nearly as easy as
solving linear systems,” Y. Chen, E. J. Candes, Communications on
pure and applied mathematics, vol. 70, no. 5, pp. 822-883, 2017.

Spectral methods 5-9

 References: applications

• “Rate-optimal perturbation bounds for singular subspaces with

applications to high-dimensional statistics,” T. Cai, A. Zhang, Annals
of Statistics, vol. 46, no. 1, pp. 60-89, 2018.
• “Optimality of spectral clustering in the Gaussian mixture model,”
M. Loffler, A. Y. Zhang, H. H. Zhou, Annals of Statistics, vol. 49,
no. 5, pp. 2506-2530, 2021.
• “Angular synchronization by eigenvectors and semidefinite
programming,” A. Singer, Applied and computational harmonic
analysis, vol. 30, no. 1, pp. 20-36, 2011.

Spectral methods 5-10

 References: `∞ and `2,∞ theory

• “Near-optimal bounds for phase synchronization,” Y. Zhong,

N. Boumal, SIAM Journal on Optimization, 2018.
• “Entrywise eigenvector analysis of random matrices with low expected
rank,” E. Abbe, J. Fan, K. Wang, Y. Zhong, Annals of Statistics, 2020.
• “Spectral method and regularized MLE are both optimal for top-K
ranking,” Y. Chen, J. Fan, C. Ma, K. Wang, Annals of Statistics, 2019.
• “The two-to-infinity norm and singular subspace geometry with
applications to high-dimensional statistics,” J. Cape, M. Tang,
C. E. Priebe, Annals of Statistics, vol. 47, no. 5, pp. 2405-2439, 2019.
• “Implicit regularization in nonconvex statistical estimation: Gradient
descent converges linearly for phase retrieval and matrix completion,”
C. Ma, K. Wang, Y. Chi, Y. Chen, Foundations of Computational
Mathematics, 2020.

Spectral methods 5-11

 References: `∞ and `2,∞ theory

• “Subspace estimation from unbalanced and incomplete data matrices:

`2,∞ statistical guarantees,” C. Cai, G. Li, Y. Chi, H. V. Poor, Y. Chen,
vol. 49, no. 2, 2021.
• “Unified `2→∞ eigenspace perturbation theory for symmetric random
matrices,” L. Lei, arXiv:1909.04798, 2019.
• “SIMPLE: Statistical inference on membership profiles in large
networks,” J. Fan, Y. Fan, X. Han, J. Lv, Journal of the Royal
Statistical Society Series B: Statistical Methodology, vol. 84, no. 2,
pp. 630-653, 2022.
• “Entrywise Estimation of Singular Vectors of Low-Rank Matrices with
Heteroskedasticity and Dependence,” J. Agterberg, Z. Lubberts,
C. Priebe, IEEE Transactions on Information Theory, vol. 68, no. 7,
pp. 4618-4650, 2022.

Spectral methods 5-12

 References: `∞ and `2,∞ theory

• “Partial recovery for top-K ranking: optimality of MLE and

suboptimality of the spectral method,” P. Chen, C. Gao, and
A. Y. Zhang, Annals of Statistics, vol. 50, no. 3, pp. 1618-1652, 2022.
• “Uncertainty quantification in the Bradley-Terry-Luce model,” C. Gao,
Y. Shen, A. Y. Zhang, Information and Inference: A Journal of the
IMA, vol. 12, no. 2, pp. 1073-1140, 2023.
• “Inference for heteroskedastic PCA with missing data,” Y. Yan,
Y. Chen, J. Fan, arXiv:2107.12365, 2021.

Spectral methods 5-13

References: leave-one-out analysis (other methods)

• “On robust regression with high-dimensional predictors,” N. El Karoui,

D. Bean, P. J. Bickel, C. Lim, B. Yu, Proceedings of the National
Academy of Sciences, vol. 110, no. 36, pp. 14557-14562, 2013.
• “On the impact of predictor geometry on the performance on
high-dimensional ridge-regularized generalized robust regression
estimators,” N. El Karoui, Probability Theory and Related Fields,
vol. 170, pp. 95-175, 2018.
• “Near-optimal bounds for phase synchronization,” Y. Zhong,
N. Boumal, SIAM Journal on Optimization, 2018.
• “The likelihood ratio test in high-dimensional logistic regression is
asymptotically a rescaled chi-square,” P. Sur, Y. Chen, E. Candes,
Probability theory and related fields, vol. 175, pp. 487-558, 2019.

Spectral methods 5-14

References: leave-one-out analysis (other methods)

• “Implicit regularization in nonconvex statistical estimation: Gradient

descent converges linearly for phase retrieval and matrix completion,”
C. Ma, K. Wang, Y. Chi, Y. Chen, Foundations of Computational
Mathematics, 2020.
• “Gradient descent with random initialization: Fast global convergence
for nonconvex phase retrieval,” Y. Chen, Y. Chi, J. Fan, C. Ma,
Mathematical Programming, vol. 176, pp. 5-37, 2019.
• “Nonconvex low-rank tensor completion from noisy data,” C. Cai,
G. Li, H. V. Poor, Y. Chen, Operations Research, vol. 70, no. 2, 2022.
• “Nonconvex rectangular matrix completion via gradient descent
without `2,∞ regularization,” J. Chen, D. Liu, X. Li, IEEE Transactions
on Information Theory, vol. 66, no. 9, pp. 5806-5841, 2020.

Spectral methods 5-15

References: leave-one-out analysis (other methods)

• “Inference and uncertainty quantification for noisy matrix completion,”

Y. Chen, J. Fan, C. Ma, Y. Yan, Proceedings of the National Academy
of Sciences, vol. 116, no. 46, pp. 22931-22937, 2019.
• “Noisy matrix completion: Understanding statistical guarantees for
convex relaxation via nonconvex optimization,” Y. Chen, Y. Chi,
J. Fan, C. Ma, Y. Yan, SIAM journal on optimization, vol. 30, no. 4,
pp. 3098-3121.
• “Bridging convex and nonconvex optimization in robust PCA: Noise,
outliers and missing data,” Y. Chen, J. Fan, C. Ma, Y. Yan, Annals of
Statistics, vol. 49, no. 5, pp. 2948-2971, 2021.
• “Model-based reinforcement learning with a generative model is
minimax optimal,” A. Agarwal, S. Kakade, L. Yang, Conference on
Learning Theory, 2020.

Spectral methods 5-16

References: leave-one-out analysis (other methods)

• “Breaking the sample size barrier in model-based reinforcement

learning with a generative model,” G. Li, Y. Wei, Y. Chi, Y. Chen,
Operations Research, 2023+.
• “Instance-dependent `∞ -bounds for policy evaluation in tabular
reinforcement learning,” A. Pananjady, M. Wainwright, IEEE
Transactions on Information Theory, vol. 67, no. 1, pp. 566-585, 2020.

Spectral methods 5-17