样本协方差矩阵的特征值的中偏差原理
Moderate Deviation Principle of the Eigenvalues of the Sample Covariance Matrix

作者: 金 鑫 , 解永晓 :山东师范大学数学与统计学院,山东 济南;

关键词: 样本协方差矩阵中偏差原理特征值码分多址Sample Covariance Matrix Moderate Deviation Principle Eigenvalues Code Division Multiple Access

摘要: 样本协方差矩阵特征值的大偏差对移动通信领域中比特错误问题的近似计算有非常重要的应用。设矩阵Ckxn的元素Cij独立且满足E[Cij]=0,Var(Cij)=1,则样本协方差矩阵的特征值为,其中x=(x1,x2,...xk),满足。本文首先给出样本协方差矩阵特征值的中偏差原理,即满足速度为速率函数为的中偏差原理,其中。其次使用数值模拟的方法利用python验证了该定理的准确性,最后利用该中偏差原理来对比CDMA系统中不同解码方案的优劣。

Abstract: The large deviation of eigenvalues of sample covariance matrix has great significance in calculating the bit error probability of Code Division Multiple Access. Throughout the paper, we assume that the i.i.d. real matrix elements of Ckxn satisfy E[Cij]=0, Var(Cij)=1, then the eigenvalue of the sample covariance matrix is , where x is with k coordinates and norm . First of all, we prove that satisfies moderate deviations where speed is and the rate function is , where . Then we use the numerical simulation method to model the theoretical function by python, to verify its reliability. Finally, we use the moderate deviation of sample covariance matrix in the CDMA to compare the advantages and disadvantages of different decoding techniques.

1. 引言

中偏差(Moderate Deviation Principle)及大偏差(Large Deviation Principle)原理可以度量稀有事件概率的渐近性质,特别是独立同分布的随机变量序列的中偏差及大偏差原理。因其典型的意义,在物理、金融和通信等很多方面都有显著的应用。虽然独立同分布随机变量序列的中偏差原理和大偏差原理形式相近,但在一定程度上还是有本质区别的 [1]。

样本协方差矩阵在统计学中经常被推广到各类实际问题上,如在电力、通信、金融和经济中进行建模。样本协方差矩阵的特征值是其中的一个重要元素,在实际问题中可以表示出很多具有现实意义的数

据。考虑一个 n k 列的矩阵 C n × k ,它的样本协方差矩阵为 W = 1 n C C T ,则对于任意的向量 x = ( x 1 , x 2 , , x k ) ,满足 x 2 = 1 。我们就可以用 x , W x 表示W的特征值,而这个 x , W x 有实际的意义。比如 C n × k 表示CDMA系统中的码相关矩阵,则借助 x , W x 的取值概率可以表示判断解码方案优劣的一种指标——比特错误概率。

Bai等人 [2] [3] [4] [5] 分别研究了元素为独立同分布随机变量时样本协方差矩阵的最大特征值和最小特征值的渐近行为。特别地,当C中的元素服从标准正态分布时,W被称作Wishirt矩阵,Wishart矩阵在统计学中扮演着重要的角色,其样本特征值的大偏差原理可见参考文献 [6]。Guionnet [7]、Hiai和Petz [8] 研究了速度为 1 n 2 时Wishart矩阵的样本特征值的大偏差原理。Anne等人 [6] [9] 证明了样本协方差矩阵最大最小特征值的大偏差原理,并在 [3] 中表明:当 n ,且k固定或者趋于无穷但不快于 o ( n / log log n ) 时,W的特征值是趋向于1的。由于W的最大最小特征值大偏差恰好就是BEP (Bit Error Probability),最后Anne等人将样本协方差矩阵的特征值大偏差情况的结果应用到CDMA系统的不同解码方案的建模中,给出了衡量CDMA解码系统优劣的另一种标准,该方法优于之前所使用的SNR (Signal Noise Ratio),见参考文献 [10]。但样本协方差矩阵的最大最小特征值的大偏差速率函数没有办法直接求解,所以Anne等人在Wishart矩阵中通过中心极限定理逼近的方法得到所求的样本协方差矩阵特征值的速率函数的渐近速率函数,并且在 λ min = 0 问题没有得到很好的解决,于是本文通过使用中偏差原理的普适性来尝试辅助解决这一问题。

定义1.1 考虑一列独立同分布的随机变量序列 { Y n } ,称 ( Y n ) 在拓扑空间X上服从速度为 a n 且速率函数为 I ( ) : X R + 的大偏差原理,是指

