标题

Size: px

Start display at page:

Download "标题"

寻旃从
5 years ago
Views:

1 第 37 卷第 9 期西南大学学报 ( 自然科学版 ) 2015 年 9 月 Vol 37 No 9 JournalofSouthwestUniversity (NaturalScienceEdition) Sep 2015 DOI: /j cni xdz 冗余字典的扰动压缩数据分离刘春燕, 张静, 王建军西南大学数学与统计学院, 重庆摘要 : 在冗余字典满足相互一致性条件和完全扰动矩阵满足限制性同构条件下, 基于 l1 极小化方法, 对压缩数据分离问题进行了研究, 完美地重构了原始信号. 关键词 : 压缩数据分离 ;l1 极小化 ; 相互一致性 ; 限制性等容性质 ; 紧框架 ; 完全扰动中图分类号 :TN911 文献标志码 : 文章编号 : (2015) 近年来,Donoho 和 Candes 等人提出的压缩感知 [1-2], 已经实现了采样和压缩同时进行. 该理论是在信号 ( 近似 ) 可压缩或稀疏条件下, 以远低于 Nyquist 标准进行采样, 从而实现对信号的准确重构. 该理论指出, 对于任何信号只要能找到其相应的稀疏表示空间, 就可以进行有效地压缩采样. 压缩感知理论的优点 [3] 还在于它对应用科学的许多领域具有重大的影响, 如统计学信息科学计算机科学等. 目前压缩感知在模拟信息采样核磁共振成像合成孔径雷达成像深孔探测成像遥感成像无线传感器网络人脸识别 [4-8] 等诸多领域展开了广泛研究. 考虑如下模型 : y=f +z (1) 其中 : R m n (m n) 是测量矩阵,y R m 是观测信号,f R n 是重构的目标信号,z R m 是一个噪音向量. 压缩感知所要解决的一个核心问题是从 (1) 式中找出一个最稀疏的解 f R n, 即如下 l0 化问题 : 极小 min f 0s t f -y 2 ε (2) f Rn 其中 : f 0 表示 f 中非零元素的个数 ἐ 是 z 2 的上界.l0 极小化是一个 NPGhard 问题 [9], 通常是将其转化为求解以下的 l1 极小化问题 : min f 1s t f -y 2 ε (3) f Rn 如果 f R n 至多有 ( n) 个非零元素, 那么称向量 f 为稀疏信号, 并记为 f 0. 由于实际应用中, 很多信号 f R n 并不具有稀疏性, 但是这些信号在一些字典 D R n d (d n) 上, 能由稀疏向量进行表示 [9-12], 即存在稀疏向量 x R d, 使得 f =Dx, 则 (1) 式的等价形式为 : y=dx+z (4) 从而通过 l1 极小化算法可重构原始信号 f = Dx [9,13-14]. 然而在现实世界中真实存在的数据还表现出诸多 1 收稿日期 : 基金项目 : 国家自然科学基金 (NO ). 作者简介 : 刘春燕 (1989 ), 女, 四川资阳人, 硕士研究生, 主要从事海量数据分析和压缩感知方面的研究. 通信作者 : 王建军, 教授.

