A new approach to derandomize compressed sensing matrices

Dustin Mixon - Air Force Institute of Technology
Jan 21 2014 - 3:00pm
Event type: 
110 Fine Hall

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 and discrepancy theory, we consider particular notions of pseudorandomness in a sequence, and we populate a sensing matrix with consecutive members of such a sequence, starting at a random member of the sequence. To demonstrate RIP, we chiefly 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.