© The Institution of Engineering and Technology
Lowdensity paritycheck (LDPC) codes and compressed sensing (CS) share many common environments. In this study, a novel approach for constructing a new class of deterministic sparse sensing matrices based on array quasicyclic (QC) LDPC codes via Singer perfect difference sets is proposed. In contrast to random and the other deterministic matrices, the proposed framework would be highly desirable as it is generated based on circulant permutation matrices, which requires less memory for storage and lower computational cost for sensing. Since the restricted isometric property is very difficult to verify, then the mutual coherence and the girth are two computationally tractable criteria that the authors used to assess the CS recovery capabilities of sensing matrices. In addition, inspired by LDPC codes, they extract a necessary condition for the proposed measurement matrix to have effective values for girth as large as . Comprehensive onedimensional (1D) and 2D simulations verify that their proposed sensing matrix has minimum coherence and superior CS recovery abilities in comparison with the corresponding random Gaussian, Bernoulli, and the other deterministically generated matrices. Furthermore, the required physical storage space and the complexity of the hardware implementation are greatly reduced due to being sparse and QC in structure.
References


1)

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

2)

2. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306.

3)

3. Zhang, J., Han, G., Fang, Y.: ‘Deterministic construction of compressed sensing matrices from protograph LDPC codes’, IEEE Signal Process. Lett., 2015, 22, (11), pp. 1960–1964.

4)

4. Baraniuk, R., Davenport, M., DeVore, R., et al: ‘A simple proof of the restricted isometry property for random matrices’, Constr. Approx., 2008, 28, (3), pp. 253–263.

5)

5. Xia, S.T., Liu, X.J., Jiang, Y., et al: ‘Deterministic constructions of binary measurement matrices from finite geometry’, IEEE Trans. Signal Process., 2015, 63, (4), pp. 1017–1029.

6)

6. Calderbank, R., Howard, S., Jafarpour, S.: ‘Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property’, IEEE J. Sel. Top. Signal Process., 2010, 4, (2), pp. 358–374.

7)

7. Li, S., Gao, F., Ge, G., et al: ‘Deterministic construction of compressed sensing matrices via algebraic curves’, IEEE Trans. Inf. Theory, 2012, 58, (8), pp. 5035–5041.

8)

8. Amini, A., Marvasti, F.: ‘Deterministic construction of binary, bipolar, and ternary compressed sensing matrices’, IEEE Trans. Inf. Theory, 2011, 57, (4), pp. 2360–2370.

9)

9. Li, S., Ge, G.: ‘Deterministic sensing matrices arising from near orthogonal systems’, IEEE Trans. Inf. Theory, 2014, 60, (4), pp. 2291–2302.

10)

10. Li, S., Ge, G.: ‘Deterministic construction of sparse sensing matrices via finite geometry’, IEEE Trans. Signal Process., 2014, 62, (11), pp. 2850–2859.

11)

11. DeVore, R.A.: ‘Deterministic constructions of compressed sensing matrices’, J. Complex., 2007, 23, pp. 918–925.

12)

12. Dimakis, A.G., Smarandache, R., Vontobel, P.O.: ‘LDPC codes for compressed sensing’, IEEE Trans. Inf. Theory, 2012, 58, (5), pp. 3093–3114.

13)

13. Liu, X.J., Xia, S.T.: ‘Constructions of quasicyclic measurement matrices based on array codes’. IEEE Int. Symp. Information Theory Proc. (ISIT), 2013, pp. 479–483.

14)

14. Lu, W., Li, W., Kpalma, K.: ‘Nearoptimal binary compressed sensing matrix’, IEEE Trans. Inf. Theory, 2013, .

15)

15. Shujuan, T., Xiaoping, F., Zhetao, L., et al: ‘Orthogonalgradient measurement matrix construction algorithm’, Chin. J. Electron., 2016, 25, (1), pp. 81–87.

16)

16. Candes, E.J., Tao, T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, (12), pp. 4203–4215.

17)

17. Xu, W., Hassibi, B.: ‘Compressed sensing over the Grassmann manifold: a unified analytical framework’. Proc. 46th Allerton Conf. Communications, Control and Computing, Monticello, IL, September 2008, pp. 562–567.

