一种改进的稀疏信号重构的梯度投影算法
An Improved Gradient Projection Method for Sparse Signal Reconstruction
DOI: 10.12677/CSA.2017.79095, PDF, HTML, XML, 下载: 1,939  浏览: 6,917  科研立项经费支持
作者: 胡剑峰*：海南师范大学数学与统计学院，海南 海口
关键词: 压缩感知；稀疏重构；凸优化；梯度投影；Compressed Sensing； Sparse Reconstruction； Convex Optimization； Gradient Projection
摘要: 压缩感知理论作为一种全新的信号采集、编解码理论，已被广泛地应用于图像处理、模式识别、自动控制和生物传感等领域，并展现出强大的力量。为了更快速地求解压缩感知问题，在稀疏信号重构的Barzilai-Borwein (B-B)梯度投影(Barzilai-Borwein Gradient Projection for Sparse Reconstruction, GPSR-BB)算法的基础上，采用预测校正的技巧，提出了一种改进的梯度投影算法。该算法首先由常数步长的梯度投影产生一个预测点，再根据预测点及B-B方法计算步长得到新的迭代点。新算法单步迭代计算同样简单，且采用预测校正技巧可使迭代点更接近问题的解，从而可望减少算法的总的迭代次数。对随机生成的测试问题进行数值实验，数值结果表明新算法的运行时间要少于GPSR-BB算法。
Abstract: As a novel sampling, coding and decoding theory, compressed sensing has been a powerful tool which was widely used to the fields of image processing, pattern recognition, automatic control, biological sensors and so on. Based on the Barzilai-Borwein (B-B) gradient projection for sparse reconstruction (GPSR-BB), this paper proposed a new algorithm by using predictor-corrector technique for solving compressed sensing problem fast. In the new algorithm, a predicted point was first generated by traditional gradient projection and then a new iteration point was obtained with B-B method according to the predicted point. In our algorithm, the calculation of a single iteration is also simple, and by using predictor-corrector technique, the iteration point may be closer to the solution of the problem, thereby the number of the iteration would be reduced. Numerical results show that the running time of the new algorithm is less than GPSR-BB for some randomly generated test problems.
文章引用：胡剑峰. 一种改进的稀疏信号重构的梯度投影算法[J]. 计算机科学与应用, 2017, 7(9): 828-833. https://doi.org/10.12677/CSA.2017.79095

参考文献

[1] Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306.
https://doi.org/10.1109/TIT.2006.871582
[2] Candès, E.J. (2006) Compressive Sampling. Proceedings of International Congress of Mathematicians, Zürich, Switzerland, European Mathematical Society Publishing House, 1433-1452.
[3] 焦李成, 谭山. 图像的多尺度几何分析: 回顾和展望[J]. 电子学报, 2003, 31(12A): 1975-1981.
[4] Bruckstein, A.M., Donoho, D.L. and Elad, M. (2009) From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images. SIAM Review, 51, 34-81.
https://doi.org/10.1137/060657704
[5] Andrés, A.M., Padovani, S., Tepper, M., et al. (2014) Face Recognition on Partially Occluded Images Using Compressed Sensing. Pattern Recognition Letters, 36, 235-242.
https://doi.org/10.1016/j.patrec.2013.08.001
[6] Baraniuk, R. and Steeghs, P. (2007) Compressive Radar Imagin. Proceedings of the Radar Conference, Boston, MA, 17-20 April 2007, 128-133.
https://doi.org/10.1109/RADAR.2007.374203
[7] Lustig, M., Donoho, D.L. and Pauly, J. (2007) Application of Compressed Sensing for Rapid MR Imaging. Magnetic Resonance in Medicine, 58, 1182-1195.
https://doi.org/10.1002/mrm.21391
[8] Candès, E.J., Romberg, J. and Tao, T. (2006) Stable Signal Recovery from Incomplete and Inaccurate Measurements. Communications on Pure and Applied Mathematics, 59, 1207-1223.
https://doi.org/10.1002/cpa.20124
[9] Candes, E.J., Romberg, J. and Tao, T. (2006) Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52, 489-509.
https://doi.org/10.1109/TIT.2005.862083
[10] Candès, E.J. and Tao, T. (2006) Near Optional Signal Recovery from Random Projections: Universal Encoding Strategies. IEEE Transactions on Information Theory, 52, 5406-5425.
https://doi.org/10.1109/TIT.2006.885507
[11] Mo, Q. and Li, S. (2011) New Bounds on the Restricted Isometry Constant. Applied and Computational Harmonic Analysis, 31, 460-468.
[12] Cai, T.T. and Zhang, A. (2014) Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices. IEEE Transactions on Information Theory, 60, 122-132.
https://doi.org/10.1109/TIT.2013.2288639
[13] Mallat, S. and Zhang, Z. (1993) Matching Pursuit with Time-Frequency Dictionaries. IEEE Transactions on Signal Processing, 41, 3397-3415.
https://doi.org/10.1109/78.258082
[14] Troop, J. and Gilbert, A. (2007) Signal Recovery from Partial Information via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 53, 4655-4666.
https://doi.org/10.1109/TIT.2007.909108
[15] 朱延万, 赵拥军, 孙兵. 一种改进的稀疏度自适应匹配追踪算法[J]. 信号处理, 2012, 28(1): 80-86.
[16] Chen, S., Donoho, D.L. and Saunders, M. (1998) Atomic Decomposition by Basis Pursuit. SIAM Journal on Scientific Computing, 20, 33-61.
https://doi.org/10.1137/S1064827596304010
[17] Daubechies, I., Friese, M.D. and Christine, D.M. (2004) An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint. Communications on Pure and Applied Mathematics, 57, 1413-1457.
https://doi.org/10.1002/cpa.20042
[18] 李小静, 李冬梅, 梁圣法. 一种改进的迭代硬阈值算法[J]. 科学技术与工程, 2014, 14(14): 64-68.
[19] Figueiredo, M., Nowak, R. and Wright, S. (2007) Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems. IEEE Journal of Selected Topics in Signal Processing, 1, 586-597.
https://doi.org/10.1109/JSTSP.2007.910281
[20] Yang, J.F. and Zhang, Y. (2011) Alternating Direction Algorithms for 1,1-Problems in Compressive Sensing. SIAM Journal on Scientific Computing, 33, 250-278.
https://doi.org/10.1137/090777761
[21] Zhu, Y., Wu, J. and Yu, G. (2015) A Fast Proximal Point Algorithm for 1,1-Minimization Problem in Compressed Sensing. Applied Mathematics and Computation, 270, 777-784.
[22] Natarajan, B.K. (1995) Sparse Approximation Solutions to Linear Systems. SIAM Journal on Computing, 24, 227-234.
https://doi.org/10.1137/S0097539792240406
[23] Nesterov, Y. (1998) Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers.
[24] Kim, S.J., Koh, K., Boyd, S., et al. (2007) A Method for Large-Scale l1-Regularized Least Squares. IEEE Journal of Selected Topics in Signal Processing, 1, 606-617.