다음의 모형을 생각하자.
다음의 두 항목을 증명하면 된다.
이 성립하는 B 1 ⊂ U ( s 0 , ζ 0 ) B 1 ⊂ U ( s 0 , ζ 0 )
이 성립하는 B 2 ⊂ U ( s 0 , ζ 0 ) B 2 ⊂ U ( s 0 , ζ 0 )
먼저 첫 항목을 보이자. ν = ϵ / 4 ν = ϵ /4 r = ⌊ p / 2 ⌋ , ϵ n p = ν log p / n r = ⌊ p /2 ⌋ , ϵ n p = ν log p / n A m ( u ) A m ( u ) m m u u
( A m ( u ) ) i j = { u i = m or j = m 0 otherwise ( A m ( u ) ) ij = { u 0 i = m or j = m otherwise
이라 하자. 이제, 다음과 같이 B 1 B 1
B 1 : = { Σ ( θ ) : Σ ( θ ) = I p + ϵ n p ∑ m = 1 r γ m A m ( λ m ) , θ = ( γ , λ ) ∈ Θ } B 1 := { Σ ( θ ) : Σ ( θ ) = I p + ϵ n p m = 1 ∑ r γ m A m ( λ m ) , θ = ( γ , λ ) ∈ Θ }
여기서 γ = ( γ 1 , ⋯ , γ r ) ∈ Γ = { 0 , 1 } r γ = ( γ 1 , ⋯ , γ r ) ∈ Γ = { 0 , 1 } r λ = ( λ 1 , ⋯ , λ r ) T ∈ Λ ⊂ R r × p λ = ( λ 1 , ⋯ , λ r ) T ∈ Λ ⊂ R r × p
Λ = { λ = ( λ i j ) : λ m i ∈ { 0 , 1 } , ∥ λ m ∥ 0 = k , ∑ i = 1 p − r λ m i = 0 , m ∈ { 1 , ⋯ , r } , satisfying max 1 ≤ i ≤ p ∑ m = 1 r λ m i ≤ 2 k } , Λ = { λ = ( λ ij ) : λ mi ∈ { 0 , 1 } , ∥ λ m ∥ 0 = k , i = 1 ∑ p − r λ mi = 0 , m ∈ { 1 , ⋯ , r } , satisfying 1 ≤ i ≤ p max m = 1 ∑ r λ mi ≤ 2 k } ,
k = ⌈ c n p / 2 ⌉ − 1 , c n p = ⌈ s 0 / p ⌉ k = ⌈ c n p /2 ⌉ − 1 , c n p = ⌈ s 0 / p ⌉ Θ = Γ × Λ Θ = Γ × Λ
이제 B 1 ⊂ U ( s 0 , ζ 0 ) B 1 ⊂ U ( s 0 , ζ 0 ) 논문의 식 (13) 이 성립함을 보이면 된다.
먼저, 임의의 ζ 0 > 1 ζ 0 > 1 n n Σ ( θ ) ∈ B 1 Σ ( θ ) ∈ B 1 ζ 0 ζ 0
λ max ( Σ ( θ ) ) ≤ ∥ Σ ( θ ) ∥ 1 ≤ 1 + 2 k ϵ n p ≤ 1 + c n p ν log p / n ≤ ζ 0 λ m a x ( Σ ( θ ) ) ≤ ∥ Σ ( θ ) ∥ 1 ≤ 1 + 2 k ϵ n p ≤ 1 + c n p ν log p / n ≤ ζ 0
두 번째 부등호는 모수공간 Λ Λ s 0 2 ( log p ) 3 = O ( p 2 n ) s 0 2 ( log p ) 3 = O ( p 2 n )
마찬가지의 이유로 임의의 ζ 0 > 1 ζ 0 > 1 n n
2 k ϵ n p ≤ c n p ν log p / n ≤ ( 1 + s 0 p ) ν log p / n ≤ 1 − ζ 0 − 1 2 k ϵ n p ≤ c n p ν log p / n ≤ ( 1 + p s 0 ) ν log p / n ≤ 1 − ζ 0 − 1
가 성립하므로 Σ ( θ ) − ζ 0 − 1 I p Σ ( θ ) − ζ 0 − 1 I p Σ ( θ ) Σ ( θ ) ζ 0 − 1 ζ 0 − 1
마지막으로 Σ ( θ ) Σ ( θ ) A m A m
s ( Σ ( θ ) ) ≤ 2 k p ≤ s 0 s ( Σ ( θ )) ≤ 2 k p ≤ s 0
에서 B 1 ⊂ U ( s 0 , ζ 0 ) B 1 ⊂ U ( s 0 , ζ 0 )
이제 논문의 식 (13) 이 성립함을 보이자. 이를 위해, 다음의 보조정리를 소개한다. 이 보조정리는 모수공간 Θ Θ d d ψ ( θ ) ψ ( θ )
(Lemma 3 of Cai and Zhou (2012))
OPTIMAL RATES OF CONVERGENCE FOR SPARSE COVARIANCE MATRIX ESTIMATION
For any s > 0 s > 0 T T ψ ( θ ) ψ ( θ ) { P θ , θ ∈ Θ } { P θ , θ ∈ Θ }
max θ ∈ Θ 2 s E θ d s ( T , ψ ( θ ) ) ≥ α r 2 min 1 ≤ i ≤ r ∥ P ‾ i , 0 ∧ P ‾ i , 1 ∥ , θ ∈ Θ max 2 s E θ d s ( T , ψ ( θ )) ≥ α 2 r 1 ≤ i ≤ r min ∥ P i , 0 ∧ P i , 1 ∥ ,
where P ‾ i , a P i , a P θ P θ γ i ( θ ) γ i ( θ ) θ θ
P ‾ i , a = 1 2 r − 1 ∣ Λ ∣ ∑ θ ∈ Θ i , a P θ , P i , a = 2 r − 1 ∣Λ∣ 1 θ ∈ Θ i , a ∑ P θ ,
for Θ i , a = { θ ∈ Θ : γ i ( θ ) = a } Θ i , a = { θ ∈ Θ : γ i ( θ ) = a }
∥ P ∧ Q ∥ = ∫ ( p ∧ q ) d μ , ∥ P ∧ Q ∥ = ∫ ( p ∧ q ) d μ ,
for probability measures P P Q Q p p q q E θ E θ [ X 1 , ⋯ , X n ∣ θ ] [ X 1 , ⋯ , X n ∣ θ ] H ( x , y ) H ( x , y )
H ( x , y ) = ∑ j = 1 r ∣ x i − y i ∣ , x , y ∈ { 0 , 1 } r . H ( x , y ) = j = 1 ∑ r ∣ x i − y i ∣ , x , y ∈ { 0 , 1 } r .
α = min ( θ , θ ′ ) : H ( γ ( θ ) , γ ( θ ′ ) ) ≥ 1 d s ( ψ ( θ ) , ψ ( θ ′ ) ) / H ( γ ( θ ) , γ ( θ ′ ) ) α = ( θ , θ ′ ) : H ( γ ( θ ) , γ ( θ ′ )) ≥ 1 min d s ( ψ ( θ ) , ψ ( θ ′ )) / H ( γ ( θ ) , γ ( θ ′ ))
최댓값은 평균보다 크거나 같으므로
max θ ∈ Θ 2 s E θ d s ( T , ψ ( θ ) ) ≥ 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ 2 s E θ d s ( T , ψ ( θ ) ) = 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ ( 2 d ( T , ψ ( θ ) ) ) s θ ∈ Θ max 2 s E θ d s ( T , ψ ( θ )) ≥ 2 r ∣Λ∣ 1 θ ∈ Θ ∑ 2 s E θ d s ( T , ψ ( θ )) = 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ ( 2 d ( T , ψ ( θ )) ) s
θ ^ : = arg min d s ( T , ψ ( θ ) ) θ ^ := arg min d s ( T , ψ ( θ ))
E θ ( 2 d ( T , ψ ( θ ) ) ) s ≥ E θ ( d ( T , ψ ( θ ) ) + d ( T , ψ ( θ ^ ) ) ) s ≥ E θ ( d ( ψ ( θ ^ ) , ψ ( θ ) ) ) s E θ ( 2 d ( T , ψ ( θ )) ) s ≥ E θ ( d ( T , ψ ( θ )) + d ( T , ψ ( θ ^ )) ) s ≥ E θ ( d ( ψ ( θ ^ ) , ψ ( θ )) ) s
를 얻는다. 마지막 부등식에서 삼각부등식을 사용하였다.
정리하면 다음을 얻는다.
max θ ∈ Θ 2 s E θ d s ( T , ψ ( θ ) ) ≥ 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ ( d ( ψ ( θ ^ ) , ψ ( θ ) ) ) s ≥ 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ [ ( d ( ψ ( θ ^ ) , ψ ( θ ) ) ) s H ( γ ( θ ) , γ ( θ ′ ) ) ∨ 1 H ( γ ( θ ) , γ ( θ ′ ) ) ] ≥ α 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ [ H ( γ ( θ ) , γ ( θ ′ ) ) ] θ ∈ Θ max 2 s E θ d s ( T , ψ ( θ )) ≥ 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ ( d ( ψ ( θ ^ ) , ψ ( θ )) ) s ≥ 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ [ H ( γ ( θ ) , γ ( θ ′ )) ∨ 1 ( d ( ψ ( θ ^ ) , ψ ( θ )) ) s H ( γ ( θ ) , γ ( θ ′ )) ] ≥ α 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ [ H ( γ ( θ ) , γ ( θ ′ )) ]
이제
1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ [ H ( γ ( θ ) , γ ( θ ′ ) ) ] ≥ r 2 min 1 ≤ i ≤ r ∥ P ‾ i , 0 ∧ P ‾ i , 1 ∥ 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ [ H ( γ ( θ ) , γ ( θ ′ )) ] ≥ 2 r 1 ≤ i ≤ r min ∥ P i , 0 ∧ P i , 1 ∥
을 보이면 원하는 결과를 얻는다.
1 2 r ∣ Λ ∣ ∑ θ ∈ Θ E θ [ H ( γ ( θ ) , γ ( θ ′ ) ) ] = 1 2 r ∣ Λ ∣ ∑ θ ∈ Θ ∑ i = 1 r E θ [ ∣ γ i ( θ ) − γ i ( θ ′ ) ) ∣ ] = ∑ i = 1 r 1 2 r ∣ Λ ∣ ∑ ρ ∈ Γ ∑ θ : γ ( θ ) = ρ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ ) ) ∣ ] = 1 2 ∑ i = 1 r { 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 0 ∑ θ : γ ( θ ) = ρ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ ) ) ∣ ] + 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 1 ∑ θ : γ ( θ ) = ρ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ ) ) ∣ ] } = 1 2 ∑ i = 1 r { 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 0 ∑ θ : γ ( θ ) = ρ E θ [ ∣ γ i ( θ ′ ) ) ∣ ] + 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 1 ∑ θ : γ ( θ ) = ρ E θ [ ∣ 1 − γ i ( θ ′ ) ) ∣ ] } = 1 2 ∑ i = 1 r { 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 0 ∑ θ : γ ( θ ) = ρ ∫ θ ′ γ i ( θ ′ ) ) d P θ ′ + 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 1 ∑ θ : γ ( θ ) = ρ ∫ θ ′ 1 − γ i ( θ ′ ) ) d P θ ′ } = 1 2 ∑ i = 1 r { ∫ θ ′ γ i ( θ ′ ) ) 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 0 ∑ θ : γ ( θ ) = ρ d P θ ′ + ∫ θ ′ ( 1 − γ i ( θ ′ ) ) ) 1 2 r − 1 ∣ Λ ∣ ∑ ρ i = 1 ∑ θ : γ ( θ ) = ρ d P θ ′ } = 1 2 ∑ i = 1 r { ∫ θ ′ γ i ( θ ′ ) ) d P ‾ i , 0 + ∫ θ ′ ( 1 − γ i ( θ ′ ) ) ) d P ‾ i , 0 } ≥ 1 2 ∑ i = 1 r ∫ d [ P ‾ i , 0 ∧ P ‾ i , 1 ] ≥ r 2 min 1 ≤ i ≤ r ∥ P ‾ i , 0 ∧ P ‾ i , 1 ∥ 2 r ∣Λ∣ 1 θ ∈ Θ ∑ E θ [ H ( γ ( θ ) , γ ( θ ′ )) ] = 2 r ∣Λ∣ 1 θ ∈ Θ ∑ i = 1 ∑ r E θ [ ∣ γ i ( θ ) − γ i ( θ ′ )) ∣ ] = i = 1 ∑ r 2 r ∣Λ∣ 1 ρ ∈ Γ ∑ θ : γ ( θ ) = ρ ∑ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ )) ∣ ] = 2 1 i = 1 ∑ r ⎩ ⎨ ⎧ 2 r − 1 ∣Λ∣ 1 ρ i = 0 ∑ θ : γ ( θ ) = ρ ∑ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ )) ∣ ] + 2 r − 1 ∣Λ∣ 1 ρ i = 1 ∑ θ : γ ( θ ) = ρ ∑ E θ [ ∣ γ i ( θ ) − γ i ( θ ′ )) ∣ ] ⎭ ⎬ ⎫ = 2 1 i = 1 ∑ r ⎩ ⎨ ⎧ 2 r − 1 ∣Λ∣ 1 ρ i = 0 ∑ θ : γ ( θ ) = ρ ∑ E θ [ ∣ γ i ( θ ′ )) ∣ ] + 2 r − 1 ∣Λ∣ 1 ρ i = 1 ∑ θ : γ ( θ ) = ρ ∑ E θ [ ∣1 − γ i ( θ ′ )) ∣ ] ⎭ ⎬ ⎫ = 2 1 i = 1 ∑ r ⎩ ⎨ ⎧ 2 r − 1 ∣Λ∣ 1 ρ i = 0 ∑ θ : γ ( θ ) = ρ ∑ ∫ θ ′ γ i ( θ ′ )) d P θ ′ + 2 r − 1 ∣Λ∣ 1 ρ i = 1 ∑ θ : γ ( θ ) = ρ ∑ ∫ θ ′ 1 − γ i ( θ ′ )) d P θ ′ ⎭ ⎬ ⎫ = 2 1 i = 1 ∑ r ⎩ ⎨ ⎧ ∫ θ ′ γ i ( θ ′ )) 2 r − 1 ∣Λ∣ 1 ρ i = 0 ∑ θ : γ ( θ ) = ρ ∑ d P θ ′ + ∫ θ ′ ( 1 − γ i ( θ ′ )) ) 2 r − 1 ∣Λ∣ 1 ρ i = 1 ∑ θ : γ ( θ ) = ρ ∑ d P θ ′ ⎭ ⎬ ⎫ = 2 1 i = 1 ∑ r { ∫ θ ′ γ i ( θ ′ )) d P i , 0 + ∫ θ ′ ( 1 − γ i ( θ ′ )) ) d P i , 0 } ≥ 2 1 i = 1 ∑ r ∫ d [ P i , 0 ∧ P i , 1 ] ≥ 2 r 1 ≤ i ≤ r min ∥ P i , 0 ∧ P i , 1 ∥
증명이 끝났다.
위의 보조정리에 s = 2 s = 2
inf Σ ^ max θ ∈ Θ 2 2 E θ ∥ Σ ^ − Σ ( θ ) ∥ F 2 ≥ α r 2 min 1 ≤ i ≤ r ∥ P ‾ i , 0 ∧ P ‾ i , 1 ∥ Σ ^ inf θ ∈ Θ max 2 2 E θ ∥ Σ ^ − Σ ( θ ) ∥ F 2 ≥ α 2 r 1 ≤ i ≤ r min ∥ P i , 0 ∧ P i , 1 ∥
여기서
α = min ( θ , θ ′ ) : H ( γ ( θ ) , γ ( θ ′ ) ) ≥ 1 ∥ Σ ( θ ) − Σ ( θ ′ ) ∥ F 2 / H ( γ ( θ ) , γ ( θ ′ ) ) α = ( θ , θ ′ ) : H ( γ ( θ ) , γ ( θ ′ )) ≥ 1 min ∥ Σ ( θ ) − Σ ( θ ′ ) ∥ F 2 / H ( γ ( θ ) , γ ( θ ′ ))
이다.
이때 임의의 θ , θ ′ ∈ Θ θ , θ ′ ∈ Θ
∥ Σ ( θ ) − Σ ( θ ′ ) ∥ F 2 = ϵ n p 2 ∥ ∑ m = 1 r γ m ( θ ) A m ( λ m ( θ ) ) − ∑ m = 1 r γ m ( θ ′ ) A m ( λ m ( θ ′ ) ) ∥ F 2 ≥ 2 k ϵ n p 2 H ( γ ( θ ) , γ ( θ ′ ) ) ∥ Σ ( θ ) − Σ ( θ ′ ) ∥ F 2 = ϵ n p 2 m = 1 ∑ r γ m ( θ ) A m ( λ m ( θ )) − m = 1 ∑ r γ m ( θ ′ ) A m ( λ m ( θ ′ )) F 2 ≥ 2 k ϵ n p 2 H ( γ ( θ ) , γ ( θ ′ ))
이므로 k k r r r = ⌊ p / 2 ⌋ , k = ⌈ c n p / 2 ⌉ − 1 , c n p = ⌈ s 0 / p ⌉ r = ⌊ p /2 ⌋ , k = ⌈ c n p /2 ⌉ − 1 , c n p = ⌈ s 0 / p ⌉
α r ≥ 2 k ϵ n p 2 r ≥ ν 2 ( 1 2 − p s 0 ) s 0 log p n ≍ s 0 log p n α r ≥ 2 k ϵ n p 2 r ≥ ν 2 ( 2 1 − s 0 p ) n s 0 log p ≍ n s 0 log p
이제, 다음을 만족하는 적당한 상수 c 1 > 0 c 1 > 0
min 1 ≤ i ≤ r ∥ P ‾ i , 0 ∧ P ‾ i , 1 ∥ ≥ c 1 1 ≤ i ≤ r min ∥ P i , 0 ∧ P i , 1 ∥ ≥ c 1