Compressed Sensing with Equiangular Tight Frames
Matt Fickus, Air Force Institute of Technology
Location: Stevenson 1307
Compressed sensing (CS) is changing the way we think about measuring high-dimensional signals and images. In particular, CS promises to revolutionize hyperspectral imaging. Indeed, emerging camera prototypes are exploiting random masks in order to greatly reduce the exposure times needed to form hyperspectral images. Here, the randomness of the masks 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. In the remainder of this talk, 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 and algebraic coding theory.