Blog
About

0
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Robust Decoding from Binary Measurements with Cardinality Constraint Least Squares

      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

          The main goal of 1-bit compressive sampling is to decode \(n\) dimensional signals with sparsity level \(s\) from \(m\) binary measurements. This is a challenging task due to the presence of nonlinearity, noises and sign flips. In this paper, the cardinality constraint least square is proposed as a desired decoder. We prove that, up to a constant \(c\), with high probability, the proposed decoder achieves a minimax estimation error as long as \(m \geq \mathcal{O}( s\log n)\). Computationally, we utilize a generalized Newton algorithm (GNA) to solve the cardinality constraint minimization problem with the cost of solving a least squares problem with small size at each iteration. We prove that, with high probability, the \(\ell_{\infty}\) norm of the estimation error between the output of GNA and the underlying target decays to \(\mathcal{O}(\sqrt{\frac{\log n }{m}}) \) after at most \(\mathcal{O}(\log s)\) iterations. Moreover, the underlying support can be recovered with high probability in \(\mathcal{O}(\log s)\) steps provided that the target signal is detectable. Extensive numerical simulations and comparisons with state-of-the-art methods are presented to illustrate the robustness of our proposed decoder and the efficiency of the GNA algorithm.

          Related collections

          Author and article information

          Journal
          03 June 2020
          Article
          2006.02890

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

          Custom metadata
          arXiv admin note: text overlap with arXiv:1711.01206
          cs.IT math.IT

          Numerical methods, Information systems & theory

          Comments

          Comment on this article