1) 对所有的开集 G X ,有

lim n inf 1 a n log ( Y n G ) inf x G I ( x ) , (1)

2) 对所有的闭集 A X ,有

lim n sup 1 a n log ( Y n A ) inf x A I ( x ) , (2)

其中I是下半连续函数,并且对所有的 L R + ,有紧的水平集 N L : = { x X : I ( x ) L }

{ Y n } 在拓扑空间X上服从速度为 n B 2 ( n ) 且速率函数为 I ( ) : X R + 的中偏差原理,其中 B ( n ) 是单调递增的数列,并且当 n 时满足

B ( n ) n 0 , B ( n ) n , (3)

在形式上也有类似的结果。

定义1.2 对于如定义1.1中的 { Y n } ,记 S n = i = 1 n Y n ,称 ( S n B ( n ) ) 满足速度为 n B 2 ( n ) ,速率函数为 I ( x ) 的中偏差原理,是指

1) 对所有的开集 G X ,有

lim n inf n B 2 ( n ) log ( S n B ( n ) G ) inf x G I ( x )

2) 对所有的闭集 A X ,有

lim n sup n B 2 ( n ) log ( S n B ( n ) A ) inf x A I ( x )

其中 I ( x ) = x 2 2 Var ( Y 1 )

大偏差原理和中偏差原理有本质的区别。大偏差原理描述的是依赖于大数定律的遍历现象,而中偏差原理则是描述的介于大数定律和中心极限定理之间的概率的渐近行为。具体地,大偏差原理的速率函数的计算依赖于随机变量的分布,而中偏差原理的速率函数只依赖于变量的中心极限定理的极限密度形式.也就是说,中偏差原理的速率函数并不依赖于随机变量的分布,所以中偏差原理相比于大偏差原理有普适性的特点。

对于一列独立同分布随机变量序列 X 1 , X 2 , , X n

δ > 0 , E e δ | X 1 | < + , (4)

则它的对数矩生成函数 Λ ( t ) = log E [ e t X 1 ] < t < ,由Cremér定理可知,随机变量序列 { X n } 的部分和序列 { S n } 满足速度为 1 n ,速率函数为 I ( α ) 的大偏差原理,其中速率函数 I ( α ) = sup t ( t α log E [ e t X 1 ] ) 。根据参考文献 [11] 的命题1.7可得,在(4)的条件下,对于满足条件(3)的 B ( n ) ,随机变量序列 { X n } 满足速度为 n B 2 ( n ) 速率为 I ( ) 的中偏差原理,其中

I ( x ) = x 2 2 Var ( X 1 ) . (5)

2. 样本协方差矩阵的特征值的中偏差原理

2.1. 系统模型

对于样本协方差矩阵为 W = 1 n C C T ,如果矩阵 C k × n 中的元素含有随机变量,则 W C 都是随机矩阵.本文假设 C 中的元素都是独立同分布的随机变量且满足

E ( C i j ) = 0 , Var ( C i j ) = 1. (6)

对于满足上述条件的 C ,当元素 C i j 的四阶矩有限,并且 k , n k n = β 时,其中 β 是一常数,那么W的特征值会收敛到固定的值。进一步,根据Bai和Yin的文献 [5] 可知, λ max 收敛到 ( 1 + β ) 2 ,而 λ min 收敛到 ( 1 β ) + 2 ,其中 x + = max { 0 , x } 。对于 C i j ,因为满足条件(6),可得W的非对角元素趋于0,而对角元素趋于1。对于矩阵 W 和任意的满足 x 2 = 1 的k维向量x,可知

λ min x , W x λ max ,

其中 x , W x 可以表示为

x , W x = 1 n | C T x | 2 = 1 n i = 1 n ( m = 1 k x m C m i ) 2 .

S x , i = m = 1 k x m C m i .

根据C的定义,可得 { S x , i } 是独立同分布的随机变量序列,并且满足 E ( S x , i ) = 0 , Var ( S x , i ) = x 2 ,通过Cremér定理可以得到 { S x , i 2 } 的大偏差原理,具体的内容可以查阅参考文献 [6] 和 [9]。

本文主要考虑的是 { S x , i 2 } 的中偏差定理,下面先来看一下主要结果。

2.2. 主要结果

对于上述定义的序列 { S x , i } ,记 σ 2 = Var ( S x , i 2 ) S n = i = 1 n S x , i 2 。设 B ( n ) 为单调上升序列,满足(3)式,若 ϵ > 0 ,使得

