Blog
About

  • Record: found
  • Abstract: found
  • Article: found
Is Open Access

Sparse Recovery With Integrality Constraints

Preprint

Read this article at

Bookmark
      There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

      Abstract

      In this paper, we investigate conditions for the unique recoverability of sparse integer-valued signals from few linear measurements. Both the objective of minimizing the number of nonzero components, the so-called \(\ell_0\)-norm, as well as its popular substitute, the \(\ell_1\)-norm, are covered. Furthermore, integer constraints and possible bounds on the variables are investigated. Our results show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. Moreover, even though the considered problems are NP-hard in general (even with an \(\ell_1\)-objective), we investigate testing the \(\ell_0\)-recovery conditions via some numerical experiments; it turns out that the corresponding problems are quite hard to solve in practice. However, medium-sized instances of \(\ell_0\)- and \(\ell_1\)-minimization with binary variables can be solved exactly within reasonable time.

      Related collections

      Author and article information

      Journal
      2016-08-30
      1608.08678

      http://arxiv.org/licenses/nonexclusive-distrib/1.0/

      Custom metadata
      cs.IT math.IT math.OC

      Numerical methods, Information systems & theory

      Comments

      Comment on this article

      Similar content 3,437