Date:	Mon, October 28, 2013
Time:	17:15
Place:	Research II Lecture Hall

Abstract: Subsampled convolutions appear in various sensing mechanisms such as coded aperture imaging and remote sensing. In the underlying model, the signal is convolved with a filter, which can be at least partially influenced by the measurement setup. Then the resulting measurement is subsampled.

In this talk we will argue that for signal processing efficiency, a random choice of this filter is useful. Namely, such a setup allows for compressed sensing: signal recovery is possible despite the subsampling provided the underlying signal is approximately sparse, i.e., it is well-approximated by a vector most of whose entries vanish. A key concept for the underlying proofs is the Restricted Isometry Property (RIP). A is said to have the RIP, if its restriction to any small subset of the columns acts almost like an isometry. As we will argue, the RIP also has applications in dimension reduction and quantization.

The result presented establishes the RIP for subsampled random convolutions with high probability if the embedding dimension is bigger than Cslog(n)⁴. This bound exhibits optimal dependence on s while previous works had only obtained a suboptimal scaling of s^3/2.

This talk is based on joint works with Shahar Mendelson and Holger Rauhut, Joe-Mei Feng, and Rachel Ward.