E [ e ϵ C 11 2 ] < (7)

则随机变量序列 { S x , i 2 } 满足中偏差原理,下面给出 S x , i 2 的具体中偏差结果。

定理2.2.1 记 μ n = ( | S n n B ( n ) | < ε ) ,若(7)成立,则 { S x , i 2 } 满足速度为 n B 2 ( n ) ,速率为 I ( x ) 的中偏差原理,其中 I ( x ) = x 2 2 σ 2 ,即

lim n n B 2 ( n ) log ( | S n n B ( n ) | < ε ) = ε 2 2 σ 2 . (8)

证明:由参考文献 [11] 知, ( μ n , n ) 的Cremér泛函为

( y ) = lim n log exp x , y / n B 2 ( n ) d μ n ( x ) = lim n n B 2 ( n ) log E exp [ ( S n n ) y B ( n ) B 2 ( n ) n ] = lim n n B 2 ( n ) log E exp [ ( S x , 1 2 1 ) B ( n ) n ] n = lim n n B 2 ( n ) log E exp [ S x , 1 2 y B ( n ) n y B ( n ) n ] = lim n n 2 B 2 ( n ) [ Λ ( B ( n ) n y ) B ( n ) n y ]

其中

Λ ( y ) = log E exp ( S x , 1 2 y ) ,

f ( t ) = Λ ( t y ) = log E exp ( S x , 1 2 t y ) ,计算可以得

f ( t ) = E S x , 1 2 y e S x , 1 2 t y E e S x , 1 2 t y ,

t = 0 可得 f ( 0 ) = y ,再对上式求导可得

f ( t ) = E ( S x , 1 2 y ) 2 e S x , 1 2 t y ( E S x , 1 2 y e S x , 1 2 t y ) 2 ( E exp S x , 1 2 t y ) 2 ,

带入 t = 0 可得 f ( 0 ) = E ( S x , 1 2 y ) 2 E 2 ( S x , 1 2 y ) = y 2 σ 2

由泰勒公式就可以得

( y ) = lim n 1 ( B 2 ( n ) n ) 2 [ f ( B ( n ) n ) f ( 0 ) B ( n ) n ] ,

所以

( y ) = 1 2 f ( 0 ) = y 2 σ 2 2 ,

则它的Legendre变换即速率函数就是

I ( x ) = sup ( x , y σ 2 y 2 2 ) = x 2 2 σ 2 .

lim n n B 2 ( n ) log ( | S n n B ( n ) | < ε ) = ε 2 2 σ 2 .

从而 μ n = ( | S n n B ( n ) | < ε ) 满足速率函数为 I ( x ) ,速度为 n B 2 ( n ) 的大偏差原理,即(8)式成立,则随机变量序列 { S x , i 2 } 的中偏差定理得证。

2.3. 数值模拟

对于所求速率函数 I ( x ) ,因为并没有良好的验证方法去验证其有效性,于是本文考虑(8)式,通过数值模拟的方法去实现对中偏差估计的检验。

上述中偏差的具体形式为定理2.2.1中的(8)式,当n充分大时,由(8)式得

n B 2 ( n ) log ( | S n n B ( n ) | < ε ) ε 2 2 σ 2

从而

( | S n n B ( n ) | < ε ) e ( ε B ( n ) ) 2 2 n σ 2 ,

P ( n ) = ( | S n n B ( n ) | < ε ) ,

Q ( n ) = e ( ε B ( n ) ) 2 2 n σ .

通过借助python生成 n 个满足 E [ x n ] = 0 , Var ( x n ) = 1 的随机变量 x n ,其中 x n , n = 1 , 2 , , 5000 ,然后通过带入 x n 计算 P ( n ) = ( | S n n B ( n ) | < ε ) 的图像,并可以直接输入公式 Q ( n ) = e ( ε B ( n ) ) 2 2 n σ 来画出 P ( n ) 的图像。本例中取 B ( n ) = n 0.9 ε = 0.1 ,最后将这两个函数的图像放在同一坐标系中来判断拟合的准确程度,最终结果如下图。

图1中,橙色曲线为 P ( n ) 的图像,蓝色曲线为 Q ( n ) 的图像,根据图片可以看出,随着n的逐渐增大, P ( n ) 逐渐逼近 Q ( n ) 。具体地:当 n < 500 时,两函数之间还会有些差异,这应该是单次模拟不充分导致的,但是当 n ( 500 , 1000 ) 时, P ( n ) 就渐渐地逼近 Q ( n ) ,至于 n > 1000 时,拟合的结果就非常好了,这是符合定理2.2.1的预期结果。

