TY - JOUR
T1 - The Road to Deterministic Matrices with the Restricted Isometry Property
AU - Bandeira, Afonso S.
AU - Fickus, Matthew
AU - Mixon, Dustin G.
AU - Wong, Percy
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013/12
Y1 - 2013/12
N2 - The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.
AB - The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.
KW - Compressed sensing
KW - Equiangular tight frames
KW - Restricted isometry property
UR - http://www.scopus.com/inward/record.url?scp=84888436702&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84888436702&partnerID=8YFLogxK
U2 - 10.1007/s00041-013-9293-2
DO - 10.1007/s00041-013-9293-2
M3 - Article
AN - SCOPUS:84888436702
VL - 19
SP - 1123
EP - 1149
JO - Journal of Fourier Analysis and Applications
JF - Journal of Fourier Analysis and Applications
SN - 1069-5869
IS - 6
ER -