• DocumentCode
    53568
  • Title

    NP/CMP Equivalence: A Phenomenon Hidden Among Sparsity Models l_{0} Minimization and

  • Author

    Jigen Peng ; Shigang Yue ; Haiyang Li

  • Author_Institution
    Sch. of Math. & Stat., Xi´an Jiaotong Univ., Xi´an, China
  • Volume
    61
  • Issue
    7
  • fYear
    2015
  • fDate
    Jul-15
  • Firstpage
    4028
  • Lastpage
    4033
  • Abstract
    In this paper, we have proved that in every underdetermined linear system Ax = b, there corresponds a constant p*(A, b) > 0 such that every solution to the l p-norm minimization problem also solves the l0-norm minimization problem whenever 0 <; p <; p*(A, b). This phenomenon is named NP/CMP equivalence.
  • Keywords
    linear systems; minimisation; NP-CMP equivalence; information processing; lp-norm minimization problem; sparsity models l0 minimization; underdetermined linear system; Computational modeling; Information processing; Linear programming; Linear systems; Minimization; Optimization; Sparse matrices; $l_{p}$ minimization; Information processing; Sparse recovery; Sparse representation; Underdetermined linear system; lp minimization; sparse recovery; sparse representation; underdetermined linear system;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.2015.2429611
  • Filename
    7101837
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=53568