Gauge-Aware Deflated Search for Tight Fusion Frames in the Low-Redundancy Gap

A tight frame is a redundant set of vectors that reconstructs any signal as simply as an orthonormal basis does. A fusion frame is the same idea built from subspaces instead of single vectors, as when each sensor in a network reports a projection of the signal. Exact algebraic recipes exist for building these objects when there are at least twice as many vectors as dimensions. In the low-redundancy regime, between one and two times as many vectors as dimensions, the classical test for whether a requested design can exist becomes necessary but no longer sufficient. Below that boundary nobody knows which designs are realizable. The obvious response is numerical search, but the search space is non-convex and full of near-misses. The one paper in this area that tried continuous search on related matrix problems reported that it stalled in local minima.

This note proposes a search procedure that attacks that stall with two ingredients. First, we parameterize candidate frames with constant-modulus matrices, whose entries all share the same magnitude. Scaling their rows changes the spectrum without changing any column norm, so two of the three design constraints hold exactly by construction, and the optimizer only has to satisfy the remaining one. Second, we run sequential restarts that are explicitly pushed away from previously found minima. The push is measured in quantities that do not change when a frame is rotated, its vectors re-phased, or its subspaces relabeled. Without this, naive restarts mostly rediscover the same stuck solution in disguise. The output is meant to be mathematics, not a leaderboard entry: verified new constructions, and a census of local minima that turns repeated failure into evidence about where infeasibility begins.

Background and the gap

The constructive theory comes from the Spectral Tetris line of work. Constructions and existence of tight fusion frames builds unit-norm tight frames from small 1×1 and 2×2 blocks, then modulates them into equal-dimension tight fusion frames. It proves existence when $2L<N$, $L\nmid N$ and $K>\lceil N/L\rceil+2$, and it shows that $KL>N$ and, for $L\nmid N$, $K>\lceil N/L\rceil+1$ are necessary. Spectral tetris fusion frame constructions extends this to arbitrary spectra using row-scaled DFT matrices. It shows that the criterion based on majorization (an ordering of how spread out two sequences are) is necessary and sufficient once redundancy reaches 2, but only necessary below 2. Necessary and sufficient conditions to perform Spectral Tetris characterizes when the block-stacking algorithm itself succeeds below redundancy 2. That result constrains our design: wherever Spectral Tetris applies, it is an exact competitor we must not pretend to beat. The open territory is the set of majorization-feasible requests that Spectral Tetris cannot build. These papers motivate the problem and supply the row-scaling identity we reuse, but none of them searches.

On the optimization side, Sharp results for NIEP and NMF is the closest precedent. When its Haar and DFT constructions failed on a residual set of nonnegative inverse eigenvalue cases, the authors fell back to optimization over orthogonal matrices. They report that this was costly and became trapped in local minima or saddles, and they leave globally convergent manifold search open. That is the motivating negative result.

The diversity literature supplies the escape mechanism but in a form that does not transfer directly. Discovering alternative solutions beyond the simplicity bias in recurrent neural networks trains successive networks while penalizing linear predictability from earlier ones, a Gram-Schmidt-like deflation. Divergence-Guided Particle Swarm Optimization repels particles from the swarm's best point with a Gaussian distance kernel. Both measure similarity in raw coordinates. For frames this is the wrong metric, because a rotated or re-phased copy of a stuck frame is far away in coordinates but is the same frame. Our contribution is to deflate in invariants instead.

Core Claim

We claim that combining two things makes low-redundancy existence questions searchable at sizes where plain restarts stall. One is a constant-modulus parameterization that enforces spectrum and column norms exactly. The other is deflation measured on gauge invariants, meaning quantities unchanged by rotating the frame, re-phasing vectors, or relabeling subspaces. Searchable means two things. Solutions are found reliably on known-feasible controls. On open instances, the census of distinct minima stabilizes, so it can be read as evidence rather than noise.

Concretely, let $U\in\mathbb{C}^{N\times M}$ have entries $U_{jk}=e^{i\theta_{jk}}/\sqrt{M}$, with phases $\theta$ as the free variables. Let $D=\mathrm{diag}(\sqrt{\lambda_1},\dots,\sqrt{\lambda_N})$ carry the target spectrum, with $\sum_j\lambda_j=M$. The synthesis matrix is $\Phi=DU$, and by the constant-modulus identity every column of $\Phi$ has unit norm for every choice of $\theta$. What remains is a single residual.

$$\mathcal{L}(\theta)=\|UU^*-\tfrac{1}{M}\cdot M\, I_N\|_F^2\cdot 0+\|UU^*-I_N\|_F^2+\sum_{b}\|\Phi_b^*\Phi_b-I_{L_b}\|_F^2$$

Here the first term vanishes and is written only to make clear that it is dropped. The second term forces the rows of $U$ to be orthonormal, so that the frame operator $\Phi\Phi^*$ equals $\mathrm{diag}(\lambda)$. The third term forces each block $\Phi_b$ of $L_b$ columns to be orthonormal, so that each block spans a subspace and the blocks together form a fusion frame. A zero of $\mathcal{L}$ is an exact solution, which we then polish and verify in high precision. In practice we implement $\mathcal{L}$ with only the last two terms.

After finding minima $\theta^{(1)},\dots,\theta^{(r)}$, the $(r{+}1)$-th run minimizes the deflated objective

$$\mathcal{L}_{r+1}(\theta)=\mathcal{L}(\theta)\prod_{s=1}^{r}\Big(1+\frac{\alpha}{\,\|g(\theta)-g(\theta^{(s)})\|^{2}}\Big),$$

