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.  doi: 10.1016/j.ffa.2006.09.006.  Google Scholar

[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.  doi: 10.1215/00127094-1384809.  Google Scholar

[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.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[4]

E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Trans. Inf. Theory, 51 (2005), 4203.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[5]

R. A. DeVore, Deterministic constructions of compressed sensing matrices,, J. Complexity, 23 (2007), 918.  doi: 10.1016/j.jco.2007.04.002.  Google Scholar

[6]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inf. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  doi: 10.1007/s10623-004-3807-5.  Google Scholar

[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.  doi: 10.1007/s10623-005-4599-y.  Google Scholar

[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.  doi: 10.1007/s10623-004-5661-x.  Google Scholar

[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.  doi: 10.1007/s10623-005-5471-9.  Google Scholar

[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.  doi: 10.1109/18.476245.  Google Scholar

[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.  doi: 10.1109/TIT.2012.2196256.  Google Scholar

[13]

G. L. Matthews, Weierstrass pairs and minimum distance of Goppa codes,, Des. Codes Crypt., 22 (2001), 107.  doi: 10.1023/A:1008311518095.  Google Scholar

[14]

S. Park, Minimum distance of Hermitian two-point codes,, Des. Codes Crypt., 57 (2010), 195.  doi: 10.1007/s10623-009-9361-4.  Google Scholar

[15]

H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition,, Springer-Verlag, (2009).   Google Scholar

[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.  doi: 10.1109/18.979330.  Google Scholar

show all references

References:
[1]

P. Beelen, The order bound for general algebraic geometric codes,, Finite Fields Appl., 13 (2007), 665.  doi: 10.1016/j.ffa.2006.09.006.  Google Scholar

[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.  doi: 10.1215/00127094-1384809.  Google Scholar

[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.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[4]

E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Trans. Inf. Theory, 51 (2005), 4203.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[5]

R. A. DeVore, Deterministic constructions of compressed sensing matrices,, J. Complexity, 23 (2007), 918.  doi: 10.1016/j.jco.2007.04.002.  Google Scholar

[6]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inf. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  doi: 10.1007/s10623-004-3807-5.  Google Scholar

[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.  doi: 10.1007/s10623-005-4599-y.  Google Scholar

[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.  doi: 10.1007/s10623-004-5661-x.  Google Scholar

[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.  doi: 10.1007/s10623-005-5471-9.  Google Scholar

[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.  doi: 10.1109/18.476245.  Google Scholar

[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.  doi: 10.1109/TIT.2012.2196256.  Google Scholar

[13]

G. L. Matthews, Weierstrass pairs and minimum distance of Goppa codes,, Des. Codes Crypt., 22 (2001), 107.  doi: 10.1023/A:1008311518095.  Google Scholar

[14]

S. Park, Minimum distance of Hermitian two-point codes,, Des. Codes Crypt., 57 (2010), 195.  doi: 10.1007/s10623-009-9361-4.  Google Scholar

[15]

H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition,, Springer-Verlag, (2009).   Google Scholar

[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.  doi: 10.1109/18.979330.  Google Scholar

[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 & Management Optimization, 2017, 13 (5) : 1-8. 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]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020038
[6]

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

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

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
[9]

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
[10]

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
[11]

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 & Related Fields, 2013, 3 (4) : 397-432. doi: 10.3934/mcrf.2013.3.397
[12]

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

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
[14]

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
[15]

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

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

José M. Arrieta, Esperanza Santamaría. Estimates on the distance of inertial manifolds. Discrete & Continuous Dynamical Systems - A, 2014, 34 (10) : 3921-3944. doi: 10.3934/dcds.2014.34.3921
[18]

Liliana Trejo-Valencia, Edgardo Ugalde. Projective distance and $g$-measures. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3565-3579. doi: 10.3934/dcdsb.2015.20.3565
[19]

Michael Brin, Dmitri Burago, Sergey Ivanov. Dynamical coherence of partially hyperbolic diffeomorphisms of the 3-torus. Journal of Modern Dynamics, 2009, 3 (1) : 1-11. doi: 10.3934/jmd.2009.3.1
[20]

Bernard Bonnard, Thierry Combot, Lionel Jassionnesse. Integrability methods in the time minimal coherence transfer for Ising chains of three spins. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4095-4114. doi: 10.3934/dcds.2015.35.4095

2018 Impact Factor: 0.879

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences