Toeplitz矩阵有限等距特性研究

陈忠辉, 熊　芸

(福州大学物理与信息工程学院, 福建 福州 350116)



Toeplitz矩阵有限等距特性研究

陈忠辉, 熊芸

(福州大学物理与信息工程学院, 福建 福州 350116)

摘要：在压缩感知热潮的影响下,观测矩阵的有限等距特性(restricted isometry property, RIP)也受到广泛关注。大多数理论研究表明高斯随机矩阵是满足RIP特性的,但由于其存储成本较高,物理实现较复杂,在实际使用中托普利兹(Toeplitz)随机矩阵由于可以使用快速离散傅里叶变换实现而受到青睐。该文将图论中点均匀着色定理和盖尔圆盘定理应用于压缩感知中,对托普利兹观测矩阵的RIP特性进行了证明,证明结果表明,由服从某种特定概率分布的项构造的Toeplitz矩阵以较大概率满足有限等距特性。最后,对最小二乘算法(least square,LS)、线性最小均方误差(linear minimum mean square error,LMMSE)算法和高斯观测矩阵的压缩感知算法以及Toeplitz观测矩阵的压缩感知算法进行了对比分析,Toeplitz观测矩阵的压缩感知算法在性能方面要优于高斯观测矩阵的压缩感知算法和传统算法,运算复杂度方面要优于高斯随机矩阵,为压缩感知实现无失真地重构原始信号提供了理论和应用参考。

关键词：观测矩阵; 有限等距特性; 均匀着色; 盖尔圆盘定理

0引言

图的染色理论是图论中的一个重要分支,在现实生活中有很多问题,例如排序问题、工作分配问题、无线电频率分配问题、卫星通讯问题等最终都可以归结为图的染色问题。染色按照点边的不同又分为点染色,边染色和全染色等[8]。该文创造性地将图的均匀着色理论应用于观测矩阵RIP的证明。

观测矩阵RIP-3k性质的一个等价描述是ΘT的奇异值或由ΘT构成的Gram矩阵Gr(ΘT)=(ΘT)TΘT的特征值位于区间(1-δ3k,1+δ3k)。Geršchgorin圆盘定理是矩阵特征值估计的一个基本定理,指出矩阵Mn×n的所有特征值包含在以对角线元素为圆心的n个圆盘的并集中。这种天然的联系使得应用Geršchgorin圆盘定理于RIP特性证明成为可能。

1图论着色模型数学描述

图的着色理论是图论的重要组成部分,图的着色主要有点着色和边着色,点着色由可以细分为均匀着色,松弛着色和树着色。图G的一个正常k-顶点着色是指k种颜色在V上的一种分配,使得任意2个相邻的顶点分配以不同颜色。若图G有一个正常k-顶点着色,就称G是k-顶点可着色的。

设φ是图G的一个正常的顶点着色,φ的任何2种不同颜色所染的顶点数目至多相差1,称φ是G的一个均匀着色。如果φ是图G的一个均匀k-顶点着色,称φ是G的一个均匀k-顶点着色。有限、简单图由G=G(V(G),E(G))来描述,简写为G=G(V,E)。V(G)为图G的顶点集合,V(G)的元素为图G的顶点,图G的顶点个数称为它的阶;E(G)称为图G的边集合,E(G)的元素为图G的边;在图G中与顶点u相邻的顶点的全体叫作u的邻域,记作NG(u),称NG(u)为顶点u的度数,记作dG(u)。同时称度数为k的顶点为k-点。Δ(G)和δ(G)分别表示图G的最大自由度和最小自由度。

实际上,图论着色方法可用于很多观测矩阵具有统计结构相关性的情况下,该文所阐述的是均匀着色在观测矩阵的有限等距特性证明的应用,重点目标就是将由观测矩阵构成的无向简单图G划分为若干个完全非连通子图,也就是独立集。我们给出如下的例子进行说明：对于一个5阶无向简单图,均匀点着色方案之一如图1所示。