where $\alpha>0$ is a strength parameter. The invariant map $g$ returns the sorted multiset of subspace overlaps $\mathrm{tr}(P_aP_b)$, with $P_a$ the projection onto block $a$, together with the sorted moduli of the Gram matrix $\Phi^*\Phi$. These quantities are unchanged by unitaries, phases and permutations, so deflation can only be satisfied by moving to a genuinely new configuration.

A limitation follows from the parameterization. The constant-modulus family is a strict subset of all frames, so failure inside it does not rule out existence. We therefore pair it with an unrestricted arm that searches over $N\times M$ matrices with orthonormal rows, under the same deflation, and we report both.

Research Program

The work has three stages.

The first stage builds and validates the solver on instances with known answers. Positive controls are equal-dimension instances certified by the existence theorem of Constructions and existence of tight fusion frames, including its explicit (5,4,11) example, plus non-flat spectra that DFT Spectral Tetris builds. Negative controls are instances violating $KL>N$ or $K>\lceil N/L\rceil+1$, which must never return a verified solution.

The second stage is a systematic sweep of majorization-feasible, low-redundancy requests with $N\le 16$ that no Spectral Tetris variant constructs. For each request we record verified solutions and the number of gauge-inequivalent minima found. We also record how fast new minima stop appearing as restarts accumulate.

The third stage turns numbers into theorems. For each family of solutions, we test whether the overlaps and phases match algebraic values, such as roots of unity, before attempting an exact construction.

We also intend to run the same machinery on the residual nonnegative-inverse-eigenvalue cases of Sharp results for NIEP and NMF, but only after one sanity check. Under the convention summarized in our file ($m$ entries equal to $-1$ with $m=K/2+1$), the trace of $QJQ^T$ would be $-2$. A doubly stochastic matrix has nonnegative trace, so those cases would be trivially infeasible. The precise definition of the open cases must be re-derived from the paper before any search is run.

Baselines

The do-nothing reference is plain random-restart Riemannian gradient descent on the unrestricted orthonormal-row parameterization. This is essentially the approach Sharp results for NIEP and NMF reports stalling. It gets the same total budget of gradient evaluations and the same polishing and verification step as our method.

The strongest exact competitor is Spectral Tetris in its DFT and prescribed-norm variants (Spectral tetris fusion frame constructions, Necessary and sufficient conditions to perform Spectral Tetris). Wherever it applies, it solves the instance instantly, so we only claim progress on instances outside its reach. We use it to check that our solver does not miss cases Spectral Tetris covers.

The strongest diversity-maintenance competitor is a divergence-guided swarm in the style of Divergence-Guided Particle Swarm Optimization, run over the same phase vector with its Gaussian repulsion. We tune its kernel width and repulsion coefficient with the same budget we spend tuning $\alpha$. The file reports DPSO gains of 2× to 8× over standard PSO on multimodal functions such as Ackley and Levy. There is no reported result on Lacuna for any optimizer on fusion-frame or frame-synthesis existence problems, so no external number on our task exists to beat.

Two ablations isolate the key ingredients. In the first, deflation operates on raw coordinates, as in linear-predictivity deflation (Discovering alternative solutions beyond the simplicity bias in recurrent neural networks), instead of on invariants. In the second, the constant-modulus parameterization is removed while invariant deflation is kept.

Beating the baselines means two outcomes at matched compute. On positive controls, a higher rate of verified solutions with residual below $10^{-12}$ after polishing. On open instances, strictly more gauge-inequivalent minima, or verified solutions where the baselines find none.

Why not just…?

Why not just run many more random restarts? This is the real threat for small $N$, where restarts may simply suffice. The concern is that restarts in raw coordinates spend most of their budget re-entering basins already visited, because each frame appears in many rotated and re-phased copies. The invariant-versus-coordinate ablation measures this directly as the fraction of restarts that return an already-seen invariant signature. If that fraction stays low and restarts match our success rate, we will report that deflation is unnecessary at these sizes.

Why not just use alternating projections between the spectrum constraint and the block-orthonormality constraint? Alternating projections is cheap and natural. However, it has no memory of previous failures, so like restarts it cannot build a census of distinct minima. We include it as an extra arm under the same budget. If it reaches the same verified solutions, the constant-modulus loss offers nothing beyond convenience, and we will say so.

Why not just apply an off-the-shelf diversity metaheuristic? Swarm methods with Euclidean repulsion measure distance in the wrong space here, since two coordinate-distant particles can be the same frame. The file also records that DPSO loses precision on unimodal Sphere. Our task needs exactly that precision, since only exact zeros of the loss count as solutions. The DPSO baseline tests this concern directly.

Why not just solve small cases exactly with computer algebra? For the very smallest instances this may well win, and we will use it as a cross-check. Polynomial systems in $NM$ complex unknowns grow quickly beyond that range, and our search can supply candidate algebraic solutions for computer algebra to confirm.

Proposed Experiments

The decisive checks are these. The solver must achieve a near-perfect verified success rate on Spectral Tetris–certified positive controls and zero false successes on negative controls; otherwise nothing else counts. On the low-redundancy sweep, invariant deflation should find more distinct minima per thousand runs than coordinate deflation and plain restarts. Its census of new minima should level off as restarts accumulate, and only then do we read persistent failure as a conjecture of infeasibility. The single result that would justify the project is at least one verified, exactly reconstructed fusion frame for a majorization-feasible, low-redundancy request that no Spectral Tetris variant builds. We report verified success rate, number of distinct invariant classes, gradient evaluations to first verified solution, and wall-clock time, all averaged over seeds.