一般对偶框架下基于lp(0
2015-06-09吴焚供张然然覃耀海钟彭洪
中山大学学报(自然科学版)(中英文) 2015年6期吴焚供，张然然，覃耀海，钟彭洪
(广东第二师范学院数学系，广东 广州 510303)
一般对偶框架下基于lp(0吴焚供，张然然，覃耀海，钟彭洪
(广东第二师范学院数学系，广东 广州 510303)
压缩感知理论指出，只要信号是可压缩的或稀疏的，就能以较低的频率采样信号，并能高概率的重构该信号。在实际的应用中, 许多信号只能在某些框架下具有稀疏表示，而无法在正交基下获得稀疏表示。针对这一类信号的恢复，一般采取的是l1-analysis方法。近期有些相关研究考虑了一般对偶框架下基于l1-analysis方法的信号恢复问题，在比前期l1-analysis方法更弱的条件下得到了更好的恢复结果。受此启发，我们考虑了一般对偶框架下，基于lp(0压缩感知；信号恢复；框架；对偶框架；l1-analysis
压缩感知所考虑的问题是如何将一个高维稀疏信号从数目不大的一组测量数据
y=Af+z
中恢复出来，其中A是m×n的测量矩阵，且m<一般情况下，考虑的信号f是在一组正交基下具有稀疏的 (或近乎稀疏的)表示，或者更一般的
情况，f本身便是稀疏的 (或近乎稀疏的)。如果测量矩阵A满足限制等距性质(RestrictedIsometryproperty)的条件(参考文[6-11])，则稀疏信号f可以通过求解如下的lp-最小化问题
得到精确的 (或者误差很小的) 恢复，这里p∈(0,1]。向量u∈Rn的lp-范数定义为
然而在信号处理的实际应用中，越来越多的情况所涉及的信号f是在一个框架 (或过完备字典) 下是稀疏的，而不是在一个标准正交基下稀疏的。我们说矩阵D∈Rn×d(n
本文中我们要研究的信号f就是在某个框架D下是稀疏的。即f=Dx,x∈Rd为稀疏向量。此时对f的相应测量数据变成
y=ADx+z
由于x是稀疏的，一种直接恢复f的方法很自然的被考虑到，即l1-synthesis(参考文[12-14])。该方法首先通过求解如下的l1-最小化问题
另外一种可以代替l1-synthesis的方法是l1-analysis(参考文[14,18-19])。这个方法是通过求解如下l1最小化问题：
(1)
(2)
(3)
(4)
受文[20]的启发，考虑了一般对偶框架下，基于lp(0
(5)
采用新的方法，并得到了相应的理论结果。
1 记号与定义
另记T01=T0∪T1，D*h(t)表示D*h的第t个元素。
下面对本文中常用到的概念给出具体的定义。
定义2[22]设测量矩阵A∈Rm×n，称A满足常数为γs∈(0,1)的s阶RIP性质，如果对所有的s阶稀疏的信号v，总成立
定义3[14]设D∈Rn×d为一框架，Σs为Rd中所有s阶稀疏的向量之集，测量矩阵A满足常数为δs的D-RIP性质，是指
对所有的u∈Σs都成立。
2 引理和主要结果
在给出主要结果前，我们先给出如下两个有用的引理。
抓好做实企业基层思想政治工作是一门大学问，如何灵活应用适当的方法，对确保思想政治工作的实效性至关重要。毛泽东曾以“过河”是用“桥”或“船”的问题作过生动比喻，深刻地说明了工作方式方法的重要性。
两边开p次方后再平方，得
对t∈Tj求和，得
两边开平方再乘p次方，得
对全体的j∈{1,2,…,l-1}求和，有
则问题 (5) 的解与原始信号满足
其中C1,C2为常数。
(7)
因为
由引理1可得
结合引理2，有
(8)
(9)
结合(7)-(9)式，可得
其中
证完。
[1]CANDSEJ,TAOT.Nearoptimalsignalrecoveryfromrandomprojections:Universalencodingstrategies? [J].IEEETransactionsonInformationTheory, 2006, 52: 5406-5425.
[2]CANDSEJ,ROMBERGJ,TAOT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactiononInformationTheory, 2006, 52: 489-509.
[3]CANDSEJ.Compressivesampling[J].InternationalCongressMathematicians, 2006, 3: 1433-1452.
[4]DONOHODL.Compressedsensing[J].IEEETransactionsonInformationTheory, 2006, 52: 1289-1306.
[5]DONOHODL,ELADM,TEMLYAKOVVN.Stablerecoveryofsparseovercompleterepresentationsinthepresenceofnoise[J].IEEETransactionsonInformationTheory, 2006, 52: 6-18.
[6]CHARTRANDR,STANEVAV.Restrictedisometrypropertiesandnonconvexcompressivesensing[J].InverseProblem, 2008, 24: 035020.
[7]FOUCARTS,LAIMJ.Sparsestsolutionsofunderdeterminedlinearsystemsvialq-minimization for 0[8]SAABR,CHARTRANDR,YILMAZO.Stablesparseapproximationsvianonconvexoptimization[C]∥IEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing, 2008: 3885-3888.
[9]SHENY,LIS.Restrictedp-isometrypropertyanditsapplicationfornonconvexcompressivesensing[J].AdvancesinComputationalMathematics, 2012, 37(3): 441-452.
[10]DAVIESME,GRIBONVALR.Restrictedisometryconstantswherelpsparserecoverycanfailfor0[11]CANDSEJ.Therestrictedisometrypropertyanditsimplicationsforcompressedsensing[J].ComptesRendusMathematique, 2008, 346(9/10): 589-592.
[12]CHENSS,DONOHODL,SAUNDERSMA.Atomicdecompositionbybasispursuit[J].SIAMReview, 2001, 43: 129-159.
[13]ELADM,MILANFARP,RUBINSTEINR.Analysisversussynthesisinsignalpriors[J].InverseProblem, 2007, 23: 947-968.
[14]CANDSEJ,ELDARYC,NEEDELLD,etal.Compressedsensingwithcoherentandredundantdictionaries[J].AppliedandComputationalHarmonicAnalysis, 2011, 31(1): 59-73.
[15]RAUHUTH,SCHNASSANDK,VANDERGHEYNSTP.Compressedsensingandredundantdictionaries[J].IEEETransactionsonInformationTheory, 2008, 54: 2210-2219.
[16]TROPPJA.Greedisgood:Algorithmicresultsforsparseapproximation[J].IEEETransactionsonInformationTheory, 2004, 50: 2231-2242.
[17]BAJWAWU,CALDERBANKR,JAFARPOURS.WhyGaborframes?Twofundamentalmeasuresofcoherenceandtheirgeometricsignificance[J].CoRR, 2009, 01.http:∥arxiv.org/abs/0911.2746.
[18]ELADM,STARCKJL,QUERREP,etal.Simultaneouscartoonandtextureimageinpaintingusingmorphologicalcomponentanalysis(MCA) [J].AppliedComputationalHarmonicAnalysis, 2005, 19: 340-358.
[19]ELADM,MILANFARP,RUBINSTEINR.Analysisversussynthesisinsignalpriors[J].InverseProblem, 2007, 23: 947-968.
[20]LIUY,MIT，LIS.Compressedsensingwithgeneralframesviaoptimal-dual-basedl1-analysis[J].IEEETransactionsonInformationTheory, 2012, 58(7): 4201-4214.
[21] 曲文长，何友，刘卫华，等. 框架理论及应用[M]. 北京：国防工业出版社, 2009.
[22]CANDSEJ,TAOT.Decodingbylinearprogramming[J].IEEETransactionsonInformationTheory, 2005, 51: 4203-4215.
Stable Signal Recovery with Dual Frames vialp-Minimization for0WUFengong,ZHANGRanran,QINYaohai,ZHONGPenghong
(Department of Mathematics, Guangdong University of Education, Guangzhou 510303, China)
The theory of compressed sensing points out that, sparse (or compressible) signals can be reconstructed with high probability by lower sampling frequency. In more and more practical applications, many signals are sparse or approximately sparse in terms of some frames rather than orthonormal bases. In such settings, one approach to recover the signals is known asl1-analysis.Somerecentstudyusingalternativedualframesasanalysisoperators,andprovideaweakerconditionthanexistingresultsintheliterature.Inspiredbythis,therecoveryofsuchkindofsignalswithgeneraldualframevialp-minimization(0compressed sensing; signal recovery; frame; dual frame;l1-analysis
10.13471/j.cnki.acta.snus.2015.06.009
2015-04-21 基金项目：广东省高等学校优秀青年教师培养计划资助项目(Yq20145084602)；国家自然科学基金数学天元基金资助项目(11426068)
吴焚供(1980年生)，男；研究方向：最优化算法理论；E-mail:wufngong@gdei.edu.cn
TN
A
0529-6579(2015)06-0046-04
猜你喜欢
杂志排行
2015-06-09吴焚供张然然覃耀海钟彭洪
吴焚供，张然然，覃耀海，钟彭洪
(广东第二师范学院数学系，广东 广州 510303)
一般对偶框架下基于lp(0 吴焚供，张然然，覃耀海，钟彭洪 (广东第二师范学院数学系，广东 广州 510303) 压缩感知理论指出，只要信号是可压缩的或稀疏的，就能以较低的频率采样信号，并能高概率的重构该信号。在实际的应用中, 许多信号只能在某些框架下具有稀疏表示，而无法在正交基下获得稀疏表示。针对这一类信号的恢复，一般采取的是l1-analysis方法。近期有些相关研究考虑了一般对偶框架下基于l1-analysis方法的信号恢复问题，在比前期l1-analysis方法更弱的条件下得到了更好的恢复结果。受此启发，我们考虑了一般对偶框架下，基于lp(0 压缩感知；信号恢复；框架；对偶框架；l1-analysis 压缩感知所考虑的问题是如何将一个高维稀疏信号从数目不大的一组测量数据 y=Af+z 中恢复出来，其中A是m×n的测量矩阵，且m< 一般情况下，考虑的信号f是在一组正交基下具有稀疏的 (或近乎稀疏的)表示，或者更一般的 情况，f本身便是稀疏的 (或近乎稀疏的)。如果测量矩阵A满足限制等距性质(RestrictedIsometryproperty)的条件(参考文[6-11])，则稀疏信号f可以通过求解如下的lp-最小化问题 得到精确的 (或者误差很小的) 恢复，这里p∈(0,1]。向量u∈Rn的lp-范数定义为 然而在信号处理的实际应用中，越来越多的情况所涉及的信号f是在一个框架 (或过完备字典) 下是稀疏的，而不是在一个标准正交基下稀疏的。我们说矩阵D∈Rn×d(n 本文中我们要研究的信号f就是在某个框架D下是稀疏的。即f=Dx,x∈Rd为稀疏向量。此时对f的相应测量数据变成 y=ADx+z 由于x是稀疏的，一种直接恢复f的方法很自然的被考虑到，即l1-synthesis(参考文[12-14])。该方法首先通过求解如下的l1-最小化问题 另外一种可以代替l1-synthesis的方法是l1-analysis(参考文[14,18-19])。这个方法是通过求解如下l1最小化问题： (1) (2) (3) (4) 受文[20]的启发，考虑了一般对偶框架下，基于lp(0 (5) 采用新的方法，并得到了相应的理论结果。 另记T01=T0∪T1，D*h(t)表示D*h的第t个元素。 下面对本文中常用到的概念给出具体的定义。 定义2[22]设测量矩阵A∈Rm×n，称A满足常数为γs∈(0,1)的s阶RIP性质，如果对所有的s阶稀疏的信号v，总成立 定义3[14]设D∈Rn×d为一框架，Σs为Rd中所有s阶稀疏的向量之集，测量矩阵A满足常数为δs的D-RIP性质，是指 对所有的u∈Σs都成立。 在给出主要结果前，我们先给出如下两个有用的引理。 抓好做实企业基层思想政治工作是一门大学问，如何灵活应用适当的方法，对确保思想政治工作的实效性至关重要。毛泽东曾以“过河”是用“桥”或“船”的问题作过生动比喻，深刻地说明了工作方式方法的重要性。 两边开p次方后再平方，得 对t∈Tj求和，得 两边开平方再乘p次方，得 对全体的j∈{1,2,…,l-1}求和，有 则问题 (5) 的解与原始信号满足 其中C1,C2为常数。 (7) 因为 由引理1可得 结合引理2，有 (8) (9) 结合(7)-(9)式，可得 其中 证完。 [1]CANDSEJ,TAOT.Nearoptimalsignalrecoveryfromrandomprojections:Universalencodingstrategies? [J].IEEETransactionsonInformationTheory, 2006, 52: 5406-5425. [2]CANDSEJ,ROMBERGJ,TAOT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactiononInformationTheory, 2006, 52: 489-509. [3]CANDSEJ.Compressivesampling[J].InternationalCongressMathematicians, 2006, 3: 1433-1452. [4]DONOHODL.Compressedsensing[J].IEEETransactionsonInformationTheory, 2006, 52: 1289-1306. [5]DONOHODL,ELADM,TEMLYAKOVVN.Stablerecoveryofsparseovercompleterepresentationsinthepresenceofnoise[J].IEEETransactionsonInformationTheory, 2006, 52: 6-18. [6]CHARTRANDR,STANEVAV.Restrictedisometrypropertiesandnonconvexcompressivesensing[J].InverseProblem, 2008, 24: 035020. [7]FOUCARTS,LAIMJ.Sparsestsolutionsofunderdeterminedlinearsystemsvialq-minimization for 0 [8]SAABR,CHARTRANDR,YILMAZO.Stablesparseapproximationsvianonconvexoptimization[C]∥IEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing, 2008: 3885-3888. [9]SHENY,LIS.Restrictedp-isometrypropertyanditsapplicationfornonconvexcompressivesensing[J].AdvancesinComputationalMathematics, 2012, 37(3): 441-452. [10]DAVIESME,GRIBONVALR.Restrictedisometryconstantswherelpsparserecoverycanfailfor0 [11]CANDSEJ.Therestrictedisometrypropertyanditsimplicationsforcompressedsensing[J].ComptesRendusMathematique, 2008, 346(9/10): 589-592. [12]CHENSS,DONOHODL,SAUNDERSMA.Atomicdecompositionbybasispursuit[J].SIAMReview, 2001, 43: 129-159. [13]ELADM,MILANFARP,RUBINSTEINR.Analysisversussynthesisinsignalpriors[J].InverseProblem, 2007, 23: 947-968. [14]CANDSEJ,ELDARYC,NEEDELLD,etal.Compressedsensingwithcoherentandredundantdictionaries[J].AppliedandComputationalHarmonicAnalysis, 2011, 31(1): 59-73. [15]RAUHUTH,SCHNASSANDK,VANDERGHEYNSTP.Compressedsensingandredundantdictionaries[J].IEEETransactionsonInformationTheory, 2008, 54: 2210-2219. [16]TROPPJA.Greedisgood:Algorithmicresultsforsparseapproximation[J].IEEETransactionsonInformationTheory, 2004, 50: 2231-2242. [17]BAJWAWU,CALDERBANKR,JAFARPOURS.WhyGaborframes?Twofundamentalmeasuresofcoherenceandtheirgeometricsignificance[J].CoRR, 2009, 01.http:∥arxiv.org/abs/0911.2746. [18]ELADM,STARCKJL,QUERREP,etal.Simultaneouscartoonandtextureimageinpaintingusingmorphologicalcomponentanalysis(MCA) [J].AppliedComputationalHarmonicAnalysis, 2005, 19: 340-358. [19]ELADM,MILANFARP,RUBINSTEINR.Analysisversussynthesisinsignalpriors[J].InverseProblem, 2007, 23: 947-968. [20]LIUY,MIT，LIS.Compressedsensingwithgeneralframesviaoptimal-dual-basedl1-analysis[J].IEEETransactionsonInformationTheory, 2012, 58(7): 4201-4214. [21] 曲文长，何友，刘卫华，等. 框架理论及应用[M]. 北京：国防工业出版社, 2009. [22]CANDSEJ,TAOT.Decodingbylinearprogramming[J].IEEETransactionsonInformationTheory, 2005, 51: 4203-4215. Stable Signal Recovery with Dual Frames vialp-Minimization for0 WUFengong,ZHANGRanran,QINYaohai,ZHONGPenghong (Department of Mathematics, Guangdong University of Education, Guangzhou 510303, China) The theory of compressed sensing points out that, sparse (or compressible) signals can be reconstructed with high probability by lower sampling frequency. In more and more practical applications, many signals are sparse or approximately sparse in terms of some frames rather than orthonormal bases. In such settings, one approach to recover the signals is known asl1-analysis.Somerecentstudyusingalternativedualframesasanalysisoperators,andprovideaweakerconditionthanexistingresultsintheliterature.Inspiredbythis,therecoveryofsuchkindofsignalswithgeneraldualframevialp-minimization(0 compressed sensing; signal recovery; frame; dual frame;l1-analysis 10.13471/j.cnki.acta.snus.2015.06.009 2015-04-21 基金项目：广东省高等学校优秀青年教师培养计划资助项目(Yq20145084602)；国家自然科学基金数学天元基金资助项目(11426068) 吴焚供(1980年生)，男；研究方向：最优化算法理论；E-mail:wufngong@gdei.edu.cn TN A 0529-6579(2015)06-0046-041 记号与定义
2 引理和主要结果
