[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A valuable opportunity is provided by compressed sensing (CS) to accomplish the tasks of high speed sampling, the transmission of large volumes of data, and storage in signal processing. To some extent, CS has brought tremendous changes in the information technologies that we use in our daily lives. However, the construction of compressed sensing matrices still can pose substantial problems. In this paper, we provide a kind of deterministic construction of sensing matrices based on singular linear spaces over finite fields. In particular, by choosing appropriate parameters, we constructed binary sensing matrices that are superior to existing matrices, and they outperform DeVore’s matrices. In addition, we used an embedding manipulation to merge our binary matrices with matrices that had low coherence, thereby improving such matrices. Compared with the quintessential binary matrices, the improved matrices possess better ability to compress and recover signals. The favorable performance of our binary and improved matrices was demonstrated by numerical simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Amini A, Montazerhodjat V, Marvasti F (2012) Matrices with small coherence using \(p\)-ary block codes. IEEE Trans Signal Process 60(1):172–181

    Article  MathSciNet  Google Scholar 

  • Amini A, Marvasti F (2011) Deterministic construction of binary, bipolar and ternary compressed sensing matrices. IEEE Trans Inf Theory 57(4):2360–2370

    Article  MathSciNet  Google Scholar 

  • Applebaum L, Howard S, Searle S, Calderbank R (2009) Chirp sensing codes: deterministic compressed sensing measurements for fast recovery. Appl Comput Harmon Anal 26(2):283–290

    Article  MathSciNet  MATH  Google Scholar 

  • Berinde R, Gilbert A, Indyk P, Karloff H, Strauss M (2008) Combining geometry and combinatorics: a unified approach to sparse signal recovery, In Proceeding 46th Annual Allerton Conference Communication, Control, Computing, pp. 798–805

  • Bourgain J, Dilworth S, Ford K, Konyagin S, Kutzarova D (2011) Explicit constructions of RIP matrices and related problems. Duke Math J 159(1):145–185

    Article  MathSciNet  MATH  Google Scholar 

  • Brouwer A, Cohen A, Neumaier A (1989) Distance-regular graphs. Springer, Berlin

    Book  MATH  Google Scholar 

  • Calderbank R, Howard S, Jafarpour S (2010) Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE Trans Inf Theory 4(2):358–374

    Google Scholar 

  • Candès E, Romberg J, Tao T (2006) Stable signal recovery from incomplete and inaccurate measurement. Commun Pure Appl Math 59(8):1207–1223

    Article  MathSciNet  MATH  Google Scholar 

  • Candès E, Romberg J, Tao T (2006) Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inf Theory 52(2):489–509

    Article  MathSciNet  MATH  Google Scholar 

  • Candès E (2008) The restricted isometry property and its implications for compressed sensing. Comptes Rendus Math 346(9–10):589–592

    Article  MathSciNet  MATH  Google Scholar 

  • Candès E, Tao T (2005) Decoding by linear programming. IEEE Trans Inf Theory 51(12):4203–4215

    Article  MathSciNet  MATH  Google Scholar 

  • Candès E, Tao T (2006) Near-optimal signal recovery from random projections: universal encoding strategies. IEEE Trans Inf Theory 52(12):5406–5425

    Article  MathSciNet  MATH  Google Scholar 

  • Cohen A, Dahmen W, DeVore R (2009) Compressed sensing and best \(k\)-term approximation. J Am Math Soc 22(1):211–231

    Article  MathSciNet  MATH  Google Scholar 

  • Davenport M, Wakin M (2009) Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Trans Inf Theory 56(9):4395–4401

    Article  MathSciNet  Google Scholar 

  • DeVore R (2007) Deterministic constructions of compressed sensing matrices. J Complex 23(4–6):918–925

    Article  MathSciNet  MATH  Google Scholar 

  • Donoho D, Tsaig Y, Drori I, Starck J (2006) Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. IEEE Trans Inf Theory 58(2):1094–1121

    Article  MathSciNet  Google Scholar 

  • Donoho D (2006) Compressed sensing. IEEE Trans Inf Theory 52(4):1289–1306

    Article  MathSciNet  MATH  Google Scholar 

  • Gilbert A, Indyk P (2010) Sparse recovery using sparse matrices. Proc IEEE 98(6):937–947

    Article  Google Scholar 

  • Gu B, Sheng S, Wang Z, Ho D, Osman S, Li S (2015) Incremental learning for v-support vector regression. Neural Netw 67:140–150

    Article  Google Scholar 

  • Ionin Y, Kaharaghani H (2007) Balanced generalized weighing matrices and conference matrices, in the CRC handbook of combinatorial designs, 2nd edn. CRC Press, Boca Raton

    Google Scholar 

  • Karystinos G, Pados D (2003) New bounds on the total squared correlation and optimum design of DS-CDMA binary signature sets. IEEE Trans Inf Theory 51(1):48–51

    Google Scholar 

  • Li S, Gao F, Ge G, Zhang S (2012) Deterministic construction of compressed sensing matrices via algebraic curves. IEEE Trans Inf Theory 58(8):5035–5041

    Article  MATH  Google Scholar 

  • Li S, Ge G (2014) Deterministic sensing matrices arising from near orthogonal systems. IEEE Trans Inf Theory 60(4):2291–2302

    Article  MathSciNet  MATH  Google Scholar 

  • Li S, Ge G (2014) Deterministic construction of sparse sensing matrices via finite geometry. IEEE Trans Signal Process 62(11):2850–2859

    Article  MathSciNet  Google Scholar 

  • Liu X, Jie Y (2016) New construction of deterministic compressed sensing matrices via singular linear spaces over finite fields. WSEAS Trans Math 15:176–184

    Google Scholar 

  • Natarajan B (1995) Sparse approximate solutions to linear systems. SIAM J comput 24(2):227–234

    Article  MathSciNet  MATH  Google Scholar 

  • Needell D, Tropp J (2009) CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal 26(3):301–321

    Article  MathSciNet  MATH  Google Scholar 

  • Strohmer T, Heath R (2003) Grassmannian frames with applications to coding and communication. Appl Comput Harmon Anal 14(3):257–275

    Article  MathSciNet  MATH  Google Scholar 

  • Troop J (2004) Greed is good: algorithmic result for sparse approximation. IEEE Trans Inf Theory 50(10):2231–2242

    Article  MathSciNet  Google Scholar 

  • Tropp J, Gilbert A (2007) Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inf Theory 53(12):4655–4666

    Article  MathSciNet  MATH  Google Scholar 

  • Tsaig Y, Donoho D (2006) Extensions of compressed sensing. Signal Process 86(3):549–571

    Article  MATH  Google Scholar 

  • Wan Z (2002) Geometry of classical groups over finite fields, 2nd edn. Science, Beijing

    Google Scholar 

  • Wang K, Guo J, Li F (2010) Association schemes based on attenuated spaces. Eur J Combin 31:297–305

    Article  MathSciNet  MATH  Google Scholar 

  • Wang K, Guo J, Li F (2011) Singular linear space and its applications. Finite Fields Appl 17:395–406

    Article  MathSciNet  MATH  Google Scholar 

  • Welch L (1974) Lower bounds on the maximum cross correlation of signals. IEEE Trans Inf Theory 20(3):397–399

    Article  MATH  Google Scholar 

  • Wootters W, Fields B (1989) Optimal state determination by mutually unbiased measurements. Ann Phys 191(2):363–381

    Article  MathSciNet  Google Scholar 

  • Xu L, Chen H (2015) Deterministic construction of RIP matrices in compressed sensing from constant weight codes. ScienceWISE, arXiv:1506.02568. Accessed 12 Jun 2015

  • Zhang J, Han G, Fang Y (2015) Deterministic construction of compressed sensing matrices from protograph LDPC codes. IEEE Trans Signal Process Lett 22(11):1960–1964

    Article  Google Scholar 

  • Zheng Y, Jeon B, Xu D, Wu QM, Zhang H (2015) Image segmentation by generalized hierarchical fuzzy C-means algorithm. J Intell Fuzzy Syst 28(2):961–973

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, People’s Republic of China

    Yingmo Jie

  2. School of Software Technology, Dalian University of Technology, Dalian, 116620, People’s Republic of China

    Cheng Guo

  3. Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Tuqiang Street, Dalian, 116620, People’s Republic of China

    Cheng Guo

  4. School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing, 210044, People’s Republic of China

    Zhangjie Fu

Authors
  1. Yingmo Jie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cheng Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhangjie Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yingmo Jie.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jie, Y., Guo, C. & Fu, Z. Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields. J Comb Optim 34, 245–256 (2017). https://doi.org/10.1007/s10878-016-0068-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-016-0068-y

Keywords

Search

Navigation