2 2 西南大学学报 ( 自然科学版 ) htp://xbbjb swu cn 第 37 卷异于传统数据的其它结构, 比如多模态数据, 其子部分的形态各不相同. 这类数据的处理来自于很多应用问题, 如 : 声音数据处理神经生物学的图像数据处理 [17]. 从数学上讲, 任意信号 f R n 都可以被描述为 f =f1 +f2(f1 R n,f2 R n ), 文献 [16] 提出并研究了如下的 l1 极小化问题 : 其误差上限估计为 : (f1,f2)=arg min f1,f2 Rn D1 T f1 1 + D T 2f2 1s t f =f1 +f2 (5) D T 1J 1 cf1 1 + DT 2J 2 cf2 1 f1 -f1 2 + f2 -f μc 其中 μc <0 5, 且 μc 表示 D1,D2 关于索引集 J1,J2 的相互一致性. 为了方便表述, 我们首先给出以下记号. 1) 给定正整数 d,[d]={1,2,,d}, 记索引集 J [d]. 2) 给定正整数 [d], 记向量 x 的最优项逼近记 x c =x -x. x =arg min x-y 1 y 0 3) 记 () 2 =σ () max ( ) 表示矩阵的所有列子矩阵中的最大特征值. 4)DJ R n J 表示从 D 中取出索引集 J 对应的列所组成的矩阵,D1J 表示从矩阵 D1 中取出索引集 J 对应的列所组成的矩阵, 记 D T J =(DJ) T. 5) 记 K () = 1+δ,α = 2,r = x 1-δ 1-δ c 2 x 1 下面通过 3 类相对误差上限来量化矩阵 E 与噪音向量 e: E 2 ε 2,s = x c 1 x 1, 且 r,s 1. E () 2 ε () () 2 e 2 ε y y 2 其中 :ε ἐ () ἐ 表示相对误差上限 y ; 2, () 2, y 2 0;ε ἐ () ἐ y <1. 考虑数学问题 : 设 f =f1+f2(f1 R n,f2 R n ), 基于 f1,f2 的 l1 极小化的数据分离方法如下 [12] : (f1,f2)=arg min f1,f2 Rn D1 T f1 1 + D T 2f2 1s t (f1 +f2)-y 2 ε (6) 设线性测量 y= (f1 +f2)+z, R m n (m n) 是测量矩阵,z R m 是误差向量且 z 2 ε. 设 D1 R n d 1,D2 R n d 2 是两个紧框架, 则 f = D1D1 T f,f = D2D T 2 f, 对所有 f R n, 设令 d =d1 +d2 D =[D1 D2] φ = D1 0 ö f = f1 ö è 0 D2 èf2 则有 Dφ T f =f1 +f2, 从而问题 (6) 的等价问题为 : f =arg min φ T f 1s t Dφ T f -y 2 ε (7) f R2n 在一定条件下, 文献 [12] 获得了 (7) 式的部分扰动结果. 本文在 = +E 和加性噪音下, 研究了完全扰动的 l1 极小化问题, 即 : (f1,f2)=arg min D1T f1 1 + D 2f2 1s t T (f1 +f2)-y 2 ε,, y f1,f2 Rn 问题 (8) 的等价问题为 : f =arg min f R2n φ T f 1s t Dφ T f -y 2 ε,, y (8) (9)

3 第 9 期刘春燕, 等 : 冗余字典的扰动压缩数据分离 3 其中 : ε() = +E(E R m n K ()+ε α r 为的扰动矩阵 )ἐ,, y = 1-K () ( r +s) +ε ö y y 2 0 为全噪音 è 参数. 本文在上述完全扰动和冗余字典 D 下, 利用相互一致性和 RIP 条件研究了完全扰动 l1 (9), 获得了该问题的误差上限估计. 接下来给出本文的主要结果. 为此, 首先给出与本文内容相关的一些定义. 定义 1 ( -RIP) 设 δ(=1,2, ) 为矩阵的限制性等容常数, 对于任意 x R n, x 0, 满足 δ,max =(1+δ)(1+ε () )2-1 极小化问题 (1-δ ) x 2 2 x 2 2 (1+δ ) x 2 2 (10) 的最小常数 δ δ,max, 称为矩阵 = +E 的限制性等容常数 (RIC), 且称矩阵服从限制性等容性质 (RIP). 定义 2 ( -D-RIP) 设 δ(=1,2, ) 为矩阵的限制性等容常数,δ,max= (1+δ)(1+ε () )2-1, 对于任意 x R d, x 0, 满足 (1-δ ) Dx 2 2 Dx 2 2 (1+δ ) Dx 2 2 (11) 的最小常数 δ δ,max, 称为矩阵 = +E 的 D - 限制性等容常数 (D -RIC), 且称矩阵服从 D - 限制性等容性质 (D -RIP). 特别地, 类似于文献 [15] 的定理 1 可知定义 3 1- (1-δ)(1-ε () )2 δ (1+δ)(1+ε () )2-1 (12) 设 D1 =(d1i) 1 i d1,d2 =(d2j ) 1 j d 2,D1 与 D2 的相互一致性定义为 u1 =u1(d1;d2)=max d1i,d2j i,j 我们针对问题 (9), 获得了如下结果 : 定理 1 设 y=(f1 +f2)+z,d1 R n d 1,D2 R n d 2 是两个任意的紧框架,D =[D1 D2], φ = è D1 0 若 0 D2 ö,f = f1 ö, <b 4a( 其中,b,a 为正整数 ), 对于信号 f 满足 èf2 r +s < 1 K () u1(+a)(1-δ+a)(1-ε (+a) ) 2 +4ρ ( 1+δb)(1+ε (b) 2(1-ρ )2 (1+δ+a)(1+ε (+a) ) 2 < )2 + 4(1-ρ )2 (13) 其中 δ+a,δb 为的 D -RIP 常数,u1 为 D1,D2 的相互一致性常数, ρ = b, 则其中 C0,C1 为常数. φ T f - f -f 2 C0ε ( φ T f) 1,, y +C1 (14) 注 1 部分扰动情形 ( 即 E =0, 也即 ε =ε () =0,δ =δ) 下获得

