American Institute of Mathematical Sciences

Advanced
May  2016, 10(2): 429-436. doi: 10.3934/amc.2016016

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, South Korea

Received  September 2014 Published  April 2016

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: algebraic-geometric code, minimum distance., coherence, Compressed sensing.
Mathematics Subject Classification: Primary: 11T71, 14G50; Secondary: 92C55, 11R58, 14H5.
Citation: Seungkook Park. Coherence of sensing matrices coming from algebraic-geometric codes. Advances in Mathematics of Communications, 2016, 10 (2) : 429-436. doi: 10.3934/amc.2016016
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.

show all references

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.

[1]

Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[2]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[3]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[4]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[5]

Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021191
[6]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[7]

Jinmei Fan, Yanhai Zhang. Optimal quinary negacyclic codes with minimum distance four. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021043
[8]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[9]

Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[10]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175
[11]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65
[12]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018
[13]

Bernard Bonnard, Monique Chyba, Alain Jacquemard, John Marriott. Algebraic geometric classification of the singular flow in the contrast imaging problem in nuclear magnetic resonance. Mathematical Control and Related Fields, 2013, 3 (4) : 397-432. doi: 10.3934/mcrf.2013.3.397
[14]

Keith Burns, Amie Wilkinson. Dynamical coherence and center bunching. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 89-100. doi: 10.3934/dcds.2008.22.89
[15]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[16]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[17]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[18]

Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[19]

Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017
[20]

Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022010

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (179)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy