NBIHT: An Efficient Algorithm for 1-Bit Compressed Sensing With Optimal Error Decay Rate

DOI10.1109/TIT.2021.3124598MaRDI QIDQ5030352zbMATHOpenAlexFDO

Authors Michael P. Friedlander, Halyun Jeong, Özgür Yılmaz, Y. Plan

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.12886

zbMATH Keywords

binary iterative hard thresholding algorithmoptimal rate of error decayreconstruction method for one-bit compressed sensing

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The Binary Iterative Hard Thresholding (BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. There have been several works about BIHT but a theoretical understanding of the corresponding approximation error and convergence rate still remains open. This paper shows that the normalized version of BIHT (NBHIT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using $m$ one-bit measurements of an $s$-sparse vector $x$, we prove that the approximation error of NBIHT is of order $Oleft(1overmight)$ up to logarithmic factors, which matches the information-theoretic lower bound $Omegaleft(1overmight)$ proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square root error decay rate $Oleft(1over{m}^{1/2}ight)$.

Recommendations

• One-bit compressed sensing by greedy algorithms
• Noisy 1-bit compressive sensing: models and algorithms
• One-Bit Compressive Sensing With Norm Estimation
• Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• One-bit compressed sensing with non-Gaussian measurements
• Stability of 1-bit compressed sensing in sparse data reconstruction
• Robust 1-bit compressed sensing via hinge loss minimization

Cited in

(1)

• Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints

This page was built for publication: NBIHT: An Efficient Algorithm for 1-Bit Compressed Sensing With Optimal Error Decay Rate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030352)