4 4 西南大学学报 ( 自然科学版 ) htp://xbbjb swu cn 第 37 卷这与文献 [12] 的结果完全吻合. φ T f - f ( φ T f) 1 -f 2 C0ε+C1 注 2 考虑不同的划分 ( 即 a,b 的不同取法 ), 得到不同完全扰动恢复条件 : 1) 若 b=4,a=,0<ε (4) <0 01,δ4 <0 01,u1 <0 03, 则 φ T f - f -f 2 C0ε ( φ T f) 1,, y +C1 2) 若 b=8,a=2,0<ε (2) <0 01,δ8 <0 31,u1 <0 17, 则 φ T f - f -f 2 C0ε ( φ T f) 1,, y +C1 3) 若 b=8,a=2, =I,0<ε (3) <0 01,u1(1 +2)<0 16, 则 f1 -f1 2 + f2 -f2 2 C0ε,, y +C1 D T 1f 1 - (D T 1f 1 ) D T 2f 2 - (D T 2f 2 ) 注 3 信号重构速度受噪音和最佳项的控制, 特别地, 当 f 在 D 上为稀疏, 即在 φ T f=( φ T f) 和无噪音情形 (ε,, y =0) 下, 完美重构原始信号即 f =f. 定理 1 的证明设 h= f-f,f 是 (9) 式的解,f 是原始信号, φ T h= (x1,x2,,xd), 且设 φ T f 中前个是最大的值. 假设 x +1 x+2 xd, 设 J= J0 = {1,2,,} J = {+1,+2,,+a} Ji = {+a+ (i-1)b+1,,+a+ib} i= 1,2, 从而最后一个集合中的元素小于或者等于 b. 令 J0 = J0 J, 设 J 1 = J [d1] J 2 = {j-d1 j J\J 1 } 由于 D1,D2 为紧框架, 则 φ T φ =I, 从而 φ 也为紧框架. 那么, 我们有 : h 2 2 = φ T h 2 2 = φ T J 0 h φ T J0 c h 2 2 = D T 1J 1 0 h D T 2J 2 0 h φ T J0 c h 2 2 = h1,d1d 1J + h2,d2d 1 0 h1 T 1J h2 φ T J0 c h 2 2 h1 2 D1D T 1J 1 0 h1 2 + h2 2 D2DT 2J 2 0 h2 2 + φt J0 c h 2 2 h1 2 D1D T 1J 1 0 h1 2 + h2 2 D2DT 2J 2 0 h2 2 + ( i 1 φ T J i h ) 2 利用均值不等式可得, 即 h 2 2 c1 h D1D T 1J 1 0 h c1 + c1 h D2D T 2J 2 0 h c1 + ( i 1 φ T J i h ) 2 h 2 2 c1 h ( D1D T 1J 1 0 h D2D T 2J 2 0 h1 2 2)+ ( φ T J i h ) 2 (15) 2c1 i 1 为了获得 h 2 2 的上界, 下面我们估计 D1D T 1J 1 0 h D2D T 2J 2 0 h1 2 2 与 i 1 φ T J i h, [15] 由于 f 是可行解, 我们可得 Dφ T h 2 = Dφ T (f -f) 2 Dφ T f -y 2 + Dφ T f -y 2

