高 有，王 剛

（中國民航大學(xué)理學(xué)院，天津 300300）

基于仿射奇異線性空間構(gòu)造壓縮感知矩陣

高 有，王 剛

（中國民航大學(xué)理學(xué)院，天津 300300）

基于仿射奇異線性空間的子空間面之間的關(guān)聯(lián)關(guān)系，構(gòu)造了一個新的壓縮感知矩陣，計算了所構(gòu)造的壓縮感知矩陣的相關(guān)性，并得到處理信號可以恢復(fù)的最大稀疏度，同時，與Ronald A DeVore利用有限域上的多項式構(gòu)造的壓縮感知矩陣進行比較，當兩個壓縮感知矩陣處理信號的有效率相同時，基于仿射奇異線性空間構(gòu)造的壓縮感知矩陣處理信號的最大稀疏度優(yōu)于Ronald A.DeVore構(gòu)造的壓縮感知矩陣處理信號的最大稀疏度。

壓縮感知矩陣；仿射奇異線性空間；相關(guān)性；稀疏度

壓縮感知理論在信號處理過程中扮演著重要的角色，其主要目的是通過較少的測量次數(shù)對信號進行觀測來獲取信號的主要信息，進而能準確或高概率恢復(fù)信號。給定一個離散信號x∈Rn（實數(shù)域R上的n維列向量），利用m個線性投影來測量信號x，并把這m個線性投影組成的m×n階矩陣φ叫做壓縮感知矩陣，并把y=φx稱為測量向量。

如果一個信號x∈Rn中至多有k個非0分量，則稱x是k-稀疏信號。對于一個給定的測量向量y，如何將原始信號x從y=φx中恢復(fù)出來，Donodo和Candes等[1-2]充分利用信號的稀疏性質(zhì)，通過尋找線性方程y=φx的稀疏解問題

即可得到原始稀疏信號x的信息。而給定一個矩陣，如何判斷其是否適合作為壓縮感知矩陣，Candes等[2]給出被廣泛接受的判斷標準——受限等距性。設(shè)φ是一個m×n階矩陣，如果存在一個常數(shù)0≤δk＜1，使得對于任意k-稀疏的信號x∈Rn，均有如下不等式成立

則稱矩陣φ滿足k階受限等距性，滿足上式的最小非負實數(shù)δk稱為k階受限等距常數(shù)。設(shè)矩陣φ的列向量為（a1，a2，…，an），則矩陣φ的相關(guān)性為

由于低相關(guān)性可以導(dǎo)出受限等距性[3]，因此只要一個矩陣的相關(guān)性足夠低即可用來測量信號。

引理1[4]設(shè)矩陣φ的相關(guān)性為μ，則對于所有矩陣φ都滿足k階受限等距性，受限等距常數(shù)δk≤μ（k-1）。

DeVore[5]利用有限域上次數(shù)不大于r的多項式構(gòu)造相關(guān)性是的感知矩陣；Li Shuxing等[6-7]利用代數(shù)曲線和有限幾何構(gòu)造了感知矩陣；Bourgain等[3]利用加法組合學(xué)構(gòu)造了m×n的感知矩陣，其中受限等距性的階為是任意選定的實數(shù)；Zhao Xianghui等[8]利用偽辛空間中子空間的關(guān)聯(lián)關(guān)系構(gòu)造了新的池設(shè)計。

本文基于仿射奇異線性空間構(gòu)造了壓縮感知矩陣，計算了其相關(guān)性，并得到了構(gòu)造的壓縮感知矩陣可恢復(fù)的信號最大稀疏度，并與DeVore利用有限域上多項式構(gòu)造的壓縮感知矩陣進行比較，當兩個壓縮感知矩陣處理信號的有效率相同時，基于仿射奇異線性空間構(gòu)造的壓縮感知矩陣處理信號的最大稀疏度優(yōu)于Ronald A.DeVore構(gòu)造的壓縮感知矩陣處理信號的最大稀疏度。

1 預(yù)備知識

仿射奇異線性空間的概念[9-11]介紹如下。

2 壓縮感知矩陣的構(gòu)造

首先回顧DeVore[5]構(gòu)造的大小為p2×pr的感知矩陣。設(shè)Fp是一個有限域，其中p是一個素數(shù)，Pr表示有限域Fp上所有次數(shù)不超過r-1的多項式組成的集合，所以任意一個多項式f∈Pr，可將f看成是從Fp到Fp得映射，對于取定的一個多項式f，記二元列向量vf為

設(shè)GA（n+l，n；Fq）是Fq上的（n+l）-維仿射奇異線性空間，集合G表示（n+l）-維仿射奇異線性空間GA（n+l，n；Fq）中所有（m1，s1）-面的集合，其中0≤s1≤ l，0≤m1-s1≤n，即M）是GA（n+l，n；Fq）中不同的（m1，s1）-面，M=O（m1，s1；n+l，n）。集合H表示（n+l）-維仿射奇異線性空間GA（n+l，n；Fq）中所有（m，s）-面的集合，其中0≤s≤l， 0≤m-s≤n，即N）是GA（n+l，n；Fq）中不同的（m，s）-面，N=O（m，s；n+ l，n）。

設(shè)φ0=（aij）M×N是一個{0,1}-矩陣，其中

{0,1}-矩陣φ0的每一列中1的個數(shù)L等于GA（n+l，n；Fq）中包含在給定的（m，s）-面的（m1，s1）-面的個數(shù)。由引理3，知

