基于稀疏表示理论的优化算法综述
|
摘要
近年来,稀疏表示理论在信号处理、图像处理和计算机视觉等领域引起了广泛关注。很多研究人员提出了基于稀疏模型的算法,从不同视角对稀疏表示进行分类,如稀疏约束中使用的不同范数的方法可分为l_0范数最小化、l_p范数(0 In recent years, sparse representation has attracted wide attention in fields of signal processing, image processing and computer vision. Many researchers have proposed different algorithms based on sparse model. The taxonomy of sparse representation methods can be studied from various viewpoints. For example, in terms of different norm minimizations used in sparsity constraints. The methods can be roughly categorized into five groups: sparse representation with l_0-norm minimization; sparse representation with l_p-norm(0
引文
[1] Hubel D H,Wiesel T N.Receptive Fields of Single Neurons in the Cat’s Striate Cortex[J].The Journal of Physiology,1959,148(3):574-591
[2] Field D J.Relations Between the Statistics of Natural Images and the Response Properties of Cortical Cells[J].Journal of the Optical Society of America (A,Optics and Image Science),1987,4(12):2 379-2 394
[3] Olshausen B A,Field D J.Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural Images[J].Nature,1996,381(6 583):607-609
[4] Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52(4):1 289-1 306
[5] Candès E J,Romberg J,Tao T.Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].IEEE Transactions on Information Theory,2006,52(2):489-509
[6] Elad M.Sparse and Redundant Representations:From Theory to Applications in Signal and Image Processing[M].New York,USA:Springer,2010
[7] Wright J,Ma Y,Mairal J,et al.Sparse Representation for Computer Vision and Pattern Recognition[J].Proceedings of the IEEE,2010,98(6):1 031-1 044
[8] Elad M,Figueiredo M A T,Ma Y.On the Role of Sparse and Redundant Representations in Image Processing[J].Proceedings of the IEEE,2010,98(6):972-982
[9] 张良培,李家艺.高光谱图像稀疏信息处理综述与展望[J].遥感学报,2016,20(5):1 091-1 101
[10] 刘帆,裴晓鹏,张静,等.基于优化字典学习的遥感图像融合方法[J].电子与信息学报,2018,40(12):2 804-2 811
[11] 李丽,隋立春,康军梅,等.非参数贝叶斯字典学习的遥感影像超分辨率重建[J].测绘通报,2018(7):5-8
[12] Tropp J A,Gilbert A C.Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4 655-4 666
[13] Tibshirani R.Regression Shrinkage and Selection via the Lasso[J].Journal of the Royal Statistical Society (Series B):Methodological,1996,58(1):267-288
[14] Saab R,Chartrand R,Yilmaz O.Stable Sparse Approximations via Nonconvex Optimization[C].2008 IEEE International Conferenceon Acoustics,Speech and Signal Processing,Las Vegas,USA,2008
[15] Chartrand R.Exact Reconstruction of Sparse Signals via Nonconvex Minimization[J].IEEE Signal Processing Letters,2007,14(10):707-710
[16] Xu Zongben.Data Modeling:Visual Psychology Approach and l2,1 Regularization Theory[C].International Congress of Mathematicians,Hyderabad,India,2010
[17] Shi Xiaoshuang,Yang Yujiu,Guo Zhenhua,et al.Face Recognition by Sparse Discriminant Analysis via Joint l2,1-Norm Minimization[J].Pattern Recognition,2014,47(7):2 447-2 453
[18] Nie Feiping,Huang Heng,Cai Xiao,et al.Efficient and Robust Feature Selection via Joint l2,1-Norms Minimization[C].Advances in Neural Information Processing Systems,Vancouver,Canada,2010
[19] Yang Yi,Shen Hengtao,Ma Zhigang,et al.l2,1-Norm Regularized Discriminative Feature Selection for Unsupervised Learning[C].The Twenty-Second International Joint Conference on Artificial Intelligence,Barcelona,Spain,2011
[20] Liu Jun,Ji Shuiwang,Ye Jieping.Multi-task Feature Learning via Efficient l2,1-Norm Minimization [C].The Twenty-Fifth Conference on Uncertainty in Artificial Intelligence,Montreal,Canada,2009
[21] Hou Chenping,Nie Feiping,Li Xuelong,et al.Joint Embedding Learning and Sparse Regression:A Framework for Unsupervised Feature Selection[J].IEEE Transactions on Cybernetics,2014,44(6):793-804
[22] Naseem I,Togneri R,Bennamoun M.Linear Regression for Face Recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(11):2 106-2 112
[23] Zhang Lei,Yang Meng,Feng Xiangchu.Sparse Representation or Collaborative Representation:Which Helps Face Recognition[C].2011 IEEE International Conference on Computer Vision,Barcelona,Spain,2011
[24] Xu Y,Zhang D,Yang J,et al.A Two-Phase Test Sample Sparse Representation Method for Use with Face Recognition[J].IEEE Transactions on Circuits and Systems for Video Technology,2011,21(9):1 255-1 262
[25] Donoho D L,Elad M.Optimally Sparse Representation in General (Non-orthogonal) Dictionaries via l1 Minimization[J].Proceedings of the National Academy of Sciences,2003,100(5):2 197-2 202
[26] Amaldi E,Kann V.On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems[J].Theoretical Computer Science,1998,209(1/2):237-260
[27] Donoho D L.For Most Large Underdetermined Systems of Equations,the Minimal l1-Norm Near-Solution Approximates the Sparsest Near-Solution[J].Communications on Pure and Applied Mathematics,2006,59(6):907-934
[28] Candès E J,Romberg J K,Tao T.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics,2006,59(8):1 207-1 223
[29] Candès E J,Tao T.Near-Optimal Signal Recovery from Random Projections:Universal Encoding Strategies[J].IEEE Transactions on Information Theory,2006,52(12):5 406-5 425
[30] Lyu Qin,Lin Zhouchen,She Yiyuan,et al.A Comparison of Typical lp Minimization Algorithms[J].Neurocomputing,2013,119:413-424
[31] Zhang Zheng,Wang Long,Zhu Qi,et al.Noise Mode-ling and Representation Based Classification Methods for Face Recognition[J].Neurocomputing,2015,148:420-429
[32] Tropp J A,Gilbert A C,Strauss M J.Algorithms for Simultaneous Sparse Approximation (Part I:Greedy Pursuit)[J].IEEE Transactions on Signal Processing,2006,86(3):572-588
[33] Mallat S G,Zhang Z.Matching Pursuits with Time-Frequency Dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3 397-3 415
[34] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal Matching Pursuit:Recursive Function Approximation with Applications to Wavelet Decomposition[C].The 27th Asilomar Conference on Signals,Systems and Computers,Pacific Grove,CA,USA,1993
[35] Donoho D L,Tsaig Y,Drori I,et al.Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2012,58(2):1 094-1 121
[36] Dai W,Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2 230-2 249
[37] Do T T,Gan L,Nguyen N,et al.Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C].Asilomar Conference on Signals,Systems and Computers,Pacific Grove,CA,USA,2008
[38] Jost P,Vandergheynst P,Frossard P.Tree-Based Pursuit:Algorithm and Properties[J].IEEE Transactions on Signal Processing,2006,54(12):4 685-4 697
[39] La C,Do M N.Tree-Based Orthogonal Matching Pursuit Algorithm for Signal Reconstruction[C].2006 International Conference on Image Processing,Atlanta,USA,2006
[40] Fadili M J,Starck J L,Murtagh F.Inpainting and Zooming Using Sparse Representations[J].The Computer Journal,2009,52(1):64-79
[41] Xu Zongben,Sun Jian.Image Inpainting by Patch Propagation Using Patch Sparsity[J].IEEE Transactions on Image Processing,2010,19(5):1 153-1 165
[42] Li Zhidan,He Hongjie,Yin Zhongke,et al.A Color-Gradient Patch Sparsity Based Image Inpainting Algorithm with Structure Coherence and Neighborhood Consistency[J].IEEE Transactions on Signal Processing,2014,99(6):116-128
[43] Li Zhidan,He Hongjie,Tai Hengming,et al.Color-Direction Patch-Sparsity-Based Image Inpainting Using Multidirection Features[J].IEEE Transactions on Image Processing,2015,24(3):1 138-1 152
[44] Figueiredo M A T,Nowak R D,Wright S J.Gradient Projection for Sparse Reconstruction:Application to Compressed Sensing and Other Inverse Problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-597
[45] Boyd S,Vandenberghe L,Faybusovich L.Convex Optimization[J].IEEE Transactions on Automatic Control,2006,51 (11):1 859-1 859
[46] Boyd S,Parikh N,Chu E,et al.Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[M].Oxford,England:Oxford University Press,2011
[47] Portugal L F,Resende M G C,Veiga G,et al.A Truncated Primal-Infeasible Dual-Feasible Network Interior Point Method[J].Networks,2000,35(2):91-108
[48] Koh K,Kim S J,Boyd S.An Interior-Point Method for Large-Scale l1-Regularized Logistic Regression[J].Journal of Machine Learning Research,2007,8:1 519-1 555
[49] Figueiredo M A T,Nowak R D.A Bound Optimization Approach to Wavelet-Based Image Deconvolution[C].IEEE International Conference on Image Processing,Genova,Italy,2005
[50] Beck A,Teboulle M.A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[J].SIAM Journal on Imaging Sciences,2009,2(1):183-202
[51] Zeng Jinshan,Lin Shaobo,Wang Yao,et al.l1/2 Regularization:Convergence of Iterative Half Thresholding Algorithm[J].IEEE Transactions on Signal Processing,2014,62(9):2 317-2 329
[52] Elad M,Matalon B,Zibulevsky M.Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization[J].Applied and Computational Harmonic Analysis,2007,23(3):346-367
[53] Donoho D L,Maleki A,Montanari A.Message-Passing Algorithms for Compressed Sensing[J].Proceedings of the National Academy of Sciences of the United States of America,2009,106(45):18 914-18 919
[54] Becker S R,Bobin J,Candès E J.NESTA:A Fast and Accurate First-Order Method for Sparse Recovery[J].SIAM Journal on Imaging Sciences,2011,4(1):1-39
[55] Becker S,Candès E J,Grant M C.Templates for Convex Cone Problems with Applications to Sparse Signal Recovery[J].Mathematical Programming Computation,2011,3(3):165-218
[56] Osborne M R,Presnell B,Turlach B A.A New Approach to Variable Selection in Least Squares Problems[J].IMA Journal of Numerical Analysis,2000,20(3):389-403
[57] Yang Junfeng,Zhang Yin.Alternating Direction Algorithms for l1-Problems in Compressive Sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278
[58] Plumbley M D.Recovery of Sparse Representations by Polytope Faces Pursuit[C].The 6th International Conference on Independent Component Analysis and Blind Signal Separation,Berlin,Germany,2006
[59] Donoho D L,Tsaig Y.Fast Solution of l1-Norm Minimization Problems when the Solution May Be Sparse[J].IEEE Transactions on Information Theory,2008,54(11):4 789-4 812
[60] Efron B,Hastie T,Johnstone I,et al.Least Angle Regression[J].The Annals of Statistics,2004,32(2):407-499
[61] Asif M S,Romberg J.Fast and Accurate Algorithms for Re-Weighted l1-Norm Minimization[J].IEEE Transactions on Signal Processing,2012,61(23):5 905-5 916
[2] Field D J.Relations Between the Statistics of Natural Images and the Response Properties of Cortical Cells[J].Journal of the Optical Society of America (A,Optics and Image Science),1987,4(12):2 379-2 394
[3] Olshausen B A,Field D J.Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural Images[J].Nature,1996,381(6 583):607-609
[4] Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52(4):1 289-1 306
[5] Candès E J,Romberg J,Tao T.Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].IEEE Transactions on Information Theory,2006,52(2):489-509
[6] Elad M.Sparse and Redundant Representations:From Theory to Applications in Signal and Image Processing[M].New York,USA:Springer,2010
[7] Wright J,Ma Y,Mairal J,et al.Sparse Representation for Computer Vision and Pattern Recognition[J].Proceedings of the IEEE,2010,98(6):1 031-1 044
[8] Elad M,Figueiredo M A T,Ma Y.On the Role of Sparse and Redundant Representations in Image Processing[J].Proceedings of the IEEE,2010,98(6):972-982
[9] 张良培,李家艺.高光谱图像稀疏信息处理综述与展望[J].遥感学报,2016,20(5):1 091-1 101
[10] 刘帆,裴晓鹏,张静,等.基于优化字典学习的遥感图像融合方法[J].电子与信息学报,2018,40(12):2 804-2 811
[11] 李丽,隋立春,康军梅,等.非参数贝叶斯字典学习的遥感影像超分辨率重建[J].测绘通报,2018(7):5-8
[12] Tropp J A,Gilbert A C.Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4 655-4 666
[13] Tibshirani R.Regression Shrinkage and Selection via the Lasso[J].Journal of the Royal Statistical Society (Series B):Methodological,1996,58(1):267-288
[14] Saab R,Chartrand R,Yilmaz O.Stable Sparse Approximations via Nonconvex Optimization[C].2008 IEEE International Conferenceon Acoustics,Speech and Signal Processing,Las Vegas,USA,2008
[15] Chartrand R.Exact Reconstruction of Sparse Signals via Nonconvex Minimization[J].IEEE Signal Processing Letters,2007,14(10):707-710
[16] Xu Zongben.Data Modeling:Visual Psychology Approach and l2,1 Regularization Theory[C].International Congress of Mathematicians,Hyderabad,India,2010
[17] Shi Xiaoshuang,Yang Yujiu,Guo Zhenhua,et al.Face Recognition by Sparse Discriminant Analysis via Joint l2,1-Norm Minimization[J].Pattern Recognition,2014,47(7):2 447-2 453
[18] Nie Feiping,Huang Heng,Cai Xiao,et al.Efficient and Robust Feature Selection via Joint l2,1-Norms Minimization[C].Advances in Neural Information Processing Systems,Vancouver,Canada,2010
[19] Yang Yi,Shen Hengtao,Ma Zhigang,et al.l2,1-Norm Regularized Discriminative Feature Selection for Unsupervised Learning[C].The Twenty-Second International Joint Conference on Artificial Intelligence,Barcelona,Spain,2011
[20] Liu Jun,Ji Shuiwang,Ye Jieping.Multi-task Feature Learning via Efficient l2,1-Norm Minimization [C].The Twenty-Fifth Conference on Uncertainty in Artificial Intelligence,Montreal,Canada,2009
[21] Hou Chenping,Nie Feiping,Li Xuelong,et al.Joint Embedding Learning and Sparse Regression:A Framework for Unsupervised Feature Selection[J].IEEE Transactions on Cybernetics,2014,44(6):793-804
[22] Naseem I,Togneri R,Bennamoun M.Linear Regression for Face Recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(11):2 106-2 112
[23] Zhang Lei,Yang Meng,Feng Xiangchu.Sparse Representation or Collaborative Representation:Which Helps Face Recognition[C].2011 IEEE International Conference on Computer Vision,Barcelona,Spain,2011
[24] Xu Y,Zhang D,Yang J,et al.A Two-Phase Test Sample Sparse Representation Method for Use with Face Recognition[J].IEEE Transactions on Circuits and Systems for Video Technology,2011,21(9):1 255-1 262
[25] Donoho D L,Elad M.Optimally Sparse Representation in General (Non-orthogonal) Dictionaries via l1 Minimization[J].Proceedings of the National Academy of Sciences,2003,100(5):2 197-2 202
[26] Amaldi E,Kann V.On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems[J].Theoretical Computer Science,1998,209(1/2):237-260
[27] Donoho D L.For Most Large Underdetermined Systems of Equations,the Minimal l1-Norm Near-Solution Approximates the Sparsest Near-Solution[J].Communications on Pure and Applied Mathematics,2006,59(6):907-934
[28] Candès E J,Romberg J K,Tao T.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics,2006,59(8):1 207-1 223
[29] Candès E J,Tao T.Near-Optimal Signal Recovery from Random Projections:Universal Encoding Strategies[J].IEEE Transactions on Information Theory,2006,52(12):5 406-5 425
[30] Lyu Qin,Lin Zhouchen,She Yiyuan,et al.A Comparison of Typical lp Minimization Algorithms[J].Neurocomputing,2013,119:413-424
[31] Zhang Zheng,Wang Long,Zhu Qi,et al.Noise Mode-ling and Representation Based Classification Methods for Face Recognition[J].Neurocomputing,2015,148:420-429
[32] Tropp J A,Gilbert A C,Strauss M J.Algorithms for Simultaneous Sparse Approximation (Part I:Greedy Pursuit)[J].IEEE Transactions on Signal Processing,2006,86(3):572-588
[33] Mallat S G,Zhang Z.Matching Pursuits with Time-Frequency Dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3 397-3 415
[34] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal Matching Pursuit:Recursive Function Approximation with Applications to Wavelet Decomposition[C].The 27th Asilomar Conference on Signals,Systems and Computers,Pacific Grove,CA,USA,1993
[35] Donoho D L,Tsaig Y,Drori I,et al.Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2012,58(2):1 094-1 121
[36] Dai W,Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2 230-2 249
[37] Do T T,Gan L,Nguyen N,et al.Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C].Asilomar Conference on Signals,Systems and Computers,Pacific Grove,CA,USA,2008
[38] Jost P,Vandergheynst P,Frossard P.Tree-Based Pursuit:Algorithm and Properties[J].IEEE Transactions on Signal Processing,2006,54(12):4 685-4 697
[39] La C,Do M N.Tree-Based Orthogonal Matching Pursuit Algorithm for Signal Reconstruction[C].2006 International Conference on Image Processing,Atlanta,USA,2006
[40] Fadili M J,Starck J L,Murtagh F.Inpainting and Zooming Using Sparse Representations[J].The Computer Journal,2009,52(1):64-79
[41] Xu Zongben,Sun Jian.Image Inpainting by Patch Propagation Using Patch Sparsity[J].IEEE Transactions on Image Processing,2010,19(5):1 153-1 165
[42] Li Zhidan,He Hongjie,Yin Zhongke,et al.A Color-Gradient Patch Sparsity Based Image Inpainting Algorithm with Structure Coherence and Neighborhood Consistency[J].IEEE Transactions on Signal Processing,2014,99(6):116-128
[43] Li Zhidan,He Hongjie,Tai Hengming,et al.Color-Direction Patch-Sparsity-Based Image Inpainting Using Multidirection Features[J].IEEE Transactions on Image Processing,2015,24(3):1 138-1 152
[44] Figueiredo M A T,Nowak R D,Wright S J.Gradient Projection for Sparse Reconstruction:Application to Compressed Sensing and Other Inverse Problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-597
[45] Boyd S,Vandenberghe L,Faybusovich L.Convex Optimization[J].IEEE Transactions on Automatic Control,2006,51 (11):1 859-1 859
[46] Boyd S,Parikh N,Chu E,et al.Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[M].Oxford,England:Oxford University Press,2011
[47] Portugal L F,Resende M G C,Veiga G,et al.A Truncated Primal-Infeasible Dual-Feasible Network Interior Point Method[J].Networks,2000,35(2):91-108
[48] Koh K,Kim S J,Boyd S.An Interior-Point Method for Large-Scale l1-Regularized Logistic Regression[J].Journal of Machine Learning Research,2007,8:1 519-1 555
[49] Figueiredo M A T,Nowak R D.A Bound Optimization Approach to Wavelet-Based Image Deconvolution[C].IEEE International Conference on Image Processing,Genova,Italy,2005
[50] Beck A,Teboulle M.A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[J].SIAM Journal on Imaging Sciences,2009,2(1):183-202
[51] Zeng Jinshan,Lin Shaobo,Wang Yao,et al.l1/2 Regularization:Convergence of Iterative Half Thresholding Algorithm[J].IEEE Transactions on Signal Processing,2014,62(9):2 317-2 329
[52] Elad M,Matalon B,Zibulevsky M.Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization[J].Applied and Computational Harmonic Analysis,2007,23(3):346-367
[53] Donoho D L,Maleki A,Montanari A.Message-Passing Algorithms for Compressed Sensing[J].Proceedings of the National Academy of Sciences of the United States of America,2009,106(45):18 914-18 919
[54] Becker S R,Bobin J,Candès E J.NESTA:A Fast and Accurate First-Order Method for Sparse Recovery[J].SIAM Journal on Imaging Sciences,2011,4(1):1-39
[55] Becker S,Candès E J,Grant M C.Templates for Convex Cone Problems with Applications to Sparse Signal Recovery[J].Mathematical Programming Computation,2011,3(3):165-218
[56] Osborne M R,Presnell B,Turlach B A.A New Approach to Variable Selection in Least Squares Problems[J].IMA Journal of Numerical Analysis,2000,20(3):389-403
[57] Yang Junfeng,Zhang Yin.Alternating Direction Algorithms for l1-Problems in Compressive Sensing[J].SIAM Journal on Scientific Computing,2011,33(1):250-278
[58] Plumbley M D.Recovery of Sparse Representations by Polytope Faces Pursuit[C].The 6th International Conference on Independent Component Analysis and Blind Signal Separation,Berlin,Germany,2006
[59] Donoho D L,Tsaig Y.Fast Solution of l1-Norm Minimization Problems when the Solution May Be Sparse[J].IEEE Transactions on Information Theory,2008,54(11):4 789-4 812
[60] Efron B,Hastie T,Johnstone I,et al.Least Angle Regression[J].The Annals of Statistics,2004,32(2):407-499
[61] Asif M S,Romberg J.Fast and Accurate Algorithms for Re-Weighted l1-Norm Minimization[J].IEEE Transactions on Signal Processing,2012,61(23):5 905-5 916