Source-linked AI summary
Constructing packings in Grassmannian manifolds via alternating projection
I. S. Dhillon, R. W. Heath, T. Strohmer, J. A. Tropp
TL;DR
The paper addresses how to construct good packings in Grassmannian manifolds and projective spaces across several metrics. It uses alternating projection on structural and spectral matrix constraints, often obtaining packings that compete with known results and are nearly optimal in many cases.
Problem
Constructing optimal or high-quality packings in Grassmannian and projective spaces is difficult because the feasibility problem is highly nonconvex.
Method
The method alternately enforces structural and spectral properties of a Gram matrix, then factors the resulting matrix to extract a subspace packing.
Results
The method often matches the best known packings, extends to previously unstudied metrics and spaces, and produces many configurations that are essentially optimal relative to Rankin bounds.
Takeaways & Limitations
Alternating projection is an effective, versatile numerical algorithm for packing problems, including complex Grassmannian packings relevant to wireless communications.
Takeaways & Limitations
The method can struggle with degenerate configurations, including cases where optimal packings are subsets of larger arrangements.
Abstract
from arXiv · showhide
This paper describes a numerical method for finding good packings in Grassmannian manifolds equipped with various metrics. This investigation also encompasses packing in projective spaces. In each case, producing a good packing is equivalent to constructing a matrix that has certain structural and spectral properties. By alternately enforcing the structural condition and then the spectral condition, it is often possible to reach a matrix that satisfies both. One may then extract a packing from this matrix. This approach is both powerful and versatile. In cases where experiments have been performed, the alternating projection method yields packings that compete with the best packings recorded. It also extends to problems that have not been studied numerically. For example, it can be used to produce packings of subspaces in real and complex Grassmannian spaces equipped with the Fubini--Study distance; these packings are valuable in wireless communications. One can prove that some of the novel configurations constructed by the algorithm have packing diameters that are nearly optimal.
1. Introduction
The paper develops a flexible numerical approach to packing points or subspaces in compact metric spaces, especially Grassmannian manifolds. Alternating projection enforces structural and spectral matrix conditions, producing packings that often match known results while extending to less-studied settings.
- Packing seeks finite configurations whose closest pair is as far apart as possible, with Grassmannian subspace packing linked to applications in quantum computing and wireless communications.
- The paper targets feasibility problems: given ρ, construct N points whose pairwise distances meet the required threshold, although maximizing feasible ρ is highly nonconvex.
- Alternating projection is flexible and easy to implement, and modifications apply across Grassmannian metrics and previously unstudied packing problems.
- The method represents configurations by matrices, then alternately enforces structural and spectral conditions before extracting a subspace configuration.
- The method may converge slowly, lack numerical precision, and perform poorly when the ambient dimension or number of subspaces is large.
- Experiments often match the best known packings, while the method is particularly effective for complex packings with few subspaces in low-dimensional ambient spaces.
2. Packing in Grassmannian Manifolds
Grassmannian packings arrange subspaces using principal angles and metrics derived from them. Block Gram matrices encode these configurations, converting distance constraints into structural and spectral matrix conditions.
- The complex Grassmannian G(K, C^d) consists of K-dimensional subspaces of C^d, while the real analogue uses R^d; projective space is the K = 1 case.
- Two K-dimensional subspaces have K principal angles in [0, π/2], and the metrics considered are functions of these angles.
- For orthonormal basis matrices S and T, the singular values of S*T are the cosines of the principal angles, giving a computationally convenient representation.
- The chordal, spectral, Fubini–Study, and geodesic distances provide different Grassmannian packing objectives; Fubini–Study distance is important in wireless communications.
- A configuration becomes a block Gram matrix whose diagonal blocks are identities and whose off-diagonal singular values encode pairwise principal angles.
- Packing feasibility is equivalent to constructing a Gram matrix with suitable off-diagonal magnitudes, positive semidefiniteness, bounded rank, and fixed diagonal blocks.
3. Alternating Projection for Chordal Distance
For chordal-distance packing, the algorithm alternates projections onto structural and spectral constraint sets for Gram matrices. Its output can be factored into subspaces, but convergence and initialization impose practical limitations.
- A feasible Gram matrix is Hermitian, has identity diagonal blocks, bounded off-diagonal Frobenius norms, is positive semidefinite, has rank at most d, and has trace KN.
- Structural constraints control matrix entries, whereas spectral constraints control eigenvalues; alternating projection handles these categories in successive steps.
- Each iteration computes a nearest structural matrix and then a nearest spectral matrix, repeating for a fixed number of iterations before diagonal-block normalization.
- Iterates are not guaranteed to converge in norm, although infinite sequences have accumulation points satisfying the constraint-set conclusions described by the convergence theorem.
- The output always factors into a subspace configuration, while the off-diagonal magnitude condition may remain violated.
- The structural projection preserves admissible off-diagonal blocks by scaling any block whose Frobenius norm exceeds the threshold μ.
- The spectral projection uses an eigenvalue decomposition, retains at most d nonnegative eigenvalues, and adjusts them to satisfy the trace constraint.
- Initialization can fail when the similarity threshold is too small or random choices are unfavorable, motivating an iteration counter and thresholds near the maximum value.
4. Bounds on the Packing diameter
The paper develops upper bounds for Grassmannian packing diameters and shows that attaining them forces strong geometric regularity, including equidistance and equi-isoclinicity. These bounds provide benchmarks for assessing numerical packings, although some equi-isoclinic bounds are not believed to be sharp.
- Upper bounds on packing diameter let the authors identify numerically constructed configurations that are nearly optimal.A packing close to its upper bound must have a packing diameter close to optimal.
- The Rankin bound gives an upper bound for chordal-distance packings by embedding the Grassmannian into a Euclidean sphere.The nomenclature reflects this spherical embedding and application of the classical Rankin bound.
- Attaining the chordal-distance bound makes all pairs of subspaces equidistant, with real and complex attainment subject to different limits on N.The real case requires N ≤ 1/2 d(d + 1), while the complex case requires N ≤ d^2.
- A novel spectral-distance corollary provides an analogous packing-diameter bound, and equality implies that the packing is equi-isoclinic.Equi-isoclinic means all principal angles between every pair of subspaces are identical.
- The available upper bound on the number of equi-isoclinic subspaces is not believed to be sharp.The stated real and complex bounds are 2K(K + 1) + 1 and d^2 − K^2 + 1, respectively.
5. Experiments
Experiments apply alternating projection to projective-space packings and compare the resulting configurations with known records or theoretical bounds. The method often approaches the best known values, but performance worsens for larger configurations and can miss degenerate optima.
- The complex projective results were evaluated against the Rankin bound because comparable numerical tables were unavailable.The real case could instead be compared with Sloane’s tabulated world records.
- Alternating projection consistently produced best real projective packings within tenths or hundredths of a degree of known configurations.For (d, N) = (5, 16), fewer than 1000 iterations were needed on average to get within 0.001 degrees of optimal.
- Performance generally improves when N is small, while larger N produces larger errors and requires more iterations.The experiments identify a systematic dependence on the number of points.
- Complex line packings sometimes came within a thousandth of a degree of the Rankin bound, although the bound is usually unattainable.These cases were judged essentially optimal.
- Some computed configurations were anomalously worse than larger configurations because optimal arrangements for smaller N can be subsets of larger optimal configurations.The paper highlights this issue for P4(C), including the optimal configuration of 25 lines.
- Real and complex projective packings differ markedly, with equal packing diameters occurring only when the real configuration meets the Rankin bound.The complex space contains the real projective space isometrically.
5.2. The Chordal Distance.
For chordal-distance Grassmannian packings, alternating projection is compared with Sloane’s records in the real case and with the Rankin bound in the complex case. Many configurations are essentially optimal, but performance declines near parameter limits and for degenerate subset configurations.
- Real chordal experiments used Sloane-derived feasibility parameters and 5000 alternating-projection iterations for each tested triple.The complex experiments likewise used Rankin-bound parameters and random starting points.
- Many real chordal packings attained squared packing diameters within 10^-3 of Sloane’s best recorded values.The algorithm was especially successful for smaller numbers of subspaces, with performance flagging as N approached 20.
- Degenerate configurations were difficult to locate precisely when smaller optimal arrangements were subsets of a larger optimal configuration.The anomaly for 11–16 subspaces in R4 is explained by the optimal 17-subspace configuration.
- Real and complex packings nearly meet the Rankin bound wherever it is attainable, but real packing diameters fall off beyond the real attainment limit.The comparison concerns best configurations in the two Grassmannian spaces.
- The algorithm failed for the best arrangements of 17 and 18 subspaces in G(2, C4), which were slightly worse than corresponding real arrangements.This contradicts the expected advantage of the complex setting in those cases and is identified as an algorithmic failure.
5.3. The Spectral Distance.
The spectral-distance experiments adapt the alternating-projection feasibility formulation to singular-value constraints and compare results with a novel spectral Rankin bound. Some configurations are equi-isoclinic and near-optimal, but the method has notable failures in particular real cases.
- The spectral-distance problem uses a modified alternating-projection procedure for feasibility in Grassmannian manifolds.The paper introduces the spectral constraint set and a nearest-matrix projection based on singular-value truncation.
- The nearest feasible off-diagonal block is obtained by truncating singular values that exceed the threshold µ.Convexity and singular-value structure yield the unique Frobenius-norm projection.
- Some spectral packings essentially meet the Rankin bound and are therefore equi-isoclinic.The experiments ran alternating projection for 5000 iterations across feasibility parameters from the minimum to twice the minimum.
- The algorithm always produced zero packing diameter for 8 and 9 subspaces in G(3, R6), despite nonzero-diameter random starting points.The authors report that they do not understand this failure.
- Complex spectral packings generally outperform real ones; every tested configuration in G(2, C6) nearly meets the Rankin bound.Only two real configurations achieved the same distinction, while few G(2, C5) arrangements came close.
5.4. The Fubini–Study Distance.
The paper extends alternating projection to Fubini–Study packings, where the problem lacks prior experimental or theoretical study and general upper bounds. Experiments reach maximum diameter for small configurations, while larger cases remain difficult to assess and scale.
- The Fubini–Study packing problem lacks prior experimental or theoretical treatments and general upper bounds for evaluating configurations.This makes quality assessment especially difficult in the new setting.
- The method alternates structural and spectral constraints through matrix-nearness problems, including a nonlinear formulation for off-diagonal blocks.The nearest feasible matrix has a block-identity diagonal, while its off-diagonal blocks are obtained using singular-value structure and constrained optimization.
- The implementation used Matlab nonlinear programming and ran 100 to 500 iterations for selected parameter triples and feasibility values.The exploratory experiments were limited because the implementation was too slow for more iterations.
- For small N, the packings attain the maximum possible packing diameter π/2, indicating success in those cases.
- For larger N, the packing quality cannot be judged against optimality, and larger-scale studies require faster nonlinear programming and implementation.The authors leave detailed Fubini–Study packing analysis for future research.
- Complex packings are at least as good as real packings, while their smooth quality decline suggests undiscovered order in packing diameters.
6. Discussion
Grassmannian packings connect to wireless communication through noncoherent signaling and subspace quantization. The discussion concludes that alternating projection is versatile, often matches known packings, and extends to numerically unexplored problems.
- Subspace packings arise in noncoherent communication and subspace quantization, with the latter having strong practical impact in multiple-antenna systems.
- In noncoherent communication, information-theoretic analyses identify optimal transmit signals with packings in G(K, C^d), where K and d reflect system dimensions and channel coherence.
- Prior approaches include numerical line-packing algorithms, structured Fourier constructions, and complex chordal-packing methods, but they have limitations such as missing properties or nonoptimality.
- The same application area uses chordal, spectral, and Fubini–Study distances for optimal subspace quantizers.
- Alternating projection solves diverse packing problems, often matches the best known packings, extends to unstudied cases, and yields configurations shown by Rankin bounds to be essentially optimal.
Appendix A. Tammes’ Problem
The appendix applies alternating projection to Tammes’ problem, the long-studied task of packing points on a sphere. It situates the method alongside extensive records of putatively optimal configurations.
- Alternating projection is applied to packing points on a sphere in Tammes’ Problem.
- The problem has received extensive attention over 75 years, with tables of putatively optimal packings available for comparison.
A.1. Modifications to Algorithm.
For spherical point packings, the algorithm retains the spectral constraint and reduces the structural projection to a simple matrix-nearness operation. The nearest feasible matrix has unit diagonal and clipped off-diagonal entries.
- The spherical feasibility problem seeks N unit-sphere points with packing diameter ρ subject to bounded pairwise inner products.
- The spectral constraint set remains unchanged, and the associated matrix-nearness problem is trivial to solve.
- The unique nearest feasible matrix has a unit diagonal and off-diagonal entries clipped to the interval [−1, µ].
A.2. Numerical Results.
The experiments show that alternating projection often produces packings close to recorded optima, with performance depending on the number and structure of points. It also recovers known optimal configurations accurately in many three-dimensional cases, while exhibiting specific failures.
- Best configurations typically fall within hundredths or thousandths of a degree of Sloane’s recorded packing diameters.Maximum inner-product differences are usually on the order of 10^-4 or 10^-5.
- Average configurations typically achieve packing diameters only several tenths of a degree from optimal.
- Performance generally improves for smaller N, while larger point sets produce larger errors and require more iterations.The authors associate these trends with combinatorial and random regimes in Tammes’ Problem.
- For d = 3, the algorithm calculates known optimal configurations to high accuracy and generally performs better on nondegenerate cases.Established cases include N = 1, 2, . . . , 12 and N = 24.
- The algorithm misses the optimal packing diameter for the 24-point packing on S3 by 1.79°, with smaller failures at five additional parameter pairs.The additional cases are (d, N) = (3, 25), (4, 14), (4, 25), (5, 22), and (5, 23).
Appendix B. Tables and Figures
The tables and figures report experimental calculations rather than definitive best packings, and additional effort could improve many of the reported packing diameters.
- The reported packing diameters are experimental results that may improve with additional effort.