Tighter Upper Bound of Real Log
Canonical Threshold of Non-negative
Matrix Factorization and its Application
to Bayesian Inference
Naoki Hayashi* (TokyoTech, Dept. of MCS)
Sumio Watanabe (TokyoTech, Dept. of MCS)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

1Slide• This slide is available at
http://watanabe-www.math.dis.titech.ac.jp/~nhayashi/pdf/hayashi1039.pdf

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

2

Index• Introduction• Main Theorem• Discussion• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

31. INTRODUCTION

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

4Index• Introduction– Non-negative Matrix Factorization– Real Log Canonical Threshold– Research Goal

• Main Theorem• Discussion• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

5

NMF has been applied• Non-negative Matrix Factorization (NMF) has
been applied to many field• E. g.
– Purchase basket data → Consumer analysis– Image, sound,… → Signal processing– Text data → Text mining– Microarray data → Bioinformatics↑ Knowledge/Structure Discovery
NMF: data → knowledge
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

6

HOWEVER

Suffering• NMF has hierarchical structure• Likelihood cannot be approximatedby Gaussian function• Traditional statistics cannot be used AIC BIC

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

7

HOWEVER

Suffering• NMF has hierarchical structure• Likelihood cannot be approximatedby Gaussian function• Traditional statistics cannot be used AIC BIC
Hierarchical structure causes non-identifibility :𝑿𝒀 = 𝑿𝑷𝑷−𝟏 𝒀; 𝐟𝐨𝐫 ∃𝑷 ≠ 𝑰; 𝑿, 𝒀, 𝑿𝑷, 𝑷−𝟏 𝒀 ≥ 𝟎𝟏 𝟑𝟏 𝟑𝟏 𝟒

2017/11/28

𝟏 𝟑𝟒𝟐 −𝟑 𝟐 −𝟑 −𝟏 𝟏 𝟏= 𝟏 𝟑𝟒𝟏 𝟐𝟏 𝟐𝟓 𝟏
𝟏 𝟒𝟏𝟔 𝟒 𝟏𝟔
𝟏 𝟓 𝟑 𝟏𝟕 𝟓 𝟐𝟎== 𝟏𝟔 𝟒 𝟏𝟔
𝟓 𝟑𝟗 𝟏 𝟒𝟕𝟐𝟏 𝟓 𝟐𝟎
𝟔 𝟓𝟏 𝟏𝟓 𝟏IEEE SSCI 2017 FOCI, Hawaii

𝟒𝟒8

HOWEVERSuffering• NMF has hierarchicalOne
structurematrix,• Likelihood cannot be approximated(at least)
pairs
by Gaussian function
about
theNMF• Traditional statistics cannot be used AIC BIC
Hierarchical structure causes non-identifibility :𝑿𝒀 = 𝑿𝑷𝑷−𝟏 𝒀; 𝐟𝐨𝐫 ∃𝑷 ≠ 𝑰; 𝑿, 𝒀, 𝑿𝑷, 𝑷−𝟏 𝒀 ≥ 𝟎
𝟏 𝟑
𝟏 𝟑𝟏 𝟒2017/11/28

𝟏 𝟑𝟒𝟐 −𝟑 𝟐 −𝟑 −𝟏 𝟏 𝟏= 𝟏 𝟑𝟒
𝟏 𝟐𝟏 𝟐𝟓 𝟏
𝟏 𝟒𝟏𝟔 𝟒 𝟏𝟔
𝟏 𝟓 𝟑 𝟏𝟕 𝟓 𝟐𝟎== 𝟏𝟔 𝟒 𝟏𝟔
𝟓 𝟑
𝟗 𝟏 𝟒
𝟕𝟐𝟏 𝟓 𝟐𝟎
𝟔 𝟓

𝟏 𝟏
𝟓 𝟏

IEEE SSCI 2017 FOCI, Hawaii

𝟒𝟒9

HOWEVERSuffering• NMF has hierarchical structure• Likelihood cannot be approximatedby Gaussian function• Traditional statistics cannot be used AIC BIC

In Addition +• Strongly depending on initial value• Suffering from many local minima– It seldom reaches to the global minimum.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

10Learning Theory of NMF• NMF has been used for ``data → knowledge’’

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

11Learning Theory of NMF• NMF has been used for ``data → knowledge’’• Mathematical property is unknown– Learning theory has not been yet established– Prediction accuracy has not been yet clarified

