Low-Coherence Frames From Group Fourier Matrices

Matthew Thill, Babak Hassibi

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Many problems in areas such as compressive sensing and coding theory seek to design a set of equal-norm vectors with large angular separation. This idea is essentially equivalent to constructing a frame with low coherence. The elements of such frames can in turn be used to build high-performance spherical codes, quantum measurement operators, and compressive sensing measurement matrices, to name a few applications. In this paper, we allude to the group-frame construction first described by Slepian and further explored in the works of Vale and Waldron. We present a method for selecting representations of a finite group to construct a group frame that achieves low coherence. Our technique produces a tight frame with a small number of distinct inner product values between the frame elements, in a sense approximating a Grassmannian frame. We identify special cases in which our construction yields some previously known frames with optimal coherence meeting the Welch lower bound, and other cases in which the entries of our frame vectors come from small alphabets. In particular, we apply our technique to the problem choosing a subset of rows of an Hadamard matrix so that the resulting columns form a low-coherence frame. Finally, we give an explicit calculation of the average coherence of our frames, and find regimes in which they satisfy the strong coherence property described by Mixon, Bajwa, and Calderbank.
Original languageEnglish (US)
Pages (from-to)3386-3404
Number of pages19
JournalIEEE Transactions on Information Theory
Issue number6
StatePublished - Jun 2017
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2021-04-06
Acknowledgements: This work was supported in part by the National Science Foundation under Grant CNS-0932428, Grant CCF-1018927, Grant CCF-1423663, and Grant CCF-1409204, in part by a Grant from Qualcomm Inc., in part by the NASA's Jet Propulsion Laboratory through the President and Director's Fund, and in part by the King Abdulaziz University, in part by the King Abdullah University of Science and Technology.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

ASJC Scopus subject areas

  • Library and Information Sciences
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Low-Coherence Frames From Group Fourier Matrices'. Together they form a unique fingerprint.

Cite this