5 第 9 期刘春燕, 等 : 冗余字典的扰动压缩数据分离 5 令 2ε,, y 由 (15),(16),(18) 式可得 i 1 ρ= b Dφ T J 0 h η= 2 φt J cf 1 φ T J i h 2 ρ ( h 2 +η ) ( 16) 1-δ +a [2ε,, y + 2ρ ( 1+δ b)( h 2 +η )]2 (17) D1D T 1J 1 0 h D2D T 2J 2 0 h2 2 2 u1(+a) h [2ε 2 1-δ,, y + 2ρ ( 1+δ b)( h 2 +η )]2 (18) +a h 2 2 c1 h ρ ( h 2 +η )2 + 1 u1(+a) h c1 è δ +a [2ε,, y + 2ρ ( 1+δ ö b)( h 2 +η )]2 = c1 (+a) 2 +u1 +ρ+ ρ( 1+δ b) ö 4c1 è c1(1-δ h (ε,,y ) 2 c1(1-δ +a) + ρ + ρ(1+δ b) ö è c1(1-δ η 2 + 2ρ ( 1+δ b) c1(1-δ +a) 2ε,,yη+ 2 ρ ( c1(1-δ +a) 2ε,,y h 2 + ρ+ ρ( 1+δ b) ö è c1(1-δ 2η h 2 c1 (+a) 2 +u1 +ρ+ ρ( 1+δ b) ö 4c1 è c1(1-δ h (ε,,y ) 2 c1(1-δ +a) + ρ + ρ(1+δ b) ö è c1(1-δ η 2 + 2ρ ( 1+δ b) ((ε c1(1-δ,, y )2 +η 2 )+ +a) 2ρ ( 1+δ b) (ε,,y ) 2 ö +c2 h 2 c1(1-δ 2 +a) è c2 + 合并 (19) 式得其中 ρ+ 2 ρ ( 1+δ b) ö è c1(1-δ è η2 c3 K1 h 2 2 K2(ε,, y )2 +K3η 2 ö +c3 h 2 2 (19)

6 6 西南大学学报 ( 自然科学版 ) htp://xbbjb swu cn 第 37 卷于是, (+a) K1 =1- c1 2 -u1 -ρ- ρ( 1+δ b) 2 ρ ( 4c1 c1(1-δ +a) -c2 c1(1-δ +a) -c3 ρ + ρ(1+δ b) ö è c1(1-δ K2 = 2 c1(1-δ +a) + 2 ρ ( c1(1-δ +a) + 2 ρ ( c1c2(1-δ +a) K3 =ρ+ ρ( 1+δ b) c1(1-δ +a) + 2 ρ ( c1(1-δ +a) + 1 ρ+ ρ( 1+δ b) ö c3 è c1(1-δ h 2 K2 K1 ε,, y + K3 η K1 K1 >0 为使 K1 >0, 需使 : c1 =c1 = (+a) u1 + 2 ρ ( 1+δ b) 2 1-δ +a c2 0 + c3 0 + 即利用 (12) 式, 我们有 u1(+a)(1-δ +a)+4ρδ b +2(1-ρ )2 δ +a <2(1-ρ )2-4ρ (20) 由 (20) 式可得定理结果. 综上, 定理 1 证毕. δ +a (1+δ+a)(1+ε (+a) ) 2-1 δ b (1+δb)(1+ε (b) )2-1 1-δ +a (1-δ+a)(1-ε (+a) ) 2 参考文献 : [1] NYQUIST H.CertainTopicsinTelegraphTransmissionTheory[J].mericanInstituteofElectricalEngineers,1928, 47(2): [2] CNDESE,ROMBERGJ,TO T.RobustUncertaintyPrinciples:ExactSignalReconstructionfrom HighlyIncomG pletefrequencyinformation [J].IEEETransactionsonInformationTheory,2006,52(2): [3] DONOHO D.CompressedSensing [J].IEEETransactionsonInformationTheory,2006,52(4): [4] BRNIUK RG.SingleGPixelImagingviaCompressiveSampling[J].IEEESiganlProcessingMagazine,2008,25(2): [5] LUSTIG M,DONOHO D,PULYJM.SparseMRI:ThepplicationofCompressedSensingforRapid MRImaging [J].MagneticResonancein Medicine,2007,58(6): [6] 王文东, 王尧, 王建军. 一类光滑加权块 l1 算法的收敛性分析与数值仿真实验 [J]. 西南大学学报 : 自然科学版, 2014,36(5): [7] WRIGHTJ,YNG Y,GNESH,etal.RobustFaceRecognitionviaSparseRepresentation [J].IEEE TransacG tionsonpaternnalysisand MachineInteligence,2009,31(2): [8] MJUMDR,WRDR.CompressedSensingofColorImages[J].SignalProcessing,2010,90(12): [9] CHENS,DONOHO DL,SUNDERSM.tomicDecompositionbyBasisPursuit[J].SIMJSciComp,1999,20 (1): [10]BRUCKSTEIN M,DONOHO DL,ELD M.FromSparseSolutionsofSystemsofEqnarraystoSparseModelingof SignalsandImages[J].SIM Rev,2009,51:34-81.

7 第 9 期刘春燕, 等 : 冗余字典的扰动压缩数据分离 7 [11]CNDESE,ELDSYC,NEEDELLD,etal.CompressedSensingwithCoherentandRedundantDictionaries[J].pG plcomputharmonnal,2011,31: [12]LINJH,LIS,SHEN Y.CompressedDataSeparationwithRedundantDictionaries[J].IEEETransactionsonInformaG tiontheory,2013,59(7): [13]ELD M,MILNFRP,RUBINSTEIN R.nalysisVersusSynthesisinSignalPriors [J].InverseProblem,2007, 23: [14]RUHUT H,SCHNSS K,VNDERGHEYNST P.CompressedSensingand RedundantDictionaries [J].IEEE TransInfTheory,2008,54(5): [15]HERMN M,STROHMER T.GeneralDeviants:an nalysisofperturbationsincompressedsensing [J].IEEE JournalofSelectedTopicsinSignalProcessing,4(2): [16]DONOHO D L,KUTYNIOK G.MicrolocalnalysisoftheGeometricSeparationProblem [J].CommunPureppl Math,2013,66:1-47. [17]CIJ,OSHERS,SHENZ.SplitBregman MethodsandFrameBasedImageRestoration [J].SiamJMultiscaleModel Simul,2009,8: CompressedDataSeparationofRedundant DictionariesofPerturbation LIU ChunGyan, ZHNG Jing, WNGJianGjun SchoolofMathematicsandStatistic,SouthwestUniversity,Chongqing400715,China bstract:compresseddataseparationisoneofthehotresearchtheoriesofsignalprocessing.underthe conditionthattheredundantdictionarysatisfiesamutualcoherenceandtheperturbationmatrixsatisfiesa restrictedisometryproperty,theauthorsofthispaperresearchcompresseddataseparationproblemsfor L1Gminimizationmethod,andachievetheperfectreconstructionoftheoriginalsignal. Keywords:compresseddataseparation;L1Gminimization;mutualcoherence;restrictedisometryproperty (RIP);tightframe;perturbation 责任编辑张栒

8 8 西南大学学报 ( 自然科学版 ) htp://xbbjb swu cn 第 37 卷

) & ( +,! (# ) +. + / & 6!!!.! (!,! (! & 7 6!. 8 / ! (! & 0 6! (9 & 2 7 6!! 3 : ; 5 7 6! ) % (. ()

) & ( +,! (# ) +. + / & 6!!!.! (!,! (! & 7 6!. 8 / ! (! & 0 6! (9 & 2 7 6!! 3 : ; 5 7 6! ) % (. () ! # % & & &! # % &! ( &! # )! ) & ( +,! (# ) +. + / 0 1 2 3 4 4 5 & 6!!!.! (!,! (! & 7 6!. 8 / 6 7 6 8! (! & 0 6! (9 & 2 7 6!! 3 : ; 5 7 6! ) % (. () , 4 / 7!# + 6 7 1 1 1 0 7!.. 6 1 1 2 1 3