No guarantee for correctness ofnumerical calculation
No method for theoretical
hyperparameter tuning
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

12Learning Theory of NMF• NMF has been used for ``data → knowledge’’• Mathematical property is unknown– Learning theory has not been yet established– Prediction accuracy has not been yet clarified

Constructing its theory is
an important problem
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

13

Index• Introduction– Non-negative Matrix Factorization– Real Log Canonical Threshold– Research Goal

• Main Theorem• Discussion• Conclusion• (Appendix: Sktech of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

14When does RLCT appear?
• In general [Watanabe, 2001]– Let n be the sample size– Bayesian generalization error 𝑮𝒏 has
an asymptotic behavior:

𝝀𝟏𝔼 𝑮𝒏 = + 𝒐𝒏𝒏• Learning coefficient
𝝀 depends on the model• 𝝀 is called real log canonicalthreshold (RLCT)
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

15Error: Bayes<<Freq.
• In hierarchical structure model, Bayesian 𝝀 issmaller than frequentist’s one and maximum
posterior one [Watanabe,2001 and 2009]• Bayesian inference is effective for reducing
the generalization error• We consider Bayesian inference framework– Bayesian inference for NMF has been proposed[Cemgil, 2009] Rem: ← is only discrete

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

16

RLCT of NMF is unknown• NMF has been used for ``data → knowledge’’• Mathematical property is unknown– Learning theory has not been established– Prediction accuracy has not been clarified↑ means that the RLCT of NMF has
not been clarified

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

17Def. RLCT• RLCT is characterized as a learning coefficient• It is defined by the largest pole of thefollowing complex function:
𝜻 𝒛 = න𝑲 𝒘 𝒛 𝝋 𝒘 𝒅𝒘,
where 𝑲 is KL-divergence from true distribution
to learning machine and 𝝋 is prior.
• A statistical model selection method that uses
RLCTs has been proposed [Drton, et al. 2017]2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

18

Def. RLCT• RLCT is characterized as a learning coefficient• It is defined by the largest pole of thefollowing complex function:𝜻 𝒛= න𝑲 𝒘 𝒛 𝝋 𝒘 𝒅𝒘,

known as sBIC
(singular BIC)

where 𝑲 is KL-divergence from true distribution
to learning machine and 𝝋 is prior.
• A statistical model selection method that uses
RLCTs has been proposed [Drton, et al. 2017]2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

19

Index• Introduction– Non-negative Matrix Factorization– Real Log Canonical Threshold– Research Goal

• Main Theorem• Discussion• Conclusion• (Appendix: Sktech of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

20Research Goal
• Constructing learning theory of NMF→focus theoretical generalization error→focus RLCT of NMF• Recently, we derived an upper bound ofRLCT [Hayashi, et. al. 2017]• We used algebraic geometrical method(singularity resolution)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii21

Research Goal
• Constructing learning theory of NMF→focus theoretical generalization error→focus RLCT of NMF• In this research, we newly derive the exact
value of the RLCT of NMF in the case rank ≦ 2• Using the above exact value, we make theupper bound tighter than previous one

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

222. MAIN THEOREM

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

23

Index• Introduction• Main Theorem– Bayesian Framework of NMF– Main Result• Discussion• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

24Formalizing and Setting• Data matrices: 𝑾𝒏 = 𝑾𝟏 , … , 𝑾𝒏 ; 𝑴 × 𝑵(× 𝒏)– For general, we treat not only n=1 but also n>1.

𝑵𝑴𝑾
[Kohjima et al. 2016/6, modified]
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

25Formalizing and Setting• Data matrices: 𝑾𝒏 = 𝑾𝟏 , … , 𝑾𝒏 ; 𝑴 × 𝑵(× 𝒏)– For general, we treat not only n=1 but also n>1.

• True factorization: 𝑨; 𝑴 × 𝑯𝟎 , 𝑩; 𝑯𝟎 × 𝑵• Learner factorization: 𝑿; 𝑴 × 𝑯, 𝒀; 𝑯 × 𝑵
𝑯𝟎𝑵𝑵𝑯𝟎𝑴𝑾𝑴

𝑩𝑨[Kohjima et al. 2016/6, modified]

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

26

Formalizing and Setting• Data matrices: 𝑾𝒏 = 𝑾𝟏 , … , 𝑾𝒏 ; 𝑴 × 𝑵(× 𝒏)– For general, we treat not only n=1 but also n>1.

• True factorization: 𝑨; 𝑴 × 𝑯𝟎 , 𝑩; 𝑯𝟎 × 𝑵• Learner factorization: 𝑿; 𝑴 × 𝑯, 𝒀; 𝑯 × 𝑵• What is the Bayesian framework of ↑?
𝑯𝟎𝑵𝑵𝑯𝟎𝑴𝑾𝑴

𝑩

𝑨[Kohjima et al. 2016/6, modified]

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

27

Formalizing and Setting• Notation of probability density function (PDF)
data– 𝑞 𝑊 : true distribution,– 𝑝 𝑊 𝑋, 𝑌 : learning machine,– 𝑝∗ 𝑊 : predictive distribution,
whose domains are Euclidian sp.
parameter– 𝜑 𝑋, 𝑌 : prior distribution,– 𝑝 𝑋, 𝑌 𝑊 𝑛 : posterior distribution given data,
whose domains are compact subsets of Euclidian sp.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

28Formalizing and Setting• Assume𝟏𝒒 𝑾 ∝ 𝐞𝐱𝐩 − 𝑾 − 𝑨𝑩 𝟐 ,𝟐𝟏
𝒑 𝑾 𝑿, 𝒀 ∝ 𝐞𝐱𝐩 − 𝑾 − 𝑿𝒀 𝟐 ,𝟐and prior 𝝋 is strictly positive and bounded in aneighborhood of 𝑨, 𝑩 .
• Remark: Poisson and exponential dist. can bealso applied [Hayashi, et al. 2017].
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

29

Bayesian Framework• The posterior is defined by𝒏𝟏
𝒏𝒑 𝑿, 𝒀 𝑾 =ෑ 𝒑 𝑾𝒊 𝑿, 𝒀 𝝋 𝑿, 𝒀
𝒁𝒏
𝒊=𝟏

where 𝒁𝒏 is normalizing constant.
• The predictive distribution is defined by𝒑∗ 𝑾 = න𝒑 𝑾 𝑿, 𝒀 𝒑 𝑿, 𝒀 𝑾𝒏 )𝒅𝑿𝒅𝒀 .

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

30Bayesian Framework• The Bayesian generalization error is defined by
KL-divergence from true to predictive dist. :𝒒 𝑾
𝑮𝒏 = න 𝒒 𝑾 𝐥𝐨𝐠 ∗𝒅𝑾.
𝒑 𝑾
• This depends on the training data thus it is arandom variable.
• Its expected value among the overall data has
an asymptotic behavior:
𝝀𝟏
𝔼 𝑮𝒏 = + 𝒐.
𝒏𝒏
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

31

Index• Introduction• Main Theorem– Bayesian Framework of NMF– Main Result• Discussion• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

32

Def. RLCT of NMF• The RLCT of NMF is defined by the minus
maximum pole of the following zeta function:
𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩2017/11/28

𝟐 𝒛 𝒅𝑿𝒅𝒀 .

IEEE SSCI 2017 FOCI, Hawaii

33

Def. RLCT of NMF• The RLCT of NMF is defined by the minus
maximum pole of the following zeta function:
𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩

𝟐 𝒛 𝒅𝑿𝒅𝒀 .

• 𝜻 𝒛 can be analytically continued to the entire
complex plane and its poles are negative
rational numbers.
• The largest pole of 𝜻 𝒛equals −𝝀 . Then,
𝝀 is the RLCT of NMF.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

34

Def. RLCT of NMF• The RLCT of NMF is defined by the minus
maximum pole of the following zeta function:
𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩

𝟐 𝒛 𝒅𝑿𝒅𝒀 .

• 𝜻 𝒛 can be analytically continued to the entire
complex plane and its poles are negative
rational numbers.
𝒛 = −𝝀• The largest pole of 𝜻 𝒛𝐎𝐗
𝐗𝐗 𝐗𝐗
equals −𝝀 . Then,ℂ
𝝀 is the RLCT of NMF.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

35

Main Theorem• The RLCT of NMF 𝝀 satisfies the following
inequality:
𝟏𝝀≤𝑯 − 𝑯𝟎 𝐦𝐢𝐧 𝑴, 𝑵 + 𝑯𝟎 𝑴 + 𝑵 − 𝟐 + 𝜹𝑯𝟎 ,𝟐where𝟏 (𝑯𝟎 ≅ 𝟏, 𝐦𝐨𝐝 𝟐)
𝜹 𝑯𝟎 = ቊ.
𝟎 (𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆)

The equality holds if 𝑯 = 𝑯𝟎 = 𝟏 𝐨𝐫 𝟐 or 𝑯𝟎 = 𝟎.

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

36

3. DISCUSSION

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

37

Index• Introduction• Main Theorem• Discussion– Tightness– Theoretical Application– Numerical Experiment and Conjecture• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

38Tighter than previous• Main Theorem shows an upper bound of theRLCT of NMF.
• We have derived another bound of it inprevious research.
• How tight is the new bound?

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

39Tighter than previous• In previous work,𝟏
𝝀 ≤ 𝝀𝒑𝒓𝒗 =𝑯 − 𝑯𝟎 𝐦𝐢𝐧 𝑴, 𝑵 + 𝑯𝟎 𝑴 + 𝑵 − 𝟏 .
𝟐• In this paper,𝟏
𝝀 ≤ 𝝀𝒏𝒆𝒘 =𝑯 − 𝑯𝟎 𝐦𝐢𝐧 𝑴, 𝑵 + 𝑯𝟎 𝑴 + 𝑵 − 𝟐 + 𝜹𝑯𝟎 .
𝟐• By comparing them, we improve the bound𝟏
𝝀𝒏𝒆𝒘 − 𝝀𝒑𝒓𝒗 = 𝑯𝟎 − 𝜹𝑯𝟎 .
𝟐• True dist. is more complex, bound is tighter.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

40

Index• Introduction• Main Theorem• Discussion– Tightness– Theoretical Application– Numerical Experiment and Conjecture• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

41

Bound of Error• Main Theorem shows an upper bound of theBayesian generalization error via
𝝀𝟏
𝔼 𝑮𝒏 = + 𝒐.
𝒏𝒏

• Actually, we have
𝟏𝟏𝔼 𝑮𝒏 ≤𝑯 − 𝑯𝟎 𝐦𝐢𝐧 𝑴, 𝑵 + 𝑯𝟎 𝑴 + 𝑵 − 𝟐 + 𝜹𝑯𝟎 + 𝒐.
𝟐𝒏𝒏

– This gives guarantee of accuracy!

• What distribution can we bound the error?

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

42

Robustness on Dist.
• Main Theorem assumes that elements ofparameter matrices are subject to normaldistribution:𝒒 𝑾 ∝ 𝓝 𝑾 𝑨𝑩 ,𝒑 𝑾 𝑿, 𝒀 ∝ 𝓝 𝑾 𝑿𝒀 .
• Can Main Theorem be used even for otherdistributions?

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

43

Robustness on Dist.
• In the prior work [Hayashi, et. al. 2017],
we proved that same zeta function can beapplied to Poisson and exponential distribution:𝒒 𝑾 ∝ 𝐏𝐨𝐢 𝑾 𝑨𝑩 ,Even if𝒑 𝑾 𝑿, 𝒀 ∝ 𝐏𝐨𝐢 𝑾 𝑿𝒀 ,𝒒 𝑾 ∝ 𝐄𝐱𝐩𝐨 𝑾 𝑨𝑩 ,𝒑 𝑾 𝑿, 𝒀 ∝ 𝐄𝐱𝐩𝐨 𝑾 𝑿𝒀 ,We can use
𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩2017/11/28

𝟐 𝒛 𝒅𝑿𝒅𝒀 .

IEEE SSCI 2017 FOCI, Hawaii

44Robustness on Dist.
• The above result is derived by the fact that
I-divergence and Itakura Saito-divergence havesame RLCT as square error.
Distribution

NormalPoissonSimilarity

Sq. error

I-divergence IS-divergence

We can use
𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩2017/11/28

Exponential

Same RLCTs
𝟐 𝒛 𝒅𝑿𝒅𝒀IEEE SSCI 2017 FOCI, Hawaii

45

Robustness on Dist.
• The above result is derived by the fact that
I-divergence and Itakura Saito-divergence havesame RLCT as square error.
Distribution

NormalPoisson

Exponential

Similarity

Sq. error

I-divergence IS-divergence

Same RLCTs
We can use
Main Thm.
𝒛𝜻 𝒛 = ඵ 𝑿𝒀 − 𝑨𝑩 𝟐 𝒅𝑿𝒅𝒀
is attained!
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

46

Index• Introduction• Main Theorem• Discussion– Tightness– Theoretical Application– Numerical Experiment and Conjecture• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

47

Numerical Experiment• We carried out experiment to estimate theexact value of RLCT.
– (+) to compare with the RLCT of reduced rank
regression (RRR); non-restricted matrix factorization.

• The posterior cannot be analytically derived.
→Markov Chain Monte Carlo(MCMC)– We used Metropolis Hastings method.

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

48

Non-negative Rank
• We made artificial data and set the following
cases:– 1. exact value of RLCT of NMF is known.
– 2. exact value is unknown and rank = rank+.
– 3. exact value is unknown and rank ≠ rank+.

• rank+ : minimal inner dimension of NMF– ↑ is called non-negative rank.
– In general, rank+≧ rank holds.
– If min{rows, columns} ≦ 3 or rank ≦2, rank =rank+.
– There is a non-negative matrix s.t. rank＜rank+.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

49

Condition of Experiments• Sample size n=200 (parameter dimension≦50)• The number of data sets D=100→ we empirically calculated the RLCT using𝑫

𝝀𝟏𝒏𝒋
𝔼 𝑮𝒏 = + 𝒐→ 𝝀 ≈ 𝒏𝔼 𝑮𝒏 ≈ ෍ 𝑮𝒏𝒏𝒏
𝑫𝒋=𝟏

• MCMC sample size K=1,000– Burn-in=20,000, thin=20, i.e. sampling iteration is 40,000.

• For calculating 𝑮𝒏 , we generated T=20,000 test
datas from the true distribution.
• Total: 100*(40,000+1,000*20,000) ≈ 𝑶 𝑫𝑲𝑻
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

50Numerical Result

r: true rank𝝀𝑵

𝝀Numerical
calculated

The exact
value in NMF

2017/11/28

𝝀𝑩

𝝀𝑹

The upper
The exact
bound in NMF value in RRRIEEE SSCI 2017 FOCI, Hawaii

51

Numerical Result

r: true rank
𝝀𝑵

𝝀𝝀𝑩

Numerical
calculated

The exact
value in NMF

𝝀𝑹

The upper
The exact
bound in NMF value in RRR

Numerical results equal
theoretical value: 𝝀𝑵 = 𝝀.
Numerical calculation is correct!
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

52

Numerical Resultr: true rank
𝝀𝑵𝝀𝝀𝑩

Numerical
calculated

The exact
value in NMF

𝝀𝑹The upper
The exact
bound in NMF value in RRR

If rank = rank+, then numericalresults equal RRR case: 𝝀𝑵 = 𝝀𝑹 .

It seems that if rank = rank+,
then the RLCT of NMF 𝝀 = 𝝀𝑹 .
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

53

Numerical Resultr: true rank
𝝀𝑵𝝀𝝀𝑩

Numerical
calculated

The exact
value in NMF

𝝀𝑹The upper
The exact
bound in NMF value in RRR

If rank ≠ rank+, then num. results
are larger than RRR case: 𝝀𝑵 > 𝝀𝑹 .
If rank ≠ rank+,
then the RLCT of NMF islarger than RRR case:
𝝀𝑵 > 𝝀𝑹 .
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

54

From the paper:

2017/11/28

ConjectureIEEE SSCI 2017 FOCI, Hawaii

55

4. CONCLUSION

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

56

Index• Introduction• Main Theorem• Discussion• Conclusion• (Appendix: Sketch of Proof)

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

57

Conclusion• (Main contribution) We mathematically
improved the upper bound of the RLCT of NMF.
– This made the bound of the generalization error in
Bayesian NMF tighter.

• (Minor contribution) We carried out experiments
and suggested conjecture about the exact valueof the RLCT:– ･ rank = rank+ ⇒ RLCT of NMF = RLCT of RRR.
– ･ rank ≠ rank+ ⇒ RLCT of NMF > RLCT of RRR.

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

58

APPENDIX: SKETCH OF
PROOF FOR MAIN THEOREM

2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

59

Sketch of Proof• We have already derived the exact value in thecase 𝑯𝟎 = 𝟎 and 𝑯 = 𝑯𝟎 = 𝟏.
• We newly clarified the exact value in the case
𝑯 = 𝑯𝟎 = 𝟐 by considering the dimension ofalgebraic subvariety in the parameter space.
• We bound the RLCT in the case 𝑯 = 𝑯𝟎 by using
the clarified exact value mentioned above.
• We bound the RLCT in general case by using theabove results.
2017/11/28

IEEE SSCI 2017 FOCI, Hawaii

60