18)

18. Donoho, D.L., Elad, M.: ‘Optimally sparse representation in general (nonorthogonal) dictionaries via l1minimization’, Proc. Natl. Acad. Sci., 2003, 100, (5), pp. 2197–2202.

19)

19. Bandeira, A., Dobriban, E., Mixon, D.G., et al: ‘Certifying the restricted isometry property is hard’, IEEE Trans. Inf. Theory, 2013, 59, (6), pp. 3448–3450.

20)

20. Tillmann, A.M., Pfetsch, M.E.: ‘The computational complexity of the restricted isometry property, the null space property, and related concepts in compressed sensing’, IEEE Trans. Inf. Theory, 2014, 60, (2), pp. 1248–1259.

21)

21. Gallager, R.G.: ‘Lowdensity paritycheck codes’, IEEE Trans. Inf. Theory, 1962, 8, (1), pp. 21–28.

22)

22. MacKay, D.J.C., Neal, R.M.: ‘Near Shannon limit performance of lowdensity paritycheck codes’, Electron. Lett., 1996, 32, pp. 1645–1646.

23)

23. Ryan, W.E., Lin, S.: ‘Channel codes: classical and modern’ (Cambridge University Press, New York, 2009).

24)

24. Torshizi, E.O., Sharifi, H., Seyrafi, M.: ‘A new hybrid decoding algorithm for LDPC codes based on the improved variable multi weighted bitflipping and BP algorithms’. IEEE Iranian Conf. Electrical Engineering (ICEE), Mashhad, Iran, 2013, pp. 1–6.

25)

25. Kou, Y., Lin, S., Fossorier, M.: ‘Lowdensity paritycheck codes based on finite geometries: a rediscovery and new results’, IEEE Trans. Inf. Theory, 2001, 47, pp. 2711–2736.

26)

26. Fossorier, M.P.C.: ‘Quasicyclic lowdensity paritycheck codes from circulant permutation matrices’, IEEE Trans. Inf. Theory, 2004, 50, pp. 1788–1794.

27)

27. Babcock, W.C.: ‘Intermodulation interference in radio systems/frequency of occurrence and control by channel selection’, Bell Syst. Tech. J., 1953, 31, pp. 63–73.

28)

28. Robinson, J.P., Bernstein, A.J.: ‘A class of binary recurrent codes with limited error propagation’, IEEE Trans. Inf. Theory, 1967, 13, pp. 106–113.

29)

29. Biraud, F., Blum, E.J., Ribes, J.C.: ‘On optimal synthetic linear arrays with applications to radio astronomy’, IEEE Trans. Antennas Propag., 1974, 22, pp. 108–109.

30)

30. Golomb, S.: ‘How to number a graph’, in Read, R.C.: ‘Graph theory and computing’ (Academic Press, New York, 1997), pp. 23–37.

31)

31. Halberstam, H., Laxton, R.R.: ‘Perfect difference sets’, Glasgow Math J., 1964, 6, (4), pp. 177–184.

32)

32. Drakakis, K.: ‘A review of the available construction methods for Golomb rulers’, Adv. Math. Commun., 2009, 3, (3), pp. 235–250.

33)

33. Khajehnejad, A., Tehrani, A.S., Dimakis, A.G., et al: ‘Explicit matrices for sparse approximation’. Proc. IEEE Int. Symp. Information Theory, St. Petersburg, Russia, August 2011, pp. 469–473.

34)

34. Liu, X.J., Xia, S.T.: ‘Reconstruction guarantee analysis of binary measurement matrices based on girth’. Proc. IEEE Int. Symp. Information Theory, July 2013, pp. 474–478.

35)

35. Zhao, H., Ye, H., Wang, R.: ‘The construction of measurement matrices based on block weighing matrix in compressed sensing’, Signal Process., 2016, 123, pp. 64–74.

36)

36. Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: ‘Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems’, IEEE J. Sel. Top. Signal Process., 2007, 1, (4), pp. 586–598.
http://iet.metastore.ingenta.com/content/journals/10.1049/ietcom.2018.6015
Related content
content/journals/10.1049/ietcom.2018.6015
pub_keyword,iet_inspecKeyword,pub_concept
6
6