由引理1可知，對于所有的k＜q(m1+1)+1，矩陣φ0都滿足k階受限等距性，所以信號可以恢復(fù)的最大稀疏度為

令k1=0，有m1≤m-s≤n，則kmax=q（n+1），而此時所構(gòu)造矩陣的行數(shù)與列數(shù)之比為

已知DeVore利用有限域上多項式構(gòu)造的壓縮感知矩陣的行數(shù)與列數(shù)之比為

且最大稀疏度為

這樣得到最大稀疏度kmax＞k′max。

[1]DONOHO D.Compressed sensing[J].IEEE Trans Inform Theory，2006，52：1289-1306.

[2]CANDES E，ROMBERG J，TAO T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information[J]. IEEE Trans Inform Theory，2006，52：489-509.

[3]BOURGAIN J，DILWORTH S，F(xiàn)ORD K，et al.Explicit constructions of RIP matrices and related problems[J].Duke Math J，2011，159：145-185.

[4]CANDES E.The restricted isometry property and its implications for compressed sensing[J].CR Math Acad Sci Paris，2008，346：589-592.

[5]DEVORE R.Deterministic constructions of compressed sensing matrices[J].J Complexity，2007，23：918-925.

[6]LI SHUXING，GAO FEI，GE GENNIAN，et al.Deterministic construction of compressed sensing matrices via algebraic curves[J].IEEE Trans.Inform Theory，2012，58：5035-5041.

[7]LI SHUXING，GE GENNIAN.Deterministic construction of sparse sensingmatricesviafinitegeometry[J].IEEETrans on Signal Processing，2014，62：2850-2859.

[8]ZHAO XIANGHUI，XU NING，ZHANG GENGSHENG.New pooling design constructed with pseudo-symplectic[J].Chin Quart J of Math，2012，27：526-534.

[9]ZHANG MANLI，JIE CUNLAI.Anzahl theorems of flats in affine singular linear spaces and their applications[J].Journal of Hebei Normal University（Natural Science Edition），2012，36：560-563.

[10]WAN ZHEXIAN.Geometry of Classical Groups Over Finite Fields[M]. 2nd ed.Beijing：Science Press，2002.

[11]WANG KAISHUN，GUO JUN，LI FENGGAO.Singular linaer space and its application[J].Finite Fields App，2011，17：395-406.

（責(zé)任編輯：楊媛媛）

從而

2）設(shè)m、m′是兩個同時對編碼規(guī)則e有效的不同報文，且m∩L≠m′∩L。若m與m′不相交，則不存在這樣的編碼規(guī)則。若m與m′相交，則由維數(shù)公式可知，m∩m′是一個平面，且與L不相交。該平面上任意一條直線均是對m、m′同時有效的編碼規(guī)則。從而

參考文獻：

[1]SIMMONS G J.Authentication theory/decoding theory[J].Lecture Notes in Computer Science，1985，96：411-431.

[2]LIANG M，DU B L.A new class of 3-fold perfect splitting authenticationcodes[J].DesignCodesCryptography，2012，62：109-119.

[3]CHEN S D，ZHAO D W.Construction of multi-receiver multi-fold authentication codes from singular sympletic geometry over finite fields[J]. Algebra Colloquium，2013，20（4）：701-710.

[4]CHEN S D，ZHAO D W.New construction of authentication codes with arbitration from pseudo-sympletic geometry over finite fields[J].Ars Combinatoria，2010，97（A）：453-465.

[5]GAO Y，LIU Y Q.The construction of A3-code from projective spaces over finite fields[J].WSEAS Transactions on Mathematics，2013，12（10）：1024-1033.

[6]SIMMONS G J.A game theory model of digital message authentication [J].Congr Numer，1982，34：413-424.

[7]KUROSAWA K，OBANA S.Combinatorial bounds on authentication codes with arbitration[J].Designs Codes Cryptography，2001，22：265-281.

[8]王永傳，楊義先.分裂認證碼與糾錯碼[J].通信保密，1999，77（1）：64-66.

[9]HUBER M.Combinatorial bounds and characterizations of splitting authentication codes[J].Cryptography and Communications，2010，2：173-185.

[10]WAN Z X.Geometry of Classical Groups over Finite Fields[M].2nd ed. Beijing：Science Press，2002.

（責(zé)任編輯：楊媛媛）

Construction of compressed sensing matrix based on affine singular linear spaces

GAO You，WANG Gang
（College of Science，CAUC，Tianjin 300300，China）

A compressed sensing matrix based on correlations of subspace flats in the affine singular linear spaces is constructed and the coherence of the matrix is computed.Meanwhile，the maximum sparsity of the matrix is obtained.Finally，a comparision is made with the matrix constructed by Ronald A DeVore based on polynomials over finite fields and the maximum sparsity of the current matrix is better than that of the matrix constructed by Ronald A DeVore when the efficiencies of the two matrices are equal.

compressed sensing matrix；affine singular linear space；coherence；sparsity

O157.2

：A

：1674－5590（2015）06－0061－04

2014-08-05；

：2014-10-10

中央高?；究蒲袠I(yè)務(wù)費專項（SY-1416）；中國民航大學(xué)學(xué)生（波音）技術(shù)挑戰(zhàn)資助基金項目（20140159201）

高有（1966—），男，內(nèi)蒙古化德人，教授，博士，研究方向為代數(shù)、密碼與編碼.