Figure 1. Simulation result of Theorem 2.2.1

图1. 定理2.2.1的模拟结果

3. 在CDMA系统中的应用

下面先简单地介绍一下本文所用到的CDMA系统。考虑共有k个用户的CDMA系统,每个用户发送的都是长度为n的信号,且每个信号中的元素都满足 ( C m i = 1 ) = ( C m i = 1 ) = 1 2 ,第m个用户所发送的信号为 C m = ( c m 1 , c m 2 , , c m n ) ,整个系统中的用户所发送的信号为一个k行n列的矩阵C,所以基站所接受的总体信号s就可以概括成

s = m = 1 k r m + N = C T b + N ,

其中N是由n个独立的高斯随机变量组成, N i N ( 0. σ 2 ) i = 1 , 2 , , n σ 表示噪声强弱的参数,即可加高斯白噪声(AWGN)。因为组成s的向量会在同一时间受到同一噪音的影响,并且有很多方法可以消除掉可加高斯白噪声,所以它对整个模型的影响是可以控制的,通常都会选择固定参数 σ 进行建模,具体可见参考文献 [6] [9]。

当基站接收到用户发来的编码后,需要对码序列进行解码,比如对用户m进行解码,就用码相关矩阵C和用户m的码序列 c m 做内积,然后再除以n。此时,得到 b m 的一个估计值 b ^ m

b ^ = 1 n C C T b + 1 n C N .

由于矩阵 1 n C C T 是样本协方差矩阵W,上式变成了

b ^ = 1 n W b + 1 n C N ,

通过变形可以把 b ^ m 写成

b ^ = b + ( W I ) b + 1 n C N ,

由这个式子可以清楚地看出, b ^ m 是由真实值b、多址干扰 ( W I ) b 1 n C N (即AWGN)组成。其中多址干扰(MAI)是影响解码系统效率的一个重要因素,在判断解码系统是否出现了问题时,主要是判断解码后得到的用户码序列的估计值 b ^ m 和原本的用户码序列 b m 的符号是否一致。当 b ^ m = 0 时符号就需要等可能的随机来判定正负,而如果发现 b ^ m b m 的符号不一致时,就认为解码系统产生了一个比特错误,这就是匹配滤波器解码(Matched Filter)出现错误的原理。

相对MF解码来说更加有优势的解码系统就是PIC解码(Parallel Interference Cancellation),有SD-PIC (Soft-Decision Parallel Interference Cancellation)和HD-PIC (Hard-Decision Parallel Interference Cancellation)解码方案。在大多数的解码方案中习惯性地把多址干扰和可加高斯白噪声放到一起进行处理。这种处理方式会影响对CMDA系统总体容量的估计,从而产生较大的误差,但是PIC解码会单独处理MAI,就会避免这种问题。

在多阶SD-PIC方案中,考虑忽略噪音的情况。若用 λ j 表示 W 的第 j 个特征值,一组正交基 w j 是与之对应的特征向量,向量 b 可用 W 的特征向量 w j 来表示。

b = j = 1 k β j w j ,

则SD-PIC方案的第 s 步迭代 b ^ ( s ) 可用 λ j 表示,

b ^ ( s ) = ζ = 0 s 1 j = 1 k ( 1 λ j ) s λ j β j w j = j = 1 k ( 1 ( 1 λ j ) s ) β j w j ,

在忽视噪声的情况下,若出现特征值等于0或大于2的情况,就会导致 ( 1 ( 1 λ j ) s ) 不收敛,从而产生比特错误。所以样本协方差矩阵W的最大、最小特征值的取值决定了是否会发生比特错误,我们可以通过计算样本协方差矩阵的最大、最小特征值偏差的概率来描述比特错误发生的概率,这样就把CDMA系统解码错误优劣的比较问题抽象成了一个数学问题。参考文献 [2] [3] 详细地介绍了整个建模过程,而关于CDMA系统的具体知识,可以阅读 [7]。因为发生比特错误是一个稀有事件,所以BEP可以通过使用大偏差原理来求解,在文献 [3] 中通过近似Wishart矩阵的方式计算出了该系统的BEP的速率函数,并分别给出了SD-PIC和dec两种解码方案的具体的BEP的速率函数,这里设该解码系统的大偏差原理速率函数为 I ( x ) ,对于SD-PIC,有 I S D min { I max ( 2 ) , I min ( 0 ) } 。对于dec,有 I dec I min ( 0 ) ,所以通过计算可以给出具体数值

