Discovery of Latent Factors in High-dimensional
Data via Spectral Methods
Furong Huang
University of Maryland
Workshop on Quantum Machine Learning

1 / 39

Machine Learning - Excitements

Success of Supervised Learning

Image classification

Speech recognition

Text processing

2 / 39

Machine Learning - Excitements

Success of Supervised Learning

Image classification

Speech recognition

Text processing

Key to Success
Deep composition of nonlinear units
Enormous labeled data
Computation power growth
2 / 39

Machine Learning - Modern Challenges
Automated discovery of features and categories?

Filter bank learning

Feature extraction

Embeddings, Topics

2 / 39

Machine Learning - Modern Challenges
Automated discovery of features and categories?

Real AI requires Unsupervised Learning

Filter bank learning

Feature extraction

Embeddings, Topics

Summarize key features in data◮◮

State-of-the-art: Humans are better than machines
Goal: Intelligent machines that summarize key features in data

Interpretable modeling and learning of the data◮◮

Theoretically guaranteed learning
Extracted features are interpretable2 / 39Unsupervised Learning with Big Data
Curse of Dimensionality
More information → more unknowns/variables → challenging model
learning

3 / 39Unsupervised Learning with Big Data
Information Extraction
High dimension observation vs Low dimension representation

TopicsCell Types
Communities

3 / 39Unsupervised Learning with Big Data
Information Extraction
High dimension observation vs Low dimension representation

TopicsCell Types
Communities

Finding Needle In the Haystack Is Challenging
3 / 39Unsupervised Learning with Big Data
Information Extraction
High dimension observation vs Low dimension representation

TopicsCell Types
Communities

My Solution: A Unified Tensor Decomposition Framework
3 / 39

App 1: Automated Categorization of Documents
Topics
Education

Crime

SportsDocument modeling
Observed: words in document corpus: search logs, emails etc
Hidden: (mixed) topics: personal interests, professional area etc
4 / 39

App 1: Automated Categorization of Documents
Topics
Education

Crime

SportsDocument modeling
Observed: words in document corpus: search logs, emails etc
Hidden: (mixed) topics: personal interests, professional area etc
4 / 39

App 2: Community Extraction From Connectivity Graph

Social Networks
Observed: network of social ties: friendships, transactions etc
Hidden: (mixed) groups/communities of social actors
5 / 39

App 2: Community Extraction From Connectivity Graph

Social Networks
Observed: network of social ties: friendships, transactions etc
Hidden: (mixed) groups/communities of social actors
5 / 39Tensor Methods Compared with Variational Inference
Learning Topics from PubMed on Spark: 8 million docs

10

4

103

TensorVariational

10

Running Time (s)Perplexity

105

×104

8
6
4
2
0

6 / 39Tensor Methods Compared with Variational Inference
Learning Topics from PubMed on Spark: 8 million docs

10

10

TensorVariational

Running Time (s)Perplexity

105

4

103

×104

8
6
4
2
0

Learning Communities from Graph Connectivity
10

Yelp: n ∼ 40k

1

100

10-1

10-2

FB

YP

DBLPsub

DBLP

DBLPsub: n ∼ 0.1m
Running Times (s)Error /group

Facebook: n ∼ 20k

106

DBLP: n ∼ 1m

105

104

103

102

FB

YP

DBLPsub

DBLP

6 / 39Tensor Methods Compared with Variational Inference
Learning Topics from PubMed on Spark: 8 million docs

10

10

TensorVariational

Running Time (s)Perplexity

105

4

103

×104

8
6
4
2
0

re
Mo

ra
cu
c
A

te

&
Learning Communities from Graph Connectivity
ter
10

as

F
Yelp: n ∼ 40k de DBLPsub:n ∼ 0.1m

1

100

r
de
Or

10-1

10-2

FB

YP

f
so

DBLPsub

Ma

it
gn

DBLP

u

Running Times (s)Error /group

Facebook: n ∼ 20k

106

DBLP: n ∼ 1m

105

104

103

102

FB

YP

DBLPsub

DBLP“Online Tensor Methods for Learning Latent Variable Models”, F. Huang, U. Niranjan, M. Hakeem, A. Anandkumar, JMLR14.
“Tensor Methods on Apache Spark”, F. Huang, A. Anandkumar, Oct. 2015.

6 / 39

App 3: Cataloging Neuronal Cell Types In the Brain

Neuroscience
Observed: cellular-resolution brain slices
Hidden: neuronal cell types
7 / 39

