English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Binary Iterative Hard Thresholding (BIHT) algorithm is a popularreconstruction method for one-bit compressed sensing due to its simplicity andfast empirical convergence. There have been several works about BIHT but atheoretical understanding of the corresponding approximation error andconvergence rate still remains open.  This paper shows that the normalized version of BIHT (NBHIT) achieves anapproximation error rate optimal up to logarithmic factors. More precisely,using $m$ one-bit measurements of an $s$-sparse vector $x$, we prove that theapproximation error of NBIHT is of order $O \left(1 \over m \right)$ up tologarithmic factors, which matches the information-theoretic lower bound$\Omega \left(1 \over m \right)$ proved by Jacques, Laska, Boufounos, andBaraniuk in 2013. To our knowledge, this is the first theoretical analysis of aBIHT-type algorithm that explains the optimal rate of error decay empiricallyobserved in the literature. This also makes NBIHT the first provablecomputationally-efficient one-bit compressed sensing algorithm that breaks theinverse square root error decay rate $O \left(1 \over m^{1/2} \right)$.

NBIHT: An Efficient Algorithm for 1-bit Compressed Sensing with Optimal Error Decay Rate