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

Coherence of sensing matrices coming from algebraic-geometric codes

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

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

[2]

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307

[3]

Kerioui Nadjah, Abdelouahab Mohammed Salah. Stability and Hopf bifurcation of the coexistence equilibrium for a differential-algebraic biological economic system with predator harvesting. Electronic Research Archive, 2021, 29 (1) : 1641-1660. doi: 10.3934/era.2020084

[4]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046

[5]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[6]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

[7]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[8]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117

[9]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305

[10]

Qian Liu, Shuang Liu, King-Yeung Lam. Asymptotic spreading of interacting species with multiple fronts Ⅰ: A geometric optics approach. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3683-3714. doi: 10.3934/dcds.2020050

[11]

João Vitor da Silva, Hernán Vivas. Sharp regularity for degenerate obstacle type problems: A geometric approach. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1359-1385. doi: 10.3934/dcds.2020321

[12]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

[13]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[14]

Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386

[15]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[16]

Ali Wehbe, Rayan Nasser, Nahla Noun. Stability of N-D transmission problem in viscoelasticity with localized Kelvin-Voigt damping under different types of geometric conditions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020050

[17]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]