App 3: Cataloging Neuronal Cell Types In the Brain
Our method vs Average expression level [Grange 14’]k
2.5

Spatial point process (ours)
Average expression level (previous)

2.0
1.5
1.0
0.5

Recovered known cell types
1 Interneurons

5 Microglia

2 S1Pyramidal

6 Endothelial

3 Astrocytes

7 Mural4 Ependymal

8 Oligodendrocytes“Discovering Neuronal Cell Types and Their Gene Expression Profiles Using a Spatial Point Process Mixture Model”, F. Huang,
A. Anandkumar, C. Borgs, J. Chayes, E. Fraenkel, M. Hawrylycz, E. Lein, A. Ingrosso, S. Turaga, NIPS 2015 BigNeuro workshop.
8 / 39

App 4: Word Sequence Embedding Extractiontree

The weather is good.

Her life spanned years ofincredible change for women.

soccerfootballWord Embedding

Mary lived through an era ofliberating reform for women.

Word Sequence Embedding“Convolutional Dictionary Learning through Tensor Factorization”, by F. Huang, A. Anandkumar, In Proceedings of JMLR 2015.
9 / 39

App 5: Human Disease Hierarchy Discovery
CMS: 1.6 million patients, 168 million diagnostic events, 11 k diseases.

Observed: co-occurrence of diseases on patients
Hidden: disease similarity/hierarchy” Scalable Latent TreeModel and its Application to Health Analytics ” by F. Huang, N. U.Niranjan, I. Perros, R. Chen, J. Sun,
A. Anandkumar, NIPS 2015 MLHC workshop.
10 / 39

Involve discovering the hidden and compact structurethat is embedded in the high-dimensional complex observed data

11 / 39

How to model hidden effects?
Basic Approach: mixtures/clusters
Hidden variable h is categorical.

Advanced: Probabilistic models
Hidden variable h has more general distributions.

h1
h2

h3

Can model mixed memberships.
x1 x2 x3 x4 x5This talk: basic mixture model and some advanced models (topic model)

12 / 39Challenges in Learning
Basic goal in all mentioned applications
Discover hidden structure in data: unsupervised learning.
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

TopicsA

Words
gene data DNA RNA

Latent variable model

Learning Algorithm

Inference

13 / 39Challenges in Learning – find hidden structure in data
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

TopicsA

Words
gene data DNA RNA

Latent variable model

Learning Algorithm

Inference

Challenge: Conditions for Identifiability
Whether can model be identified given infinite computation and data?
Are there tractable algorithms under identifiability?

13 / 39Challenges in Learning – find hidden structure in data
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

TopicsA

Words
gene data DNA RNA

Latent Variable model

MCMC

Inference

Challenge: Conditions for Identifiability
Whether can model be identified given infinite computation and data?
Are there tractable algorithms under identifiability?

Challenge: Efficient Learning of Latent Variable Models
MCMC: random sampling, slow◮

Exponential mixing time

13 / 39Challenges in Learning – find hidden structure in data
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

TopicsA

Words
gene data DNA RNA

Latent variable modelel i tiL Inference

Challenge: Conditions for Identifiability
Whether can model be identified given infinite computation and data?
Are there tractable algorithms under identifiability?

Challenge: Efficient Learning of Latent Variable Models
MCMC: random sampling, slow◮

Exponential mixing time

Likelihood: non-convex, not scalable◮

Exponential critical points

13 / 39Challenges in Learning – find hidden structure in data
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

TopicsA

Words
gene data DNA RNA

Latent variable model



el





Inference

Challenge: Conditions for Identifiability
Whether can model be identified given infinite computation and data?
Are there tractable algorithms under identifiability?

Challenge: Efficient Learning of Latent Variable Models
MCMC: random sampling, slow◮

Exponential mixing time

Likelihood: non-convex, not scalable◮

Exponential critical points

Efficient computational and sample complexities?
13 / 39Challenges in Learning – find hidden structure in data
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

=

Topics

+

+

A

Words
gene data DNA RNA

Latent variable model

ensor Decomposition

T

Inference

Challenge: Conditions for Identifiability
Whether can model be identified given infinite computation and data?
Are there tractable algorithms under identifiability?

Challenge: Efficient Learning of Latent Variable Models
MCMC: random sampling, slow◮

Exponential mixing time

Likelihood: non-convex, not scalable◮

Exponential critical points

Efficient computational and sample complexities?
Guaranteed and efficient learning through spectral methods
13 / 39

Unsupervised Learning via Probabilistic Models
h

k2

k1
A
life

Unlabeled data

Choice Variable

k3

k4

k5

A

A

A

Topics

=

+

+

A

Words
gene data DNA RNA

Latent variable model

Tensor Decomposition

Inference

tensor decomposition → correct model

14 / 39

Unsupervised Learning via Probabilistic Models
h

k2

k1
A
life

Unlabeled data

Contributions

Choice Variable

k3

k4

k5

A

A

A

=

Topics

+

+

A

Words
gene data DNA RNA

Latent variable model

Tensor Decomposition

Inference

tensor decomposition → correct model

Guaranteed online algorithm with global convergence guarantee
Highly scalable, highly parallel, dimensionality reduction
Tensor library on CPU/GPU/SparkInterdisciplinary applications
Extension to model with group invariance

14 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

15 / 39

Method-of-Moments At A Glance
1

Determine function of model parameters θ estimatable fromobservable data:◮

Moments
Eθ [f (X)]2

Form estimates of moments using data (iid samples {xi }ni=1 ):◮3

Empirical Momentsb (X)]
E[fSolve the approximate equations for parameters θ:◮

Moment matchingEθ [f (X)]n→∞=b (X)]
E[fToy Example
How to estimate Gaussian variable, i.e., (µ,Σ),given iid samples {xi }ni=1 ∼ N (µ, Σ2 )?
16 / 39

What is a tensor?
Multi-dimensional Array
Tensor - Higher order matrix
The number of dimensions is called tensor order.

17 / 39

Slices

Horizontal slices

Lateral slices

Frontal slices

18 / 39

Tensor Product[a ⊗ b]i1 ,i2

bi2
a i1

=
[a ⊗ b]i1 ,i2 = ai1 bi2
Rank-1 matrix[a ⊗ b ⊗ c]i1 ,i2 ,i3
c i3

bi2

= a i1[a ⊗ b ⊗ c]i1 ,i2 ,i3 = ai1 bi2 ci3
Rank-1 tensor

19 / 39

Tensors in Method of Moments
Matrix: Pair-wise relationship
Signal or data observed x ∈ Rd

Rank 1 matrix: [x ⊗ x]i,j = xi xj[x ⊗ x]i,j
=

xi

xj

Aggregated pair-wise relationship
M2 = E[x ⊗ x]

Tensor: Triple-wise relationship or higher
Signal or data observed x ∈ Rd
Rank 1 tensor:[x ⊗ x ⊗ x]i,j,k = xi xj xk[x ⊗ x ⊗ x]i,j,k
xk
= xi

xj

Aggregated triple-wise relationship
M3 = E[x ⊗ x ⊗ x] = E[x⊗3 ]20 / 39

CP decomposition

X =

R
P

h=1

ah ⊗ bh ⊗ chSummation of rank-1 tensors

21 / 39

Why are tensors powerful?
Matrix Orthogonal Decomposition
Not
unique without eigenvalue gap
1
0

0
1

⊤
⊤
⊤
= e1 e⊤
1 + e2 e2 = u 1 u 1 + u 2 u 2√√

e2 u2 = [ 22 , 22 ]e1 √√
u1 = [ 22 , −2 2 ]22 / 39

Why are tensors powerful?
Matrix Orthogonal Decomposition
Not
unique without eigenvalue gap

1 0
⊤
⊤
⊤
= e1 e⊤
1 + e2 e2 = u 1 u 1 + u 2 u 2
0 1
Unique with eigenvalue gap√√

e2 u2 = [ 22 , 22 ]e1 √√
u1 = [ 22 , −2 2 ]22 / 39

Why are tensors powerful?
Matrix Orthogonal Decomposition√

Not
unique without eigenvalue gap√

e2 u2 = [ 22 , 22 ]e1 √√
u1 = [ 22 , −2 2 ]

1 0
⊤
⊤
⊤
= e1 e⊤
1 + e2 e2 = u 1 u 1 + u 2 u 2
0 1
Unique with eigenvalue gap

Tensor Orthogonal Decomposition (Harshman, 1970)
Unique: eigenvalue gap not needed=+≠
22 / 39

Why are tensors powerful?
Matrix Orthogonal Decomposition√

Not
unique without eigenvalue gap√

e2 u2 = [ 22 , 22 ]e1 √√
u1 = [ 22 , −2 2 ]

1 0
⊤
⊤
⊤
= e1 e⊤
1 + e2 e2 = u 1 u 1 + u 2 u 2
0 1
Unique with eigenvalue gap

Tensor Orthogonal Decomposition (Harshman, 1970)
Unique: eigenvalue gap not needed
Slice of tensor has eigenvalue gap=+
22 / 39

Why are tensors powerful?
Matrix Orthogonal Decomposition√

Not
unique without eigenvalue gap√

e2 u2 = [ 22 , 22 ]e1 √√
u1 = [ 22 , −2 2 ]

1 0
⊤
⊤
⊤
= e1 e⊤
1 + e2 e2 = u 1 u 1 + u 2 u 2
0 1
Unique with eigenvalue gap

Tensor Orthogonal Decomposition (Harshman, 1970)
Unique: eigenvalue gap not needed
Slice of tensor has eigenvalue gap=+≠
22 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

23 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

24 / 39

Probabilistic Topic Models - LDA
Bag of words

Generative model

Infer topics of documents
Learn hidden process drives theobs.

Topic proportion ∼ Dir(α) for a doc
Draw a topic, then a word for a token

campuspoliceTopicswitness
campuspolicewitness

Topic Proportion
campuspolicewitness

25 / 39

Probabilistic Topic Models - LDA
Bag of words

Generative model

Infer topics of documents
Learn hidden process drives theobs.

Topic proportion ∼ Dir(α) for a doc
Draw a topic, then a word for a token

campuspoliceTopicsme
cri tsr
Spo onca

Edu

witness



campuscampuspolicepolicewitness

witness

Topic Proportion
campuspolicewitness

25 / 39

Probabilistic Topic Models - LDA
Bag of words

Generative model

Infer topics of documents
Learn hidden process drives theobs.

Topic proportion ∼ Dir(α) for a doc
Draw a topic, then a word for a token

campuspoliceTopicsEduwitnessme
cri tsr
Spo onca
campuscampuspolicepolicewitness

witness

Topic Proportion
campuspolicewitness

Goalcampuspolicewitness

Topic-word matrix P[word = ei |topic = j]
25 / 39

Moments Matching
Goal: Linearly independent topic-word tablecampuspolicewitness

E[word|topic = j] =Xi

P[word = ei |topic = j]ei =column j

26 / 39

Moments Matching
Goal: Linearly independent topic-word tablecampuspolicewitness

E[word|topic = j] =Xi

P[word = ei |topic = j]ei =column j

M1 : Occurrence Frequency of Words

itne
ca poli ss
m ce
pu
s
campuspoliceE[word] =X

E[word|topic = j]P[topic = j]

j

=

+

witnessus e 
mp p 
ca
w

a
uc
Ed

+

on

ts

or

Sp

e

im

cr

26 / 39

Moments Matching
Goal: Linearly independent topic-word tablecampuspolicewitness

E[word|topic = j] =Xi

P[word = ei |topic = j]ei =column j

M1 : Occurrence Frequency of Words)

