Deterministic construction of array QC CS measurement matrices based on Singer perfect difference sets
Abstract
Low‐density parity‐check (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 quasi‐cyclic (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 g≥6and8. Comprehensive one‐dimensional (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]
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]
Donoho D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306
[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]
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]
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]
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]
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]
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]
Li S., Ge G.: ‘Deterministic sensing matrices arising from near orthogonal systems’, IEEE Trans. Inf. Theory, 2014, 60, (4), pp. 2291–2302
[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]
DeVore R.A.: ‘Deterministic constructions of compressed sensing matrices’, J. Complex., 2007, 23, pp. 918–925
[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]
Liu X.J., Xia S.T.: ‘Constructions of quasi‐cyclic measurement matrices based on array codes’. IEEE Int. Symp. Information Theory Proc. (ISIT), 2013, pp. 479–483
[14]
Lu W., Li W., Kpalma K.: ‘Near‐optimal binary compressed sensing matrix’, IEEE Trans. Inf. Theory, 2013, arXiv preprint arXiv:1304.4071
[15]
Shujuan T., Xiaoping F., Zhetao L. et al.: ‘Orthogonal‐gradient measurement matrix construction algorithm’, Chin. J. Electron., 2016, 25, (1), pp. 81–87
[16]
Candes E.J., Tao T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, (12), pp. 4203–4215
[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]
Donoho D.L., Elad M.: ‘Optimally sparse representation in general (non‐orthogonal) dictionaries via l1‐minimization’, Proc. Natl. Acad. Sci., 2003, 100, (5), pp. 2197–2202
[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]
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]
Gallager R.G.: ‘Low‐density parity‐check codes’, IEEE Trans. Inf. Theory, 1962, 8, (1), pp. 21–28
[22]
MacKay D.J.C., Neal R.M.: ‘Near Shannon limit performance of low‐density parity‐check codes’, Electron. Lett., 1996, 32, pp. 1645–1646
[23]
Ryan W.E., Lin S.: ‘Channel codes: classical and modern’ (Cambridge University Press, New York, 2009)
[24]
Torshizi E.O., Sharifi H., Seyrafi M.: ‘A new hybrid decoding algorithm for LDPC codes based on the improved variable multi weighted bit‐flipping and BP algorithms’. IEEE Iranian Conf. Electrical Engineering (ICEE), Mashhad, Iran, 2013, pp. 1–6
[25]
Kou Y., Lin S., Fossorier M.: ‘Low‐density parity‐check codes based on finite geometries: a rediscovery and new results’, IEEE Trans. Inf. Theory, 2001, 47, pp. 2711–2736
[26]
Fossorier M.P.C.: ‘Quasi‐cyclic low‐density parity‐check codes from circulant permutation matrices’, IEEE Trans. Inf. Theory, 2004, 50, pp. 1788–1794
[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]
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]
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]
Golomb S.: ‘How to number a graph’, in Read R.C.: ‘Graph theory and computing’ (Academic Press, New York, 1997), pp. 23–37
[31]
Halberstam H., Laxton R.R.: ‘Perfect difference sets’, Glasgow Math J., 1964, 6, (4), pp. 177–184
[32]
Drakakis K.: ‘A review of the available construction methods for Golomb rulers’, Adv. Math. Commun., 2009, 3, (3), pp. 235–250
[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]
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]
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]
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
Recommendations
Deterministic Construction of Binary, Bipolar, and Ternary Compressed Sensing Matrices
In this paper, we establish the connection between the Orthogonal Optical Codes (OOC) and binary compressed sensing matrices. We also introduce deterministic bipolar m × n RIP fulfilling ±1 matrices of order k such that m ≤ O (k(log2n)( log2k)/( ln log2...
Deterministic constructions of compressed sensing matrices based on codes
Compressed sensing theory is a sampling technique which provides a fundamentally new approach to data acquisition and makes sure that a sparse signal can be reconstructed from few measurements by taking full use of sparsity. In this paper, firstly, the ...
Sparse block circulant matrices for compressed sensing
An undetermined measurement matrix can capture sparse signals losslessly if the matrix satisfies the restricted isometry property (RIP) in compressed sensing (CS) framework. However, existing measurement matrices suffer from high computational burden ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2021 The Institution of Engineering and Technology.
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 October 2019
Author Tags
Author Tags
- deterministic construction
- array QC CS measurement matrices
- Singer perfect difference sets
- low‐density parity‐check codes
- compressed sensing
- common environments
- deterministic sparse sensing matrices
- array quasicyclic LDPC codes
- deterministic matrices
- circulant permutation matrices
- restricted isometric property
- computationally tractable criteria
- CS recovery capabilities
- measurement matrix
- sensing matrix
- superior CS recovery abilities
- physical storage space
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in