I S D 1 2 1 2 log 2 ,

I dec log 2 ,

根据大偏差原理 B E P e n I 就可以计算给定用户数k和编码长度n的CDMA系统的不同解码方案的比特错误概率来比较它们的优劣。

在上述的CDMA系统中,由于 ( C m i = 1 ) = ( C m i = 1 ) = 1 2 是满足条件(6)的,所以可利用本文的结果来求解该CDMA系统的中偏差速率函数 I ( n ) ,所以在中偏差情况下,对于SD-PIC,相应的中偏差速率函数就是

I S D min { I ( 0 n B n ) , I ( 2 n B n ) } ,

对于dec解码相应的中偏差速率函数就是

I d e c I ( 0 n B n ) ,

对于具体情况,比如考察 x = 1 k ( 1 , 1 , ) 的情况,此时 σ 2 = 1 ,那中偏差速率函数 I ( α ) = α 2 2 ,于是对于 n = 16 λ 2 的速率函数即可求得 I ( λ 2 ) 0.405 ,这与 I dec 1 2 log 2 0.346 的结果相近,再将 I ( λ 2 ) 带入 Q ( x ) 即可算出 P ( d e c ) 得到最终结果

P ( d e c ) 0.024 ,

也就是说当一个CDMA系统中有16个用户时,使用dec解码方案会出错的概率约为0.024。

基金项目

国家自然科学基金青年基金(批准号:11601287)。

NOTES

*通讯作者。

文章引用: 金 鑫 , 解永晓 (2021) 样本协方差矩阵的特征值的中偏差原理。 应用数学进展, 10, 1350-1358. doi: 10.12677/AAM.2021.104145

参考文献

[1] Arcones, M.A. (2003) Moderate Deviations of Empirical Processes. Stochastic Inequalities and Applications, 56, 189-212.
https://doi.org/10.1007/978-3-0348-8069-5_13

[2] Bai, Z.D. and Silverstein, J.W. (1998) No Eigenvalues outside the Support of the Limiting Spectral Distribution of Large-Dimensional Sample Covariance Matrices. Annals of Probability, 26, 316-345.
https://doi.org/10.1214/aop/1022855421

[3] Bai, Z.D. and Silverstein, J.W. (2004) CLT for Linear Spectral Statistics of Large-Dimensional Sample Covariance Matrices. Annals of Probability, 32, 553-605.
https://doi.org/10.1214/aop/1078415845

[4] Bai, Z.D., Silverstein, J.W. and Yin, Y.Q. (1998) A Note on the Largest Eigenvalue of a Large Dimensional Sample Covariance Matrix. Journal of Multivariate Analysis, 26, 166-168.
https://doi.org/10.1016/0047-259X(88)90078-4

[5] Bai, Z.D. and Yin, Y.Q. (1993) Limit of the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix. Annals of Probability, 21, 1275-1294.
https://doi.org/10.1214/aop/1176989118

[6] Fey-den Boer, A., van der Hofstad, R. and Klok, M.J. (2008) Large Deviations for Eigenvalues of Sample Covariance Matrices with Applications to Mobile Communication Systems. Advance in Applied Probability, 40, 1048-1071.
https://doi.org/10.1017/S0001867800002962

[7] Guionnet, A. (2002) Large Deviation Asymptotics for Spherical Integrals. Journal of Functional Analysis, 188, 461-515.
https://doi.org/10.1006/jfan.2001.3833

[8] Hiai, F. and Petz, D. (1998) Eigenvalue Density of the Wishart Matrix and Large Deviations. Infinite Dimensional Analysis, Quantum Probability, 1, 633-646.
https://doi.org/10.1142/S021902579800034X

[9] Fey-den Boer, A., van der Hofstad, R. and Klok, M.J. (2003) Linear Interference Cancellation in CDMA Systems and Large Deviations of the Correlation Matrix Eigenvalues. 10th Symposium on Communications and Vehicular Technology in the Benelux, Eindhoven University of Technology, The Netherlands, 13 November 2003.

[10] Klok, M.J. (2001) Performance Analysis of Advanced Third Generation Receiverss. Ph.D. Thesis, Delft University of Technology, Delft, The Netherlands.

[11] 严加安, 彭实戈, 方诗赞, 等. 随机分析选讲[M]. 北京: 科学出版社, 1997.

分享
Top