Statistical mechanics analysis of thresholding 1-bit compressed sensing

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Yingying Xu
  • Yoshiyuki Kabashima

Research units

  • Tokyo Institute of Technology

Abstract

The one-bit compressed sensing framework aims to reconstruct a sparse signal by only using the sign information of its linear measurements. To compensate for the loss of scale information, past studies in the area have proposed recovering the signal by imposing an additional constraint on the l 2-norm of the signal. Recently, an alternative strategy that captures scale information by introducing a threshold parameter to the quantization process was advanced. In this paper, we analyze the typical behavior of thresholding 1-bit compressed sensing utilizing the replica method of statistical mechanics, so as to gain an insight for properly setting the threshold value. Our result shows that fixing the threshold at a constant value yields better performance than varying it randomly when the constant is optimally tuned, statistically. Unfortunately, the optimal threshold value depends on the statistical properties of the target signal, which may not be known in advance. In order to handle this inconvenience, we develop a heuristic that adaptively tunes the threshold parameter based on the frequency of positive (or negative) values in the binary outputs. Numerical experiments show that the heuristic exhibits satisfactory performance while incurring low computational cost.

Details

Original languageEnglish
Article number083405
Pages (from-to)1-16
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2016
Issue number8
Publication statusPublished - 22 Aug 2016
MoE publication typeA1 Journal article-refereed

    Research areas

  • analysis of algorithms, cavity and replica method, statistical inference

ID: 7390634