G=G(V,E)E={E1,E2,E3,E4,E5},对图进行点均匀着色划分独立集为{V1}{V2,V4}{V3}{V5}。在证明的过程中,我们关注的并不是找到这样的具体划分,而是确定是否存在独立集元素数目一定的划分。实际上,图论着色方法可用于很多观测矩阵具有统计结构相关性的情况下,该文所阐述的是均匀着色在观测矩阵的有限等距特性证明的应用。其中著名的Hajnal-Szemerédi定理[9]：给定一个正整数r,如果一个图G最大度不超过r,那么这个图G存在一个均匀(r+1)-着色。

图1　5阶无向简单图均匀点着色示意图

2Toeplitz矩阵RIP特性证明——图论方法

通常,我们最常用的压缩感知的理论模型为

(1)

(2)

(3)

(4)

目前在多项式时间上,还没有方法测试一个给定的观测矩阵是否满足RIP,能做的就是给定的观测矩阵能以多大的概率满足RIP。大多数的观测矩阵理论研究都是围绕高斯随机矩阵而进行的,并且理论研究表明高斯随机矩阵的效果确实不错。在实际应用中,我们并不能主观选择观测矩阵,观测矩阵与感知过程的物理性质以及物理实现是有紧密联系的。由于高斯随机矩阵的物理实现较复杂或成本较高,实际的观测矩阵通常不是高斯随机矩阵,也不是伯努利随机矩阵[11]。大量研究表明：Toeplitz矩阵由于可以通过离散傅里叶变换实现而受到广泛关注。形式如下所示：

(5)

零均值高斯分布

(6)

零均值其他分布

(7)

定义 1对方阵L∈Cl×l,

行盖尔圆盘为

(8)

列盖尔圆盘为

(9)

引理 1(圆盘定理) 对方阵L∈Cl×l,L的特征值

(10)

定理 1给定k,n,在m≥c·kln(n/k)条件下,如果观测矩阵Θ的项满足上述若干独立同分布之一,且对于任意的δ3k∈(0,1/3)和任意的T⊂{1,2,…,n}、|T|=3k,以高概率满足RIP-3k约束,则根据索引列集合T而得到m×|T|的子矩阵将以大于1-e-f(m,k,δ3k)的概率满足RIP-3k约束。

其中,f(m,k,δ3k) 是参数m,k和δ3k的实数函数。

如果θi服从同一独立同分布,观测矩阵Θ是m×n的Toeplitz矩阵,则对于任意的δ3k∈(0,1/3)和任意的T⊂{1,2,…,n}、|T|=3k,根据索引列集合T而得到m×|T|的子矩阵ΘT将以大于1-e-f(|m/q|,k,δ3k)+ln(q)的概率满足RIP-3k约束。

其中q=3k(3k-1)+1。下面就给出定理1的证明过程。

证明根据文献[13]有

(11)

式中

给定δ3k∈(0,1/3),T⊂{1,2,…,n}、|T|=3m。由ΘTi·(ΘTi·表示矩阵ΘT的第i行)中的共m行元素构造一个简单无向图G=G(V,E),V={1,2,…,m},E={(i,i′)∈V×V:i≠i′,ΘTi·和ΘTi′·是相关的}。由Toeplitz矩阵ΘT性质可得：ΘT的任一行最多与其他的|T|(|T|-1)=q-1行相关,也就是说,在构造的图G中,某个顶点最多与q-1个顶点相邻或者由某个顶点引出的边最多有q-1条,用图论的专业术语就是图G的最大自由度Δ(G)≤q-1。由Hajnal-Szemerédi定理可知,图G存在一个均匀q-点着色。我们用Cj表示某种颜色的顶点集合,即独立集。则有

(12)

同时也可以得到

(13)

(14)

(15)

证毕

3Toeplitz矩阵RIP证明——盖尔圆盘法

上文已经给出行盖尔圆盘和列盖尔圆盘的定义,下面给出盖尔圆盘半径定义。

定义 2对方阵L∈Cl×l,盖尔圆的半径定义为Gr(ΘT)盖尔圆盘的中心

(16)

引理 2对方阵L∈Cl×l,它的全部特征值都位于以ci为中心,直径为di=di(ci,ri)的圆盘内，ci=Li,i(i=1,2,…,l)。

