Density of Spherically-Embedded Stiefel and Grassmann Codes

Renaud-Alexandre Pitaval, Lu Wei, Olav Tirkkonen, Camilla Hollanti

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
120 Downloads (Pure)

Abstract

The density of a code is the fraction of the coding space covered by packing balls centered around the codewords. A high density indicates that a code performs well when used as a uniform point-wise discretization of an ambient space. This paper investigates the density of codes in the complex Stiefel and Grassmann manifolds equipped with the chordal distance arising from an Euclidean embedding, including the unitary group as a special case. The choice of distance enables the treatment of the manifolds as subspaces of Euclidean hyperspheres. In this geometry, the densest packings are not necessarily equivalent to maximum-minimum-distance codes. Computing a code’s density follows from computing i) the normalized volume of a metric ball and ii) the kissing radius, the radius of the largest balls one can pack around the codewords without overlapping. First, the normalized volume of a metric ball is evaluated by asymptotic approximations. The volume of a small ball can be wellapproximated by the volume of a locally-equivalent tangential ball. In order to properly normalize this approximation, the precise volumes of the manifolds induced by their spherical embedding are computed. For larger balls, a hyperspherical cap approximation is used, which is justified by a volume comparison theorem showing that the normalized volume of a ball in the Stiefel or Grassmann manifold is asymptotically equal to the normalized volume of a ball in its embedding sphere as the dimension grows to infinity. Then, bounds on the kissing radius are derived alongside corresponding bounds on the density. Unlike spherical codes or codes in flat spaces, the kissing radius of Grassmann or Stiefel codes cannot be exactly determined from its minimum distance. It is nonetheless possible to derive bounds on density as functions of the minimum distance. Stiefel and Grassmann codes have larger density than their image spherical codes when dimensions tend to infinity. Finally, the bounds on density lead to refinements of the standard Hamming bounds for Stiefel and Grassmann codes.
Original languageEnglish
Pages (from-to)225 - 248
Number of pages24
JournalIEEE Transactions on Information Theory
Volume64
Issue number1
Early online date2017
DOIs
Publication statusPublished - Jan 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • unitary matrix codes
  • spherical codes
  • Grassmann manifold
  • Stiefel manifold
  • density
  • packing
  • metric ball
  • volume
  • Hamming bound

Fingerprint Dive into the research topics of 'Density of Spherically-Embedded Stiefel and Grassmann Codes'. Together they form a unique fingerprint.

  • Cite this