﻿ 一种改进的稀疏信号重构的梯度投影算法 An Improved Gradient Projection Method for Sparse Signal Reconstruction

Computer Science and Application
Vol.07 No.09(2017), Article ID:21974,6 pages
10.12677/CSA.2017.79095

An Improved Gradient Projection Method for Sparse Signal Reconstruction

Jianfeng Hu

School of Mathematics and Statistics, Hainan Normal University, Haikou Hainan

Received: Aug. 22nd, 2017; accepted: Sep. 3rd, 2017; published: Sep. 8th, 2017

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.

Keywords:Compressed Sensing, Sparse Reconstruction, Convex Optimization, Gradient Projection

1. 引言

2. 压缩感知的凸优化模型

(1)

(2)

(3)

(4)

3. 改进的梯度投影法

(5)

4. 数值结果

Table 1. Iterations and CPU times for PCGP-BB and GPSR-BB (Average over ten runs,)

Table 2. Iterations and CPU times for PCGP-BB and GPSR-BB (Average over ten runs,)

PCGP-BB和GPSR-BB的迭代次数和CPU时间(以十次测试的平均值为准)，其中是Matlab随机向量生成函数。由于采用相同的最优性条件作为终止条件，这三者的均方误差基本相同，因而未在表中列出。由表1表2可知，就所测试的问题，PCGP-BB的迭代次数和CPU时间均少于GPSR-BB，而当随机取初值时，非单调的GPSR-BB甚至求解失败，表2中“-”表示迭代次数超过迭代上限仍未能终止。

5. 结语

An Improved Gradient Projection Method for Sparse Signal Reconstruction[J]. 计算机科学与应用, 2017, 07(09): 828-833. http://dx.doi.org/10.12677/CSA.2017.79095

1. 1. Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. https://doi.org/10.1109/TIT.2006.871582

2. 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. 3. 焦李成, 谭山. 图像的多尺度几何分析: 回顾和展望[J]. 电子学报, 2003, 31(12A): 1975-1981.

4. 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. 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. 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. 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. 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. 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. 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. 11. Mo, Q. and Li, S. (2011) New Bounds on the Restricted Isometry Constant. Applied and Computational Harmonic Analysis, 31, 460-468.

12. 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. 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. 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. 15. 朱延万, 赵拥军, 孙兵. 一种改进的稀疏度自适应匹配追踪算法[J]. 信号处理, 2012, 28(1): 80-86.

16. 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. 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. 18. 李小静, 李冬梅, 梁圣法. 一种改进的迭代硬阈值算法[J]. 科学技术与工程, 2014, 14(14): 64-68.

19. 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. 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. 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. 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. 23. Nesterov, Y. (1998) Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers.

24. 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.