Speaker: Matthew Fickus (Air Force Institute of Technology )

Title: Compressed Sensing with Equiangular Tight Frames

Abstract: Compressed sensing (CS) is changing the way we think about measuring very high-dimensional signals, such as hyperspectral images. Indeed, emerging hyperspectral camera prototypes are exploiting random apertures in order to greatly reduce the exposure times needed to measure such images. Here, the randomness of the aperture is due to the crucial role that random matrices play in CS. In short, in terms of CS’s restricted isometry property (RIP), random matrices far outshine all known deterministic matrix constructions. To be clear, for most deterministic constructions, it is unknown whether this performance shortfall (known as the “square-root bottleneck”) is simply a consequence of poor proof techniques or, more seriously, a flaw in the matrix design itself. We focus on this particular question in the special case of matrices formed from equiangular tight frames (ETFs). ETFs are overcomplete collections of unit vectors with minimal coherence, namely optimal packings of a given number of lines in a Euclidean space of a given dimension. We discuss the degree to which the recently-introduced Steiner and Kirkman ETFs satisfy the RIP. We further discuss how a popular family of ETFs, namely harmonic ETFs arising from McFarland difference sets, are particular examples of Kirkman ETFs. Overall, we find that many families of ETFs are shockingly bad when it comes to RIP, being provably incapable of exceeding the square-root bottleneck. Such ETFs are nevertheless useful in variety of other real-world applications, including waveform design for wireless communication.