Harmonic Grassmannian codes

Matthew Fickus, Joseph W. Iverson, John Jasper, Dustin G. MixonarXiv 2021 · OpenReview

TL;DR

This paper introduces a novel method for constructing new families of "harmonic" equi-isoclinic tight fusion frames (EITFFs), which are crucial for efficient compressed sensing. By leveraging Gauss sums over finite fields, the authors generate EITFFs with parameters that were previously difficult or impossible to achieve, expanding the known landscape of these important mathematical objects.

What Problem Does This Paper Address?

Compressed sensing aims to reconstruct signals from fewer measurements than traditionally required. A key component in achieving this efficiency is the use of dictionaries (sets of basis vectors or subspaces) that have minimal "block coherence." Equi-isoclinic tight fusion frames (EITFFs) are a specific type of dictionary that offers the strongest guarantees for recovering sparse signals. However, the existence of EITFFs with certain desirable parameters (like coprime dimensions) has been poorly understood, with most known examples arising from simpler constructions. This paper tackles the challenge of constructing new, non-trivial EITFFs, particularly those that are "harmonic" – meaning they are generated by a group action – and possess parameters that go beyond existing methods.

Methods

The core of the paper's contribution lies in its novel construction of harmonic EITFFs. The authors generalize the concept of harmonic frames, which are related to group representations and Fourier transforms. Their key idea is that a harmonic EITFF can be constructed from a smaller tight fusion frame with a well-behaved "Fourier transform." This "Fourier transform" is specifically related to Gauss sums over finite fields. The paper then uses these tools to build EITFFs with specific parameters, including those involving prime powers and specific dimensional relationships. They also leverage the theory of signature matrices and their relationship to EITFFs, providing a framework for verifying the existence and properties of these frames.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Harmonic EITFFs as a Generative Framework: The paper establishes that harmonic EITFFs, which are orbits of subspaces under group actions, can be systematically constructed from smaller tight fusion frames with specific "Fourier transform" properties. This provides a powerful new avenue for EITFF construction.
  • Gauss Sums as a Construction Tool: The paper demonstrates the utility of Gauss sums over finite fields in constructing these harmonic EITFFs, particularly for achieving specific parameter sets.
  • New Families of EITFFs: The authors successfully construct infinite families of EITFFs with parameters that were previously unknown or difficult to obtain, notably for prime powers and specific dimensional relationships.
  • Connection to Difference Sets: The work extends known equivalences between harmonic ETFs and difference sets to a more general setting involving harmonic fusion frames and difference projections, highlighting a deep combinatorial structure.

Key Results

The paper presents several key results, including:

  • New Infinite Families of EITFFs:
    • Harmonic EITFFs consisting of $Q$ planes in $\mathbb{C}^Q$ for each prime power $Q \geq 4$.
  • Harmonic EITFFs consisting of $Q-1$ planes in $\mathbb{C}^Q$ for each odd prime power $Q$.
  • A real harmonic EITFF(11,11,3).
  • Characterization of Harmonic EITFFs: The paper provides a characterization of when a harmonic tight fusion frame is equichordal or equi-isoclinic, linking it to the properties of its generating frame's "Fourier transform."
  • Generalization of Difference Set Theory: The work extends the classical relationship between harmonic ETFs and difference sets to a broader context of harmonic fusion frames and difference projections.

Limitations and Future Work

The authors acknowledge that while their method provides new constructions, it doesn't cover all possible EITFFs. They specifically mention that their constructions do not always yield EITFFs with "minimal" R parameters, and that the problem of constructing EITFFs with arbitrary coprime parameters remains open. They also suggest future work on generalizing their constructions to yield other types of EITFFs and exploring the connection to balanced incomplete block designs (BIBDs) more deeply. The paper also poses a question about the equivalence of complex symmetric and skew-symmetric conference matrices.

Summary updated

Abstract

An equi-isoclinic tight fusion frame (EITFF) is a type of Grassmannian code, being a sequence of subspaces of a finite-dimensional Hilbert space of a given dimension with the property that the smallest spectral distance between any pair of them is as large as possible. EITFFs arise in compressed sensing, yielding dictionaries with minimal block coherence. Their existence remains poorly characterized. Most known EITFFs have parameters that match those of one that arose from an equiangular tight frame (ETF) in a rudimentary, direct-sum-based way. In this paper, we construct new infinite families of non-"tensor-sized" EITFFs in a way that generalizes the one previously known infinite family of them as well as the celebrated equivalence between harmonic ETFs and difference sets for finite abelian groups. In particular, we construct EITFFs consisting of $Q$ planes in $\mathbb{C}^Q$ for each prime power $Q\geq 4$, of $Q-1$ planes in $\mathbb{C}^Q$ for each odd prime power $Q$, and of $11$ three-dimensional subspaces in $\mathbb{R}^{11}$. The key idea is that every harmonic EITFF -- one that is the orbit of a single subspace under the action of a unitary representation of a finite abelian group -- arises from a smaller tight fusion frame with a nicely behaved "Fourier transform." Our particular constructions of harmonic EITFFs exploit the properties of Gauss sums over finite fields.
BibTeX
@misc{fickus2021harmonic,
  author = {Matthew Fickus and Joseph W. Iverson and John Jasper and Dustin G. Mixon},
  title = {{Harmonic Grassmannian codes}},
  year = {2021},
  eprint = {2112.14267},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14267},
}

Loading related content...

Figure