itneca po(i ss
m ce
pu
s
campuspoliceE[word] =X

E[word|topic = j]P[topic = j]

j

=

+

witness
us !"e ''mp  !$%&
ca
#

a
uc
Ed

+

on

ts

or

Sp

e

im

cr

No unique decomposition of vectors
26 / 39

Moments Matching
Goal: Linearly independent topic-word tablecampusE[word|topic = j] =policewitness

Xi

P[word = ei |topic = j]ei =column j

M2 : Modified Co-occurrence Frequency of Word Pairs
E[word1 ⊗ word2 ] =6itne
ca po5i ss
m ce
pu
s
campusXj,j ′policeE[word1 |topic1 = j] ⊗ E[word2 |topic2 = j ′ ]P[topic1 = j, topic2 = j ′ ]=+witness
us ./e 44
mp +,- .123
ca
0

a*
uc
Ed

+

on

ts

or

Sp

e

im

cr

26 / 39

Moments Matching
Goal: Linearly independent topic-word tablecampusE[word|topic = j] =policewitness

Xi

P[word = ei |topic = j]ei =column j

M2 : Modified Co-occurrence Frequency of Word Pairs
E[word1 ⊗ word2 ] =Citne
ca poBi ss
m ce
pu
s
campusXj,j ′policeE[word1 |topic1 = j] ⊗ E[word2 |topic2 = j ′ ]P[topic1 = j, topic2 = j ′ ]=+witness
us ;<e AA
mp 89: ;>?@
ca
=

a7
uc
Ed

+

on

ts

or

Sp

e

im

cr

Matrix decomposition recovers subspace, not actual model
26 / 39

Moments Matching
Goal: Linearly independent topic-word table
Find a W

W

Wsuch thatW

M2 : Modified Co-occurrence Frequency of Word Pairs
E[word1 ⊗ word2 ] =Qitneca poPi ss
m ce
pu
s
campusXj,j ′policeE[word1 |topic1 = j] ⊗ E[word2 |topic2 = j ′ ]P[topic1 = j, topic2 = j ′ ]=+witness
us HIe OO
mp EFG HKMN
ca
J

aD
uc
Ed

+

on

ts

or

Sp

e

im

cr

Many such W ’s, find one, project data with W
26 / 39

Moments Matching
Goal: Linearly independent topic-word table
Know a W

W

W

W

such that

M3 : Modified Co-occurrence Frequency of Word Triplets
W

=

+

+

W
W
Unique orthogonal tensor decomposition, project result with W †26 / 39

Moments Matching
Goal: Linearly independent topic-word table
Know a W

W

W

W

such that

M3 : Modified Co-occurrence Frequency of Word Triplets
W

=

+

+

W
W
Tensor decomposition uniquely discovers the correct model
Learning Topic Models through Matrix/Tensor Decomposition
26 / 39Mixed Membership Community Models
Mixed memberships

27 / 39Mixed Membership Community Models
Mixed memberships

{{|
}









a






k
m

_

h

`
a
b

+

+

d
`

e

ns

=

c

cia

XYZ

no
nq
r
m

s

v
xy

RSUVW

f
g

j






an

s
u

z




ri
eta

~

ac
e

What ensures guaranteed learning?

[\]^SUW

27 / 39Mixed Membership Community Models
Mixed memberships

°°±
²

·

º»

¼

½

a

¹
¸

¿

£

Á
À

¤
¥

¾

=

+

+








ns







cia





¢

s

¬
­®

¡
¦§
¦¨
©
¥

an

ª
«

¯

´µ
¶

ri
eta

³

ac
e

What ensures guaranteed learning?



27 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

28 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =Piai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0

29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =Piai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0
Objective?

29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =PiObjectiveai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0min∀i,kui k2 =1

P

Objective?
T (ui , ui , uj , uj )Non-convex!

i6=j

Theorem: The proposed objective function has equivalent local optima.

29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =PiObjectiveai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0min∀i,kui k2 =1

P

Objective?
T (ui , ui , uj , uj )Non-convex!

i6=j

Theorem: The proposed objective function has equivalent local optima.
ÂÃddle Point

Will SGD work?

29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =PiObjectiveai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0min∀i,kui k2 =1

P

Objective?
T (ui , ui , uj , uj )Non-convex!

i6=j

Theorem: The proposed objective function has equivalent local optima.
ÄÅddle Point

Will SGD work?

Theorem: For smooth, twice-diff fn. with non-degenerate saddle points,
noisy SGD converges to a local optimum in polynomial steps.
29 / 39

Guaranteed Online Tensor Decomposition
Model is uniquely identifiable! How to identify?

Online Tensor Decomposition
Tensor T =PiObjectiveai ⊗ ai ⊗ ai ⊗ ai , where kai k = 1, a⊤i aj = 0min∀i,kui k2 =1

P

Objective?
T (ui , ui , uj , uj )Non-convex!

i6=j

Theorem: The proposed objective function has equivalent local optima.
ÆÇddle Point

Will SGD work?

Theorem: For smooth, twice-diff fn. with non-degenerate saddle points,
noisy SGD converges to a local optimum in polynomial steps.
Global Convergence Guarantee For Online Tensor Decomposition

29 / 39

Why could we escape from saddle points?
Stochastic Gradient Descent with NoiseÈÉddle Point

Saddle point has 0 gradient“Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition”,by R. Ge, F. Huang, C. Jin, Y. Yuan,
COLT 2015.
30 / 39

Why could we escape from saddle points?
Stochastic Gradient Descent with NoisestuckescapeSaddle point has 0 gradientNon-degenerate saddle: Hessian has ± eigenvalue“Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition”,by R. Ge, F. Huang, C. Jin, Y. Yuan,
COLT 2015.
30 / 39

Why could we escape from saddle points?
Stochastic Gradient Descent with NoisestuckescapeSaddle point has 0 gradientNon-degenerate saddle: Hessian has ± eigenvalue
Negative eigenvalue: direction of escape“Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition”,by R. Ge, F. Huang, C. Jin, Y. Yuan,
COLT 2015.
30 / 39

Why could we escape from saddle points?
Stochastic Gradient Descent with NoisestuckescapeSaddle point has 0 gradientNon-degenerate saddle: Hessian has ± eigenvalue
Negative eigenvalue: direction of escape

Noise could help!
“Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition”,by R. Ge, F. Huang, C. Jin, Y. Yuan,
COLT 2015.
30 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

31 / 39

First PCA
PCA problemdSample S = {xi }mi=1 , where xi ∈ R

Q: Identifies the direction of the largest variance in the data?

Problem Formulation
Solvingmaxu∈Rd ,kuk2 =1
1
where covariance matrix A = mmPu⊤ Au,

xi xi ⊤

i=1

Problem Regime
Assume 0  A  I and s-sparse (i.e., nnz(each row or column) ≤ s)
32 / 39

Classical Algorithm
Spectral Gap

Spectral gap ∆ = λ1 − λ2◮◮ordered eigenvalues 1 ≥ λ1 ≥ . . . λd ≥ 0
and corresponding eigenvectors u1 , . . . , ud .

Methods under Warm Start

Warm start: Initialization v0 such that |< v0 , u1 >| > φ > 0
Iteration methods achieve ǫ precision: < vk , u1 >≥ 1 − ǫ
k

◮
◮

A v0
sd
1
Power method kAk v k takes O( ∆ log( φǫ ))01Lanczos method or accelerated power method takes O( √sd∆ log( φǫ))⋆Replacing the monomial Ak by its Chebyshev polynomial approximation

Question: Speedup from O(d) to poly(log d)?

33 / 39

Quantum Speedup
Motivation
Quantum effects can achieve significant speedup.

ExamplesShor’s algorithm◮

exponential speed-up for factoring integers

Grover’s algorithm◮

quadratic speed-up for searching in unstructured database(Harrow, Hassidim, Lloyd ’09) & (Childs, Kothari, Somma ’17)◮◮Ω(d) → poly(log d) for solving d-dimensional linear equation systems.
weaker output requirement⋆

a quantum state whose vector representation is roughly the solution to
the linear equation system.

34 / 39

Quantum Leading PCA
Input model
Quantum oracle which generates a quantum state whose vector
representation is v0 and A.

Output model
A quantum state whose vector representation is vk

Main Result
Under warm start | < v0 , u1 > | = φ > 0, there is a quantum algorithm
which prepares a quantum state with vector representation vk such that< vk , u1 >≥ 1 − ǫ with probability at least 2/3√
using O(s log(s/φǫ)/φ ∆) queries to quantum oracle UA,s , UA,eO(1/φ) queries to Uv0√ssw. O(s(log d log( φǫ) + log3.5 ( φǫ))/φ ∆) 2-qubit quantum gates in total.
Joint work with Tongyang Li and Xiaodi Wu.
35 / 39

Intuition for Speedup

Chebyshev polynomials can be significantly accelerated
in quantum computation
Matrix power Ak b is the key◮

Quantum-walk⋆◮effectively constructs a degree-m Chebyshev polynomial of A/s.

Quantum primitive: the linear combination of unitaries (LCU)⋆

effectively linearly combines these Chebyshev polynomials to derive thedesired approximation polynomial.

Quantum Computation for Linear Algebraic Problems

36 / 39

Outline
1

Introduction

2

Introduction of Method of Moments and Tensor Notations

3

LDA and Community Models
From Data Aggregates to Model Parameters
Guaranteed Online Algorithm

4

Quantum Algorithms for Leading Eigenvector Computation

5

Conclusion

37 / 39

Summary
Spectral methods reveal hidden structure
Text/Image processing
Social networks
Neuroscience, healthcare ...

38 / 39

Summary
Spectral methods reveal hidden structure
Text/Image processing
Social networks
Neuroscience, healthcare ...

Versatile for latent variable models
=

+

+

+

=

+

+

+...+

+

Flat model → hierarchical modelSparse coding → convolutional
model

=

Efficient, convergence guarantee

+

=

+

+

stuck

=
M3

f1

sf1

+...+
f2

sf2
escape38 / 39

Thank You
furongh@cs.umd.edu

39 / 39