Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry

Mason Faldet, Clayton Shonkwiler · 2025

Read Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry by Mason Faldet, Clayton Shonkwiler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22847.txt.

Introduction

Mason Faldet and Clayton Shonkwiler sample optimal signal frames by way of symplectic geometry in a 2025 paper. Unit-norm tight frames spread measurement energy evenly, shrugging off noise and lost data. Drawing such frames at random, fairly, is harder than it sounds.

The pair show the frame space is a tidy quotient of a larger space under symmetry. A spinning torus action on it splits the space into a simple convex base and uniform fibers. Their Eigenlift algorithm samples the base, lifts to a fiber, then spins at random. Low-dimensional trials confirm the draws behave as theory promises.

Catalog record

CREATORMason Faldet, Clayton Shonkwiler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22847

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry Mason Faldet, Clayton Shonkwiler Abstract Unit-norm tight frames in finite-dimensional Hilbert spaces (FUNTFs) are fundamental in signal processing, offering optimal robustness to noise and measurement loss. In this paper we introduce the Eigenlift algorithm for sampling random FUNTFs. Our approach exploits the symplectic geometry of the FUNTF space, which we characterize as a symplectic reduction of frame space by a symmetry group. We then define a Hamiltonian torus action on this reduced space whose momentum map induces a fiber bundle structure. The algorithm proceeds by sampling a point from the base space, which is a convex polytope, lifting it deterministically to a point on the corresponding fiber, then acting on this point by a random element of the torus to obtain a random FUNTF. We implement the method in Python and validate it in low-dimensional settings where it is computationally feasible to sample the base polytope via rejection sampling. 1 Introduction A frame in a Hilbert space \mathcal{H} is a sequence of vectors \{f_{i}\}_{i\in I}\subset\mathcal{H} such that for every v\in\mathcal{H} , \displaystyle a\|v\|^{2}\leq\sum_{i\in I}|\langle v,f_{i}\rangle|^{2}\leq b\|v\|^{2} for some 0<a\leq b called the frame bounds . When a=b the frame is called tight . A finite collection \{f_{i}\}_{i=1}^{N}\subset\mathbb{C}^{d} is a frame if and only if \operatorname{span}\{f_{1},\dots,f_{N}\}=\mathbb{C}^{d} ; that is, finite frames are equivalent to spanning sets. Our main focus is on finite tight frames in which each all of the frame vectors are unit vectors; that is, \|f_{i}\|=1 for all i=1,\dots,N . These are exactly the finite unit-norm tight frames (FUNTFs). FUNTFs have proved useful in a variety of contexts because they provide robust representations of signals with optimal resilience to noise and random erasures of measurements [ 10 , 19 , 24 ] . In this paper, we introduce the Eigenlift algorithm for sampling FUNTFs uniformly from a natural probability measure on the space of FUNTFs. This algorithm leverages the toric symplectic structure on the space of FUNTFs described in [ 29 ] . This structure involves a specific toric action on the frame space and a many-to-one map from the frame space to a convex polytope (the eigenstep polytope ) that is invariant under the torus action. Heuristically, the process consists of sampling a point from Lebesgue measure on the eigenstep polytope, identifying a frame in the fiber over that point, and applying a random element of the torus to the resulting frame. We have implemented our algorithm in Python and used this implementation to conduct small-scale experiments. A key challenge lies in efficiently sampling from the eigenstep polytope; in principle this can be done using a standard Markov chain, but in practice convergence seems to be quite slow in high dimensions. For our proof of concept, we sampled the eigenstep polytope by rejection sampling from a bounding box; unfortunately, the rejection probability goes rapidly to 1 as the dimension of the space of FUNTFs increases, so this approach is only practical in low dimensions. Outline of the paper Section 2 gives a summary of key definitions and results from frame theory and symplectic geometry that are used in this work. We then describe the symplectic structure on a suitable quotient of the space of finite unit-norm tight frames in Section 3 . In fact, this space is highly symmetric: an open, dense subset admits a Hamiltonian action of a half-dimensional torus, making this subset into a toric symplectic manifold. We describe this toric structure in Section 4 and then use it to define the Eigenlift algorithm in Algorithm 2 . Section 5 summarizes results from our low-dimensional experiments and the paper concludes with Section 6 , which includes some discussion and future directions. 2 Background on Frame Theory and Symplectic Geometry 2.1 Concepts From Frame Theory Let \mathcal{F}^{d,N} denote the set consisting of all frames of N vectors in \mathbb{C}^{d} . View \mathcal{F}^{d,N} as a subset of \mathbb{C}^{d\times N} by identifying a frame \{f_{i}\}_{i=1}^{N}\in\mathcal{F}^{d,N} with the d\times N matrix F:=\begin{bmatrix}f_{1}|&\cdots&|f_{N}\end{bmatrix} . The frame space \mathcal{F}^{d,N} is the complement of the vanishing locus of the real polynomial function \displaystyle\begin{bmatrix}f_{1}|&\cdots&|f_{N}\end{bmatrix}\mapsto\sum_{\begin{subarray}{c}\{i_{1},\dots,i_{d}\}\\ \subset\{1,\dots,N\}\end{subarray}}\left|\det\begin{bmatrix}f_{i_{1}}|&\cdots&|f_{i_{d}}\end{bmatrix}\right|^{2}, so \mathcal{F}^{d,N} is an open, dense set in \mathbb{C}^{d,N} . For any F\in\mathcal{F}^{d,N} , define three related operators: (i) The analysis operator \mathbb{C}^{d}\to\mathbb{C}^{N} defined by v\mapsto F^{*}v , or equivalently \displaystyle v\mapsto(\langle v,f_{1}\rangle,\dots,\langle v,f_{N}\rangle). (ii) The synthesis operator \mathbb{C}^{N}\to\mathbb{C}^{d} defined by w\mapsto Fw , or equivalently \displaystyle(w_{1},\dots,w_{N})\mapsto\sum_{i=1}^{N}w_{i}f_{i}. (iii) The frame operator \mathbb{C}^{d}\to\mathbb{C}^{d} is the composition of the analysis and synthesis operators; that is, it is the operator v\mapsto FF^{*}v , or equivalently v\mapsto\sum_{i=1}^{N}\langle v,f_{i}\rangle f_{i}. We can re-interpret tightness in terms of the frame operator: a frame F\in\mathcal{F}^{d,N} is tight if and only if FF^{*}=a\mathbb{I}_{d} for some a>0 ; if we want to emphasize the constant a , we will call the frame a -tight . If for every i\in\{1,\dots,N\} , \|f_{i}\|^{2}=r for some r>0 we say F is equal norm and if r=1 we call F unit norm . Lastly, we say F is full spark if any size d subset \{f_{i_{1}},\dots,f_{i_{d}}\} of F is a basis of \mathbb{C}^{d} . In this work, we restrict our focus to finite unit norm tight frames (FUNTFs). These frames are highly structured as we will see now. Let F=\{f_{i}\}_{i=1}^{N}\in\mathcal{F}^{d,N} be a FUNTF. By the cyclic invariance of trace we have \displaystyle N=\sum_{i=1}^{N}\|f_{i}\|^{2}=\operatorname{tr}F^{*}F=\operatorname{tr}FF^{*}=\sum_{i=1}^{d}\lambda_{i}, (1) where \{\lambda_{i}\}_{i=1}^{d} is the spectrum of the frame operator. But since F is tight, FF^{*}=a\mathbb{I}_{d} for some a>0 , so \lambda_{i}=a for each i=1,\dots,d . After substituting these equalities into ( 1 ) we see that \lambda_{i}=N/d . Hence, if F is a FUNTF, then F is N/d -tight and the eigenvalues of FF^{*} are (\frac{N}{d},\dots,\frac{N}{d}) . {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N,1}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N,2}}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N,d-2}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N,d-1}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N,d}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-1,1}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-1,2}}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-1,d-2}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-1,d-1}}}} {\lx@inpgf@ignorespaces{\mu_{N-1,d}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-2,1}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-2,2}}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-2,d-2}}}} {\lx@inpgf@ignorespaces{\mu_{N-2,d-1}}} {\lx@inpgf@ignorespaces{\mu_{N-2,d}}} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-d+2,1}}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-d+2,2}}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{N-d+2,d-2}}} {\lx@inpgf@ignorespaces{\mu_{N-d+2,d-1}}} {\lx@inpgf@ignorespaces{\mu_{N-d+2,d}}} {\lx@inpgf@ignorespaces{{\color[rgb]{0,0,1}\mu_{N-d+1,1}}}} {\lx@inpgf@ignorespaces{\mu_{N-d+1,2}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{N-d+1,d-2}}} {\lx@inpgf@ignorespaces{\mu_{N-d+1,d-1}}} {\lx@inpgf@ignorespaces{\mu_{N-d+1,d}}} {\lx@inpgf@ignorespaces{\mu_{N-d,1}}} {\lx@inpgf@ignorespaces{\mu_{N-d,2}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{N-d,d-2}}} {\lx@inpgf@ignorespaces{\mu_{N-d,d-1}}} {\lx@inpgf@ignorespaces{\mu_{N-d,d}}} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces{\mu_{d,1}}} {\lx@inpgf@ignorespaces{\mu_{d,2}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{d,d-2}}} {\lx@inpgf@ignorespaces{\mu_{d,d-1}}} {\lx@inpgf@ignorespaces{\mu_{d,d}}} {\lx@inpgf@ignorespaces{\mu_{d-1,1}}} {\lx@inpgf@ignorespaces{\mu_{d-1,2}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{d-1,d-2}}} {\lx@inpgf@ignorespaces{\mu_{d-1,d-1}}} {\lx@inpgf@ignorespaces 0} {\lx@inpgf@ignorespaces{\mu_{d-2,1}}} {\lx@inpgf@ignorespaces{\mu_{d-2,2}}} {\lx@inpgf@ignorespaces\cdots} {\lx@inpgf@ignorespaces{\mu_{d-2,d-2}}} {\lx@inpgf@ignorespaces 0} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\iddots} {\lx@inpgf@ignorespaces\iddots} {\lx@inpgf@ignorespaces\mu_{2,1}} {\lx@inpgf@ignorespaces\mu_{2,2}} {\lx@inpgf@ignorespaces 0} {\lx@inpgf@ignorespaces\mu_{1,1}} {\lx@inpgf@ignorespaces 0} {\lx@inpgf@ignorespaces 0} Figure 1: Eigensteps of a generic FUNTF which, by ( 2 ) and ( 3 ), are such that the columns, rows, and upward diagonals are nonincreasing. Moreover, the values in blue are N/d and the sum of the entries in the row corresponding to S_{k} is equal to k . The independent eigensteps are all those colored black, excluding the rightmost nonzero term in each row. The eigenvalues of the partial frame operators S_{k}:=f_{1}f_{1}^{*}+\cdots f_{k}f_{k}^{*} will also be of importance. By virtue of being a sum of rank 1 matrices, \operatorname{rank}S_{k}\leq\min\{k,d\} and S_{k} has at most \min\{k,d\} nonzero eigenvalues. For a fixed k=1,\dots,N , let \displaystyle\mu_{k,1}\geq\mu_{k,2}\geq\cdots\geq\mu_{k_{d}} (2) be the eigenvalues of S_{k} arranged in nonincreasing order. The values \mu_{kj} are called eigensteps [ 6 ] . Because S_{k} is a rank 1 perturbation of S_{k-1} i.e. S_{k}=S_{k-1}+f_{k}f_{k}^{*} , Weyl’s Inequality applies so that the eigensteps satisfy the interlacing inequalities \displaystyle\cdots\geq\mu_{k,j}\geq\mu_{k-1,j}\geq\mu_{k,j+1}\geq\mu_{k-1,j+1}\geq\cdots (3) for each k=2,\dots,N and j=1,\dots,\min\{k,d\} . In Fig. 1 the eigensteps are arranged into a table in which the rows, columns, and upward diagonals are nonincreasing as a consequence of ( 2

Read the complete text