Coherence of sensing matrices coming from algebraic-geometric codes

Seungkook  Park

doi:10.3934/amc.2016016

Article Contents

2016, Volume 10, Issue 2: 429-436. Doi: 10.3934/amc.2016016

This issue Previous Article On the error distance of extended Reed-Solomon codes Next Article A class of $p$-ary cyclic codes and their weight enumerators

Coherence of sensing matrices coming from algebraic-geometric codes

Seungkook Park^1,

1.
Department of Mathematics, Sookmyung Women's University, Cheongpa-ro 47 gil 100, Yongsan-Ku, Seoul 140-742

Received: September 2014

Published: May 2016

Abstract / Introduction Related Papers Cited by

Abstract

Compressed sensing is a technique which is to used to reconstruct a sparse signal given few measurements of the signal. One of the main problems in compressed sensing is the deterministic construction of the sensing matrix. Li et al. introduced a new deterministic construction via algebraic-geometric codes (AG codes) and gave an upper bound for the coherence of the sensing matrices coming from AG codes. In this paper, we give the exact value of the coherence of the sensing matrices coming from AG codes in terms of the minimum distance of AG codes and deduce the upper bound given by Li et al. We also give formulas for the coherence of the sensing matrices coming from Hermitian two-point codes.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 14G50; Secondary: 92C55, 11R58, 14H50.

Citation:

Related Papers

Cited by

References

[1]	P. Beelen, The order bound for general algebraic geometric codes, Finite Fields Appl., 13 (2007), 665-680.doi: 10.1016/j.ffa.2006.09.006.
[2]	J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, Explicit constructions of RIP matrices and related problems, Duke Math. J., 159 (2011), 145-185.doi: 10.1215/00127094-1384809.
[3]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52 (2006), 489-509.doi: 10.1109/TIT.2005.862083.
[4]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215.doi: 10.1109/TIT.2005.858979.
[5]	R. A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity, 23 (2007), 918-925.doi: 10.1016/j.jco.2007.04.002.
[6]	D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.
[7]	M. Homma and S. J. Kim, Toward the determination of the minimum distance of two-point codes on a Hermitian curve, Des. Codes Crypt., 37 (2005), 111-132.doi: 10.1007/s10623-004-3807-5.
[8]	M. Homma and S. J. Kim, The complete determination of the minimum distance of two-point codes on a Hermitian curve, Des. Codes Crypt., 40 (2006), 5-24.doi: 10.1007/s10623-005-4599-y.
[9]	M. Homma and S. J. Kim, The two-point codes on a Hermitian curve with the designed minimum distance, Des. Codes Crypt., 38 (2006), 55-81.doi: 10.1007/s10623-004-5661-x.
[10]	M. Homma and S. J. Kim, The two-point codes with the designed distance on a Hermitian curve in even characteristic, Des. Codes Crypt., 39 (2006), 375-386.doi: 10.1007/s10623-005-5471-9.
[11]	C. Kirfel and R. Pellikaan, The minimum distance of codes in an array coming from telescopic semigroups, IEEE Trans. Inf. Theory, 41 (1995), 1720-1732.doi: 10.1109/18.476245.
[12]	S. Li, F. Gao, G. Ge and S. Zhang, Deterministic construction of compressed sensing matrices via algebraic curves, IEEE Trans. Inf. Theory, 58 (2012), 5035-5041.doi: 10.1109/TIT.2012.2196256.
[13]	G. L. Matthews, Weierstrass pairs and minimum distance of Goppa codes, Des. Codes Crypt., 22 (2001), 107-121.doi: 10.1023/A:1008311518095.
[14]	S. Park, Minimum distance of Hermitian two-point codes, Des. Codes Crypt., 57 (2010), 195-213.doi: 10.1007/s10623-009-9361-4.
[15]	H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition, Springer-Verlag, Berlin, 2009.
[16]	C. P. Xing and H. Chen, Improvements on parameters of one-point AG codes from Hermitian curves, IEEE Trans. Inf. Theory, 48 (2002), 535-537.doi: 10.1109/18.979330.