3.1零均值高斯分布的Toeplitz矩阵RIP证明

下面给出定理2的证明。

证明对角线元素的对称约束我们有

(17)

对于独立的非对角线元素,会比较复杂。首先将非对角线元素作变形有

(18)

当m是偶数时,式(18)可以改写为

当m是奇数时,式(18)又可以改写为

式中,t1,t2是重新组合的元素个数。π1,π2是组合算子,没必要将组合算子π1,π2的构成弄清楚,只要知道存在这样的组合算子即可。

将一个大的组合分成2个小组合,再应用对称约束得

δo-d∈[0,1],应用大致估计t1≤t2≤m,可得

证毕

3.2零均值约束随机分布的Toeplitz矩阵RIP证明

下面给出定理3的证明：

证明应用盖尔圆盘定理,得Gram矩阵Gr(ΘT)的对角线元素和非对角线元素的对称约束条件。

对角线元素的单对称约束为

(19)

对角线元素的联合对称约束为

(20)

Gram矩阵Gr(ΘT)的非对角线元素可视为Toeplitz矩阵不同列的内积,以下例作为说明。

(21)

因此,非对角线元素的单对称约束为

同样应用大致估计t1≤t2≤m,可得

证毕

由于循环矩阵是特殊形式的Toeplitz矩阵,故上述证明对循环矩阵也适用。

4实验仿真

