A new approach to derandomize compressed sensing matrices

-
Afonso Bandeira , Princeton University
Fine Hall 601

The restricted isometry property (RIP) is a compressed sensing matrix specification which leads to performance guarantees for a wide variety of sparse signal reconstruction algorithms. For the sake of quality sensing standards, practitioners desire deterministic sensing matrices, but the best known deterministic RIP matrices are vastly inferior to those constructed using random processes. This talk presents a new way to pursue good deterministic RIP matrices. Taking inspiration from certain work in number theory, we consider particular notions of pseudorandomness in a sequence, and we populate a sensing matrix with consecutive values of the Liouville function, starting at a random member of the sequence. Condicioned on the Chowla conjecture, we leverage the sequence's pseudorandomness so that very little randomness is needed to seed the construction. We suspect that a more refined notion of pseudorandomness will completely derandomize this construction.