Computer Science/Discrete Mathematics Seminar II

Sparse recovery problems arise in many applications. Suppose v is an unknown N-dimensional signal with at most k nonzero components. We call such signals k-sparse. Suppose we are able to collect n \ll N linear measurements of v , and wish to efficiently recover v from these. The measurements are given as the n-dimensional vector \Phi_v, where \Phi is some n × N matrix. Exact recovery is possible with n \geq 2k. However, the sparse recovery problem in general is known to be NP-hard. Nevertheless, E. Cand´es, J. Romberg and T. Tao established that for some matrices this highly non-convex combinatorial problem is equivalent to a linear programming problem, and it can be effectively solved. This holds, in particular, for matrices possessing Restricted Isometry Property (RIP) with good parameters (the precise definitions will be given in the talk). Moreover, it was shown that a random matrix satisfy this property with a high probability, but it is very important to construct such matrices explicitly. The seminal papers by Cand´es, Romberg and Tao appeared about 5 years ago, and since then many significant results related to effective sparse signal recovery and RIP matrices have been obtained. The Restricted Isometry Property of a matrix is connected with its coherence parameter. In turn, the problem of construction of matrices with a small coherence parameter is related to other famous extremal problems of Harmonic Analysis and Number Theory. In all known explicit constructions for RIP, the RIP parameters are estimated in terms of coherence parameters. This dependence created a limitation for RIP parameters. In our construction we overcome the barrier by using modern methods of Additive Combinatorics. Also, we present an elementary explicit construction of matrices with small coherence parameters for large N. Our approach is motivated by the paper by M. Ajtai, H. Iwaniec, J. Koml´os, J. Pints and E. Szemer´edi. The talk is based on a joint paper with J. Bourgain, S. Dilworth, K. Ford, and D. Kutzarova.