Bit precision analysis for compressed sensing

Bit precision analysis for compressed sensing. Ardestanizadeh, E., Cheraghchi, M., & Shokrollahi, A. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 1-5, 2009.

Link

Paper doi abstract bibtex

This paper studies the stability of some reconstruction algorithms for compressed sensing in terms of the bit precision. Considering the fact that practical digital systems deal with discretized signals, we motivate the importance of the total number of accurate bits needed from the measurement outcomes in addition to the number of measurements. It is shown that if one uses a $2k × n $ Vandermonde matrix with roots on the unit circle as the measurement matrix, $O(\ell + k łog \frac{n}{k})$ bits of precision per measurement are sufficient to reconstruct a $k$-sparse signal $x ∈ ℝ^n$ with dynamic range (i.e., the absolute ratio between the largest and the smallest nonzero coefficients) at most $2^\ell$ within $\ell$ bits of precision, hence identifying its correct support. Finally, we obtain an upper bound on the total number of required bits when the measurement matrix satisfies a restricted isometry property, which is in particular the case for random Fourier and Gaussian matrices. For very sparse signals, the upper bound on the number of required bits for Vandermonde matrices is shown to be better than this general upper bound.

@INPROCEEDINGS{ref:conf:ACS09,
  author =	 {Ehsan Ardestanizadeh and Mahdi Cheraghchi and Amin
                  Shokrollahi},
  title =	 {Bit precision analysis for compressed sensing},
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  year =	 2009,
  pages =	 {1-5},
  doi =		 {10.1109/ISIT.2009.5206076},
  url_Link =	 {https://ieeexplore.ieee.org/document/5206076},
  url_Paper =	 {https://arxiv.org/abs/0901.2147},
  abstract =	 {This paper studies the stability of some
                  reconstruction algorithms for compressed sensing in
                  terms of the \textit{bit precision}. Considering the
                  fact that practical digital systems deal with
                  discretized signals, we motivate the importance of
                  the total number of accurate bits needed from the
                  measurement outcomes in addition to the number of
                  measurements.  It is shown that if one uses a $2k
                  \times n $ Vandermonde matrix with roots on the unit
                  circle as the measurement matrix, $O(\ell + k \log
                  \frac{n}{k})$ bits of precision per measurement are
                  sufficient to reconstruct a $k$-sparse signal $x \in
                  \mathbb{R}^n$ with \textit{dynamic range} (i.e., the
                  absolute ratio between the largest and the smallest
                  nonzero coefficients) at most $2^\ell$ within $\ell$
                  bits of precision, hence identifying its correct
                  support. Finally, we obtain an upper bound on the
                  total number of required bits when the measurement
                  matrix satisfies a restricted isometry property,
                  which is in particular the case for random Fourier
                  and Gaussian matrices.  For very sparse signals, the
                  upper bound on the number of required bits for
                  Vandermonde matrices is shown to be better than this
                  general upper bound.  }
}

Downloads: 0