OMP算法对稀疏信号准确重构的一个充分条件
|
摘要
压缩感知的研究对象是稀疏信号,那么在什么条件下以及采用何种方法能准确地重构一个稀疏信号自然成为人们关注的问题.在带有噪声的情形下,如果观测矩阵满足受限等距性质以及受限等距常数δk+kδk+1<1,并且噪声强度一定的条件下,证明了对任意的k-稀疏向量x,正交匹配追踪(OMP)算法可以通过k步迭代准确重构原信号.
Compressed sensing is often applied to sparse signals.Naturally,what the researchers are often concerned is whether a sparse signal can be recovered exactly under proper conditions and with proper methods.Here a noisy case is considered to show that if the compressed sensing matrix satisfies the restricted isometry property with restricted isometry constantδk+kδk+1<1and the noise is constrained,then a greedy algorithm called Orthogonal Matching Pursuit(OMP)can recover the signal with knonzero entries in kiterations.
Compressed sensing is often applied to sparse signals.Naturally,what the researchers are often concerned is whether a sparse signal can be recovered exactly under proper conditions and with proper methods.Here a noisy case is considered to show that if the compressed sensing matrix satisfies the restricted isometry property with restricted isometry constantδk+kδk+1<1and the noise is constrained,then a greedy algorithm called Orthogonal Matching Pursuit(OMP)can recover the signal with knonzero entries in kiterations.
引文
[1] LI Y Q,YU Z L,BI N,et al.Sparse representation for brain signal processing[J].IEEE Signal Processing Magazine,2014,31(3):96-106.
[2] LV J X,JIANG X,LI D,et al.Sparse representation of whole-brain FMRI signals for identification of functional networks[J].Medical Image Analysis,2015,20(1):112-134.
[3] DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[4] CANDES E J, ROMBERG J, TAO T.Stable signal recovery from incomplete and inaccurate measurements[J].Communications on Pure and Applied Mathematics,2006,59(8):1207-1223.
[5] ALBERT C,WOLFGANG D,RONALD D.Compressed sensing and best k-term approximation[J].Journal of the American Mathematical Society,2009,22(1):211-231.
[6] DONOHO D L,ELAD M.Optimally sparse representation in general(nonorthogonal)dictionaries via1minimization[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(5):2197-2202.
[7] GRIBONVAL R,NIELSEN M.Sparse decompositions in unions of bases[J].IEEE Transactions on Information Theory,2003,49(12):3320-3325.
[8] DONOHO D L,HUO X M.Uncertainty principles and ideal atomic decompositions[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.
[9] CANDES E J.The restricted isometry property and its implications for compressed sensing[J].Comptes Rendus de l'Académie des Sciences,Seris I,2008,346(9/10):589-592.
[10] CANDES E J,TAO T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2006,51(12):4203-4215.
[11] MALLAT S G,ZHANG Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.
[12] PATI Y,REZAIIFAR R,KRISHNAPRASAD P.Orthogonal matching pursuit:Recursive function approximation with application to wavelet decomposition[C].Proceedings of 27th Asilomar Conference on Signals,Systems and Computers.Pacific Grove,CA,USA:IEEE Computer Society Press,1993:40-44.
[13] NEEDELL D,TROPP J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2008,26(3):301-321.
[14] BLUMENSATH T,DAVIES M.Iterative hard thresholding for compressed sensing[J].Applied and Computational Harmonic Analysis,2009,27(3):265-274.
[15] DAUBECHIES I,DEVORE R,FORNASIER M.Güntürk C S.Iteratively reweighted least squares minimization for sparse recovery[J].Communications on Pure and Applied Mathematics,2010,63(1):1-38.
[16] TROPP J A.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.
[17] MO Q,SHEN Y.A remark on the restricted isometry property in orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2012,58(6):3654-3656.
[18] FOUCART S,RAUHUT H.A mathematical introduction to compressive sensing[M].New York,USA:Springer,2013.
[19] SHEN Y,LI S.Sparse signals recovery from noisy measurements by orthogonal matching pursuit[J].Inverse Problems&Imaging,2015,9(1):231-238.
[2] LV J X,JIANG X,LI D,et al.Sparse representation of whole-brain FMRI signals for identification of functional networks[J].Medical Image Analysis,2015,20(1):112-134.
[3] DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[4] CANDES E J, ROMBERG J, TAO T.Stable signal recovery from incomplete and inaccurate measurements[J].Communications on Pure and Applied Mathematics,2006,59(8):1207-1223.
[5] ALBERT C,WOLFGANG D,RONALD D.Compressed sensing and best k-term approximation[J].Journal of the American Mathematical Society,2009,22(1):211-231.
[6] DONOHO D L,ELAD M.Optimally sparse representation in general(nonorthogonal)dictionaries via1minimization[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(5):2197-2202.
[7] GRIBONVAL R,NIELSEN M.Sparse decompositions in unions of bases[J].IEEE Transactions on Information Theory,2003,49(12):3320-3325.
[8] DONOHO D L,HUO X M.Uncertainty principles and ideal atomic decompositions[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.
[9] CANDES E J.The restricted isometry property and its implications for compressed sensing[J].Comptes Rendus de l'Académie des Sciences,Seris I,2008,346(9/10):589-592.
[10] CANDES E J,TAO T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2006,51(12):4203-4215.
[11] MALLAT S G,ZHANG Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.
[12] PATI Y,REZAIIFAR R,KRISHNAPRASAD P.Orthogonal matching pursuit:Recursive function approximation with application to wavelet decomposition[C].Proceedings of 27th Asilomar Conference on Signals,Systems and Computers.Pacific Grove,CA,USA:IEEE Computer Society Press,1993:40-44.
[13] NEEDELL D,TROPP J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2008,26(3):301-321.
[14] BLUMENSATH T,DAVIES M.Iterative hard thresholding for compressed sensing[J].Applied and Computational Harmonic Analysis,2009,27(3):265-274.
[15] DAUBECHIES I,DEVORE R,FORNASIER M.Güntürk C S.Iteratively reweighted least squares minimization for sparse recovery[J].Communications on Pure and Applied Mathematics,2010,63(1):1-38.
[16] TROPP J A.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.
[17] MO Q,SHEN Y.A remark on the restricted isometry property in orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2012,58(6):3654-3656.
[18] FOUCART S,RAUHUT H.A mathematical introduction to compressive sensing[M].New York,USA:Springer,2013.
[19] SHEN Y,LI S.Sparse signals recovery from noisy measurements by orthogonal matching pursuit[J].Inverse Problems&Imaging,2015,9(1):231-238.