实际的无线信道的稀疏性特性使得压缩感知的重构算法应用于无线信道估计有了可能,本文将一种机器学习算法(稀疏贝叶斯学习算法[16](sparseBayesianlearning,SBL)应用于长期演进(longtermevolution,LTE)系统信道估计,比较了传统的最小二乘算法(leastsquare,LS)、线性最小均方误差(linearminimummeansquareerror,LMMSE)算法、高斯观测矩阵的压缩感知算法以及Toeplitz观测矩阵的压缩感知算法的均方误差。系统仿真参数如表1所示,Matlab仿真结果如图2所示。

表1　仿真参数

图2　LS、LMMSE、Gauss、Toeplitz的信道估计均方误差比较

高斯观测矩阵和Toeplitz观测矩阵的相关性, Gauss、Toeplitz算法二者的运行时间比较如表2所示。

表2　观测矩阵相关性和运行时间比较

由仿真结果可知,稀疏贝叶斯学习算法的性能要优于传统的信道估计算法,且信噪比越大,优势更大。Toeplitz观测矩阵的相关性较高斯矩阵而言更大,算法运行时间更短,均方误差更小。

5总结

观测矩阵的设计是压缩感知三要素之一, 是将压缩感知从理论推向实际应用的一个关键因素。传统的高斯随机矩阵虽然能很好地满足RIP,但是其随机特征导致物理实现困难。Toeplitz 随机观测矩阵由于可以使用快速傅里叶变换而在物理上实现更容易、 存储成本更低。而该文引入图论着色理论和盖尔圆盘定理,证明了Toeplitz 随机观测矩阵以较大概率满足RIP。同时实验仿真表明,与高斯观测矩阵比较而言,Toeplitz 观测矩阵的运算复杂度和性能都优于前者,这对于 CS 理论的实际应用具有非常重要的意义。

参考文献：

[1] Donoho D L．Compressed sensing[J].IEEETrans.onInformationTheory,2006, 52 (4):1289-1306.

[2] Candes E J, Tao T．Near-optimal signal recovery from random projections:universal encoding strategies[J].IEEETrans.onInformationTheory,2006, 52 (12):5406-5425.

[3] Candes E J, Tao T． Decoding by linear programming[J].IEEETrans.onInformationTheory, 2005, 51 (12):4203-4215.

[4] Cohen A, Dahmen W, DeVore R. Compressed sensing and bestk-term approximation[J].JournaloftheAmericanMathematicalSociety, 2009,22(1):211-231.

[5] Cen Y G, Zhao R Z, Miao Z J, et al. A new approach of conditions on δ2s(Φ)fors-sparse recovery[J].ScienceChinaInformationSciences, 2014, 57(4):1-7.

[6] Guédon O, Litvak A E, Pajor A,et al. Restricted isometry property for random matrices with heavy-tailed columns[J].ComptesRendusMathematique, 2014, 352(5):431-434.

[7] He X, Song R. Pilot pattern optimization for compressed sensing based sparse channel estimation in OFDM systems[C]∥Proc.oftheInternationalConferenceonWirelessCommunicationsandSignalProcessing, 2010:1-5.

[8] Chen B L, Lih K W, Yen C H. Equivalence of two conjectures on equitable coloring of graphs[J].JournalofCombinatorialOptimization, 2013, 25(4):501-504.

[9] Lo A, Markstr M K. A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs[J].Combinatorics,ProbabilityandComputing, 2013, 22(01):97-111.

[10] Rauhut H, Romberg J, Tropp J A. Restricted isometries for partial random circulant matrices[J].AppliedandComputationalHarmonicAnalysis, 2012, 32(2):242-254.

[11] Strohmer T. Measure what should be measured:progress and challenges in compressive sensing[J].IEEESignalProcessingLetters, 2012, 19 (12):887-893.

[12] Haupt J, Bajwa W U, Raz G,et al. Toeplitz compressed sensing matrices with applications to sparse channel estimation[J].IEEETrans.onInformationTheory,2010,56(11):5862-5875.

[13] Krahmer F, Mendelson S, Rauhut H. Suprema of chaos processes and the restricted isometry property[J].CommunicationsonPureandAppliedMathematics, 2014.

[14] Rivenson Y, Stern A, Rosen J. Reconstruction guarantees for compressive tomographic holography[J].OpticsLetters, 2013, 38(14):2509-2511.

[15] Marsli R, Hall F J. Geometric multiplicities and Geršgorin discs[J].TheAmericanMathematicalMonthly,2013,120(5):452-455.

[16] Prasad R, Murthy C R, Rao B D. Nested sparse Bayesian learning for block-sparse signals with intra-block correlation[C]∥Proc.oftheIEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing, 2014:7183-7187.

陈忠辉(1960-),男,教授,硕士，主要研究方向为通信系统、信号处理。

E-mail：czh@fzu.edu.cn

熊芸(1988-),女,硕士研究生,主要研究方向为无线通信、压缩感知、信道估计。

E-mail：liuyunnima0911@gmail.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141105.1646.018.html

Research on the restricted isometry property for Toeplitz matrix

CHEN Zhong-hui, XIONG Yun

(CollegeofPhysicalandInformationEngineering,FuzhouUniversity,Fuzhou350116,China)

Abstract:The restricted isometry property (RIP) of the sensing matrix has recently received a lot of attention under the rubric of compressive sensing. Most studies have shown that a Gaussian random sensing matrix satisfies the RIP in theory. However, due to its high cost of storage and complex physical implementation, the Toeplitz sensing matrix is more in favored than the Gauss sensing matrix in actual. Because it can be implemented by the fast discrete Fourier transform. Proof of the RIP for the sensing matrix exploiting graph theory and the Geršgorin’s disc theorem is given. The results show that the Toeplitz random matrix satisfies the RIP with high probability. And the least square (LS), linear minimum mean square error (LMMSE), compressive sensing algorithm with the Gauss sensing matrix and compressive sensing algorithm with Toeplitz sensing matrix channel estimation algorithm are compared. The simulation results show that the Toeplitz sensing matrix has a superiority over the Gauss sensing matrix on computation complexity and the traditional channel estimation method on performance and computation complexity. It provides a theoretical and realistic foundation for reconstructing the original signal losslessly.

Keywords:sensing matrix; restricted isometry property (RIP); equitable coloring; Geršgorin’s disc theorem

作者简介：

中图分类号：TN 919.5

文献标志码：ADOI:10.3969/j.issn.1001-506X.2015.05.07

基金项目：国家自然科学基金(61170147)；福建省教育厅科技项目(JA12024)资助课题

收稿日期：2014-06-26；修回日期：2014-08-31；网络优先出版日期：2014-11-05。