Restricted isometry constant improvement based on a singular value decomposition-weighted measurement matrix for compressed sensing
- Author(s): Qian Wang 1 and Gangrong Qu 1, 2
-
-
View affiliations
-
Affiliations:
1:
School of Science , Beijing Jiaotong University , Beijing 100044 , People's Republic of China ;
2: Beijing Center for Mathematics and Information Interdisciplinary Sciences (BCMIIS) , Beijing 100048 , People's Republic of China
-
Affiliations:
1:
School of Science , Beijing Jiaotong University , Beijing 100044 , People's Republic of China ;
- Source:
Volume 11, Issue 11,
03
August
2017,
p.
1706 – 1718
DOI: 10.1049/iet-com.2016.1435 , Print ISSN 1751-8628, Online ISSN 1751-8636
In compressed sensing, an exact reconstruction depends on the restricted isometry property with a small restricted isometry constant (RIC). Based on singular value decomposition (SVD), the authors improve the RICs of measurement matrices. The proposed weighted measurement matrix method breaks the limit to attain a small RIC and has potential applications in imaging systems. They derive an improvement sufficient condition for the RIC for exact reconstruction using the orthogonal matching pursuit algorithm. The numerical stability of the SVD-based weighted equation is analysed. Simulation results show that the reconstruction results obtained by the proposed SVD-based weighted approach are obviously better than those obtained by the direct reconstruction. In the simulation, they also successfully apply the proposed weighted equation for a computed tomography reconstruction.
Inspec keywords: singular value decomposition; approximation theory; compressed sensing; numerical stability; computerised tomography; image reconstruction
Other keywords: RIC; SVD-based weighted equation; orthogonal matching pursuit algorithm; compressed sensing; numerical stability; imaging systems; computed tomography reconstruction; singular value decomposition-weighted measurement matrix; restricted isometry constant improvement
Subjects: Linear algebra (numerical analysis); Optical, image and video signal processing; Linear algebra (numerical analysis); Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis); Computer vision and image processing techniques
References
-
-
1)
-
1. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306.
-
-
2)
-
32. Lawson, C.L., Hanson, R.J.: ‘Solving least squares problems’ (Prentice-Hall, 1974).
-
-
3)
-
5. Chen, S.S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM review, 2001, 43, (1), pp. 129–159.
-
-
4)
-
7. Donoho, D.L., Johnstone, I.M.: ‘Ideal spatial adaptation by wavelet shrinkage’, Biometrika, 1998, 81, (3), pp. 425–455.
-
-
5)
-
25. Sun, J., Wang, S., Dong, Y.: ‘Sparse block circulant matrices for compressed sensing’, IET Commun., 2013, 7, (13), pp. 1412–1418.
-
-
6)
-
17. Tropp, J.A., Gilbert, A.C.: ‘Signal recovery from random measurements via orthogonal matching pursuit’, IEEE Trans. Inf. Theory, 2007, 53, (12), pp. 4655–4666.
-
-
7)
-
16. Daubechies, I., Devore, R., Fornasier, M., et al: ‘Iteratively reweighted least squares minimization for sparse recovery’, Commun. Pure Appl. Math., 2010, 63, (1), pp. 1–38.
-
-
8)
-
24. Huang, S., Zhu, J.: ‘Recovery of sparse signals using OMP and its variants: Convergence analysis based on RIP’, Inverse Probl., 2011, 27, (3), pp. 1–14.
-
-
9)
-
13. Candés, E.J., Romberg, J.K., Tao, T.: ‘Stable signal recovery from incomplete and inaccurate measurements’, Commun. Pure Appl. Math., 2006, 59, (8), pp. 1207–1223.
-
-
10)
-
27. Abolghasemi, V., Ferdowsi, S., Makkiabadi, B., et al: ‘On optimization of the measurement matrix for compressive sensing’. 18th European Signal Processing Conf., 2010, 2010, pp. 427–431.
-
-
11)
-
21. Needell, D., Vershynin, R.: ‘Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit’, Found. Comput. Math., 2007, 9, (3), pp. 317–334.
-
-
12)
-
19. Donoho, D.L., Tsaig, Y., Drori, I., et al: ‘Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit’, IEEE Trans. Inf. Theory, 2006, 58, (2), pp. 1094–1121.
-
-
13)
-
6. Daubechies, I., Defrise, M., Mol, C.D.: ‘An iterative thresholding algorithm for linear inverse problems with a sparsity constraint’, Commun. Pure Appl. Math., 2004, 57, (11), pp. 1413–1457.
-
-
14)
-
34. Wang, Q., Li, D., Shen, Y.: ‘Intelligent nonconvex compressive sensing using prior information for image reconstruction by sparse representation’, Neurocomputing, 2017, 224, pp. 71–81.
-
-
15)
-
11. Candés, E.J., Wakin, M.B., Boyd, S.P.: ‘Enhancing sparsity by reweighted l1 minimization’, J. Fourier Anal. Appl., 2008, 14, (5-6), pp. 877–905.
-
-
16)
-
29. Ganguli, S.S., Dimri, V.P.: ‘Interpretation of gravity data using eigenimage with Indian case study: a SVD approach’, J. Appl. Geophys., 2013, 95, pp. 23–35.
-
-
17)
-
20. Needell, D., Vershynin, R.: ‘Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit’, IEEE J. Sel. Top. Signal Process., 2007, 4, (2), pp. 310–316.
-
-
18)
-
26. Xu, G., Xu, Z.: ‘Compressed sensing matrices from Fourier matrices’, IEEE Trans. Inf. Theory, 2013, 61, (1), pp. 469–478.
-
-
19)
-
36. Han, G., Qu, G., Jiang, M.: ‘Relaxation strategy for the Landweber method’, Signal Process., 2016, 125, pp. 87–96.
-
-
20)
-
4. Candés, E.J., Romberg, J.K.: ‘Practical signal recovery from random projections’. Proc. of SPIE - The Int. Society for Optical Engineering, 2004, p. 5674.
-
-
21)
-
10. Rudelson, M., Vershynin, R.: ‘Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements’. Conf. on Information Sciences and Systems, 2006, 2006, pp. 207–212.
-
-
22)
-
28. Zhao, Y.J., Zheng, B.Y., Chen, S.N.: ‘The design of adaptive measurement matrix in compressed sensing’, Signal Process., 2012, 28, (12), pp. 1635–1641.
-
-
23)
-
23. Xu, Z.: ‘The performance of orthogonal multi-matching pursuit under RIP’, Journal of Computational Mathematics, 2015, 33, (5), pp. 495–516.
-
-
24)
-
33. Xu, Z., Chang, X., Xu, F., et al: ‘L1/2 regularization: a thresholding representation theory and a fast solver’, IEEE Trans. Neural Netw. Learn. Syst., 2012, 23, (7), pp. 1013–1027.
-
-
25)
-
18. Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: ‘Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition’. Conf. on Signals, 1995, pp. 1–3.
-
-
26)
-
22. Needell, D., Tropp, J.A.: ‘CoSaMP: iterative signal recovery from incomplete and inaccurate samples’, Appl. Comput. Harmon. Anal., 2008, 26, (3), pp. 301–321.
-
-
27)
-
30. Edfors, O., Sandell, M., Jan-Jaap, V.D.B., et al: ‘OFDM channel estimation by singular value decomposition’, IEEE Trans. Commun., 1998, 46, (7), pp. 931–939.
-
-
28)
-
15. Cai, T.T., Xu, G., Zhang, J.: ‘On recovery of sparse signals via minimization’, IEEE Trans. Inf. Theory, 2009, 55, (7), pp. 3388–3397.
-
-
29)
-
9. Donoho, D.L., Logan, B.F.: ‘Signal recovery and the large sieve’, SIAM J. Appl. Math., 1992, 52, (2), pp. 577–591.
-
-
30)
-
14. Candés, E.J.: ‘The restricted isometry property and its implications for compressed sensing’, Comptes Rendus Math., 2008, 346, (9-10), pp. 589–592.
-
-
31)
-
2. Candés, E.J., Romberg, J., Tao, T.: ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inf. Theory, 2006, 52, (2), pp. 489–509.
-
-
32)
-
3. Candés, E.J., Tao, T.: ‘Near-optimal signal recovery from random projections: universal encoding strategies?’, IEEE Trans. Inf. Theory, 2007, 52, (12), pp. 5406–5425.
-
-
33)
-
31. Foucart, S., Rauhut, H.: ‘A mathematical introduction to compressive sensing’, in Benedetto, J.J. (Eds.): ‘Applied and Numerical Harmonic Analysis’ (Birkhäuser/Springer, New York, 2013).
-
-
34)
-
12. Candés, E.J., Tao, T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, (12), pp. 4203–4215.
-
-
35)
-
8. Donoho, D.L.: ‘Maximum entropy and the nearly black object’, J. R. Stat. Soc., 1992, 54, (1), pp. 41–81.
-
-
36)
-
35. Siddon, R.L.: ‘Fast calculation of the exact radiological path for a three-dimensional CT array’, Med. Phys., 2010, 12, (2), pp. 252–255.
-
-
1)