@comment{ generated by <http://infoscience.epfl.ch/> }

@InProceedings{ALGO-CONF-2009-002,
   abstract    = {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
                 \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
                 \R^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.},
   address     = { },
   affiliation = {EPFL},
   author      = {Ardestanizadeh, Ehsan and Cheraghchi, Mahdi and Shokrollahi, Amin},
   booktitle   = {Proceedings of the {IEEE} {I}nternational {S}ymposium on
                 {I}nformation {T}heory ({ISIT})},
   details     = {http://infoscience.epfl.ch/record/141317},
   documenturl = {http://infoscience.epfl.ch/record/141317/files/CS_ISIT09_camera.pdf},
   keywords    = {algoweb_misc},
   location    = {Seoul, Korea Republic},
   oai-id      = {oai:infoscience.epfl.ch:141317},
   oai-set     = {conf},
   pages       = {1--5},
   publisher   = { },
   review      = {REVIEWED},
   series      = { },
   status      = {PUBLISHED},
   title       = {Bit {P}recision {A}nalysis for {C}ompressed {S}ensing},
   unit        = {ALGO},
   url         = {http://www.isit2009.info/},
   year        = 2009
}