May 6, 2012

Zero, one, and infinity in compressed sensing

I am very happy I got many comments for my first "technical" blog, where I made a question on relationship between zero and infinity norms in CS (compressed sensing).

Igor pointed out his blog entries (here and here)  in his comment.  According to the entry, an L-infinity optimization may produce a vector the elements of which are sticked to ±||x||_∞.  Applying DFT to such a vector, e.g., x=(1,1,...,1), result in a sparse vector in the Fourier domain.  This may be a simple explanation why the infinity norm is related to CS.

Mahesh and Thomas pointed out the infinity norm is also used in the Dantzig selector. This is based on the fact that L-1 (ell-1) is the dual vector space of L-infinity (ell-infinity).  This is yet another link between zero and infinity (note that L-1 is related to L-0 by so many studies on CS). This also interests me very much.


  1. Masaaki,

    You might also be interested in this paper

    In the figure "A summary of the recovery bounds obtained using Gaussian width arguments."

    there is this info about +/-1 vector being recoverable with gaussian matrices with p/2 rows.

    of related interest:[Cevher,%20Figueiredo].pdf


    1. Igor,

      Thanks a lot for linking nice pdf's.

      At p.4 of the tutorial slides, I remember Volkan had a lecture at my university, Kyoto univ, just after ICASSP2012. The lecture was nice on high-dimensional statistics, which is different from one you suggested, but he also used the "<S>parsity" notation (<S> for the trademark of Superman). That's why I remember Volkan's lecture from the tutorial slides.

      Best regards,