REVIEW 2 major objections 6 minor 34 references
Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry
T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The Eigenlift algorithm samples uniformly random finite unit-norm tight frames from the natural quotient measure by inverting the momentum map of a toric symplectic structure, and its samples are full-spark with probability one.
desk verdict Sound toric-sampling algorithm for FUNTF classes, but the paper needs a clearer frame-sampling step and a real uniformity test before I'd trust the experiments. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the momentum map Φ of the Hamiltonian torus action on the quotient F^d,N_{N/d}(1)/(U(d)×G), with image the eigenstep polytope P_{d,N}. Its points are vectors of independent eigensteps, the free parameters in the interlacing eigenvalue tables of the partial frame operators. The map restricts to a U(1)^{d_T}-fiber bundle over the regular part of the polytope, with d_T=(d-1)(N-d-1); the paper uses Cahill et al.'s lift_to_fiber construction as a rough section and then applies the coarea and Duistermaat–Heckman identity to show that the pushforward of the symplectic measure is Lebesgue measure on the polytope times Haar measure on the torus. This identity is what makes Algorithm 1, and its FUNTF specialization Algorithm 2, exact rather than approximate.
What would settle it
Sample the eigenstep polytope finely, run Algorithm 2 for a small case such as d=3,N=5, and compare the empirical distribution of the momentum map's image to Lebesgue measure on P_{3,5}; any statistically significant discrepancy would falsify the uniformity claim. Equivalently, compute a torus-invariant statistic such as coherence for many samples and compare with direct numerical integration over the quotient.
Extended reading notes
Core claim
The central claim is that for any integers d,N with d+1<N, Algorithm 2 outputs a uniformly random point of F^d,N_{N/d}(1)/(U(d)×G) with respect to the Riemannian volume measure on the quotient, and the representative frame is full-spark almost surely. The proof rests on the quotient being a toric Kähler manifold of real dimension 2(d-1)(N-d-1), with a Hamiltonian torus action whose momentum map is the vector of independent eigensteps and whose moment polytope is the eigenstep polytope P_{d,N}. Because the generic fibers are tori and the symplectic volume equals the product of Lebesgue measure on the polytope and Haar measure on the torus, the three-step sampling scheme is exact. The full-spark statement is inherited from the previously known fact that full-spark frames have full measure among FUNTFs.
Load-bearing premise
The whole construction assumes the imported toric Kähler structure: that the quotient FUNTF space has a half-dimensional torus action whose momentum map is the independent eigensteps and whose generic fibers are tori; if those fibers or the isometry property failed on a positive-measure set, the coarea proof of uniformity would collapse.
Editorial extensions
If this is right
- Uniform random FUNTF equivalence classes are sampleable in principle for every d,N with d+1<N, without rejection sampling on the frame space itself.
- Because the sampled representative is full-spark with probability one, the method supplies generic frames for compressed sensing and erasure-robust coding experiments.
- The same toric sampling scheme should work for frames with any prescribed frame-operator spectrum and vector norms, since those quotients also have dense open toric subsets.
- The practical bottleneck becomes uniform sampling of the eigenstep polytope; any improved polytope sampler directly upgrades the FUNTF sampler.
Reading between the lines
- The paper leaves open whether a volume-preserving affine map from P_{d,N} to a box exists for d>2; if it does, rejection sampling would become efficient and the algorithm would scale like the d=2 case.
- The observed coherence cap min{1,(N-d)/d} suggests that for N<2d the coherence distribution of uniform FUNTFs may concentrate near the cap; this is testable once higher-dimensional samples are available.
- A natural follow-up is to test the MANOVA-spectrum conjecture for all FUNTFs using Eigenlift samples, which the paper raises as a plausible extension rather than a proved result.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes the Eigenlift algorithm for sampling random finite unit-norm tight frames (FUNTFs) from the natural symplectic/Riemannian volume on the quotient F^d,N_{N/d}(1)/(U(d)\times G). The construction uses the toric Kähler structure imported from [29]: the independent eigensteps are interpreted as components of a momentum map for a half-dimensional torus action, and the moment polytope is the eigenstep polytope. Algorithm 2 samples a point in the polytope, constructs a representative frame via the deterministic algorithm of Cahill et al., and applies a random torus element. Theorem 4.3 claims that this procedure samples the symplectic measure on a toric Kähler manifold, and Corollary 4.9 applies it to the FUNTF quotient, adding that the representative is full-spark with probability 1. The paper includes a Python proof-of-concept implementation, low-dimensional validation, and a new coherence bound for FUNTFs.
Significance. If the uniformity claim is correct, the paper supplies a new method for sampling the geometric measure on FUNTF equivalence classes, complementing earlier work that samples eigensteps from measures that are only absolutely continuous with respect to Lebesgue measure. The self-contained proof of Theorem 4.3 via the coarea formula is a useful contribution, the implementation is publicly available on GitHub, and Proposition 5.1 gives a clean, short proof of a natural coherence bound. The main mathematical ingredients are imported from the published paper [29], so the novelty lies in the sampling scheme rather than in the toric structure itself. The two concerns below affect the correctness of the central uniformity claim as currently written, but both appear addressable within the manuscript's scope.
major comments (2)
- [Section 4, proof of Theorem 4.3] The proof asserts that for every x in the regular set Φ(fM), the fiber M_x is diffeomorphic to U(1)^n via ψ_x(θ)=φ(θ,α(x)), and consequently that Dψ_x=Id. This requires the descended torus action to be free on each such fiber, or at least to have trivial generic stabilizer on a full-measure subset of the base. The paper establishes only that the action is effective and Hamiltonian (Theorem 4.8). If the generic stabilizer is a nontrivial finite group Γ, then ψ_x is a |Γ|-fold covering rather than a diffeomorphism, the determinant computation Dψ_x=Id is invalid, and the equality m_ω=μ in the displayed equation following (13) fails by a constant factor. Since Corollary 4.9 depends directly on this step, the proof is incomplete as written. Please either prove freeness of the action on q(U_I), or cite the precise statement in [29] (or a standard toric-geometry theorem) that establishes it.
- [Algorithm 2 and abstract] Algorithm 2 returns [F_new], i.e., a unitary equivalence class, not a FUNTF. The abstract, title, and the discussion in Section 4 promise sampling of FUNTFs, and the text notes that a random FUNTF can be obtained by further acting by a random element of U(d)×G, but this step is not part of Algorithm 2 or of Corollary 4.9. Because the torus action used in Algorithm 2 is only d_T-dimensional, the representative F_new is not uniformly distributed in the fiber over its class. Please modify Algorithm 2 to append the random U(d)×G action and state the corresponding uniformity theorem, or revise the title/abstract to say that the method samples unitary equivalence classes.
minor comments (6)
- [Section 1, paragraph 2] The phrase "each all of the frame vectors" should be "each of the frame vectors".
- [Definition 4.2] For Algorithm 1 to define a random variable, the rough section α should be required to be Borel measurable; the current definition only says there is no smoothness or continuity assumption.
- [Example 2.1] The phrase "eigensteop polytope" is a typo for "eigenstep polytope".
- [Section 3.2, definition of G] Identifying G with the subgroup of T consisting of matrices whose (N,N)-entry is 1 is a choice of section of the quotient T→T/Z(U(N)); it may be clearer to say that G is identified with this subgroup.
- [Proposition 5.1, proof] The proof begins by letting F be an element of the quotient F^d,N_{N/d}(1)/(U(d)×G), but the statement concerns F∈F^d,N_{N/d}(1); this is a notational slip.
- [Section 6 and Figure 4 caption] The measure is the Liouville measure (not "Louisville measure"), and the caption "FUNTF's" should be "FUNTFs".
Circularity Check
No significant circularity: Algorithm 2's uniformity claim is backed by Theorem 4.3, which is proved in the paper, and by the toric structure imported from [29]; the latter is published, parameter-free evidence rather than a restatement of the target result.
full rationale
The paper's central claim (Corollary 4.9) decomposes into: (i) Theorem 4.3, the toric-Kahler sampling theorem, which is proved in Section 4 of this paper by an explicit coarea computation (Eq. 12 and surrounding argument), and is explicitly acknowledged to be a Duistermaat-Heckman-type result rather than a new input; (ii) the toric structure of the FUNTF quotient {half-dimensional effective Hamiltonian torus action with eigenstep momentum map and torus fibers), which is imported from Needham-Shonkwiler [29], coauthored by the present second author. This import is load-bearing, but it is real evidence under the review rules: [29] is a peer-reviewed, parameter-free published theorem whose stated assumptions (d, N, FUNTF space) do not include the sampling claim, and the present paper independently constructs the circle actions and proves the momentum-map descent (Theorems 4.6-4.7). The equality of the quotient Riemannian volume with the symplectic measure is cited to the independent [23], and the rough section is supplied by the independent algorithm of Cahill et al. [6]. Algorithm 2 fits no parameters and 'predicts' no quantity equal to its input by construction: sampling Lebesgue measure on the eigenstep polytope and pushing forward by the torus action is connected to the symplectic measure by the proved Theorem 4.3, not by definition. The numerical experiments are external sanity checks (known coherence bounds [25], consistency with [30]), and Proposition 5.1 is a new, directly proved bound. The only residual concern is verification-level, not circular: freeness/local-freeness of the descended torus action on the regular stratum is inherited from [29] rather than re-derived here, but a finite generic stabilizer would at most rescale the sampled measure by a constant, which cancels under normalization, and the paper's openly stated practical limitations (rejection sampling scaling, Section 5) do not enter the mathematical claim.
Assumptions & free parameters
assumptions (5)
- domain assumption The quotient F^d,N_{N/d}(1)/(U(d)xG) is a toric Kahler manifold with momentum map the independent eigensteps and moment polytope the eigenstep polytope.
- domain assumption Every point of the eigenstep polytope is the eigenstep data of at least one FUNTF, and such a frame can be constructed constructively (the rough section).
- domain assumption Symplectic reduction of a Kahler manifold is Kahler, and the quotient Riemannian volume measure coincides with the symplectic measure.
- domain assumption The desired 'uniform' distribution on FUNTFs is the Riemannian quotient volume measure on the equivalence class space.
- standard math The Marsden-Weinstein-Meyer reduction theorems and the Atiyah-Guillemin-Sternberg convexity theorem apply to the spaces in question.
Cite this review
Pith. "Pith review of Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry." pith.science (2026). https://pith.science/paper/CBWKVIO2
@misc{pith2026250522847,
author = {Pith},
title = {Pith review of: Sampling Finite Unit Norm Tight Frames Using Symplectic Geometry},
year = {2026},
howpublished = {\url{https://pith.science/paper/CBWKVIO2}},
note = {Machine review of arXiv:2505.22847}
}
read the original 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.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[29]
Tom Needham and Clayton Shonkwiler. Toric symplectic geometry and full spark frames.Applied and Computational Harmonic Analysis, 61:254–287, 2022.doi:10.1016/j.acha.2022.07.004. 22
-
[1]
Hans C. Andersen and Persi Diaconis. Hit and run as a unifying device.Journal de la Société Française de Statistique & Revue de Statistique Appliquée, 148(4):5–28, 2007.Numdam:JSFS_2007__148_4_5_0
work page 2007
-
[2]
Michael Francis Atiyah. Convexity and commuting Hamiltonians.Bulletin of the London Mathematical Society, 14(1):1–15, 1982.doi:10.1112/blms/14.1.1
-
[3]
John J. Benedetto and Matthew Fickus. Finite normalized tight frames.Advances in Computational Mathematics, 18(2–4):357–385, 2003.doi:10.1023/A:1021323312367
-
[4]
Arnon Boneh andA. Golan. Constraints redundancyand feasible region boundedness by random feasible point generator (RGPG). InThird European Congress on Operations Research - EURO III, Amsterdam,
-
[5]
Claude J. P. Bélisle, H. Edwin Romeijn, and Robert L. Smith. Hit-and-run algorithms for generating multivariate distributions.Mathematics of Operations Research, 18(2):255–266, 1993.doi:10.1287/ moor.18.2.255
work page 1993
-
[6]
Jameson Cahill, Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, and Nate Strawn. Constructing finite frames of a given spectrum and set of lengths.Applied and Computational Harmonic Analysis, 35(1):52–73, 2013.doi:10.1016/j.acha.2012.08.001
-
[7]
Jason Cantarella, Bertrand Duplantier, Clayton Shonkwiler, and Erica Uehara. A fast direct sam- pling algorithm for equilateral closed polygons.Journal of Physics A: Mathematical and Theoretical, 49(27):275202, 2016.doi:10.1088/1751-8113/49/27/275202
Show all 34 references
-
[8]
Jason Cantarella, Henrik Schumacher, and Clayton Shonkwiler. A faster direct sampling algorithm for equilateral closed polygons and the probability of knotting.Journal of Physics A: Mathematical and Theoretical, 57(28):285205, 2024.doi:10.1088/1751-8121/ad54a8
2024 doi
-
[9]
The symplectic geometry of closed equilateral random walks in3-space.The Annals of Applied Probability, 26(1):549–596, 2016.doi:10.1214/15-AAP1100
Jason Cantarella and Clayton Shonkwiler. The symplectic geometry of closed equilateral random walks in3-space.The Annals of Applied Probability, 26(1):549–596, 2016.doi:10.1214/15-AAP1100
2016 doi
-
[10]
Casazza and Jelena Kovačević
Peter G. Casazza and Jelena Kovačević. Equal-norm tight frames with erasures.Advances in Compu- tational Mathematics, 18(2-4):387–430, 2003.doi:10.1023/A:1021349819855. 2We’re not sure to whom we ought to attribute this idea, but we first heard it from Dustin Mixon. 21
2003 doi
-
[11]
Casazza and Manuel T
Peter G. Casazza and Manuel T. Leon. Existence and construction of finite frames with a given frame operator.International Journal of Pure and Applied Mathematics, 63(2):149–157, 2010
2010
-
[12]
Number 1764 in Lecture Notes in Mathematics
Ana Cannas da Silva.Lectures on Symplectic Geometry. Number 1764 in Lecture Notes in Mathematics. Springer, Berlin, Germany, 2008.doi:10.1007/978-3-540-45330-7
2008 doi
-
[13]
Duistermaat and Gerrit J
Johannes J. Duistermaat and Gerrit J. Heckman. On the variation in the cohomology of the sym- plectic form of the reduced phase space.Inventiones Mathematicae, 69(2):259–268, 1982.doi: 10.1007/BF01399506
1982 doi
-
[14]
Manifold structure of spaces of spherical tight frames.International Journal of Pure and Applied Mathematics, 28(2):217–256, 2006
Ken Dykema and Nate Strawn. Manifold structure of spaces of spherical tight frames.International Journal of Pure and Applied Mathematics, 28(2):217–256, 2006
2006
-
[15]
Alan Edelman and Brian D. Sutton. The beta-Jacobi matrix model, the CS decomposition, and gen- eralized singular value problems.Foundations of Computational Mathematics, 8(2):259–285, 2008. doi:10.1007/s10208-006-0215-9
2008 doi
-
[16]
FUNTF-Sampler.https://github.com/masonfaldet/FUNTF-Sampler, 2025
Mason Faldet. FUNTF-Sampler.https://github.com/masonfaldet/FUNTF-Sampler, 2025
2025
-
[17]
Brendan Farrell. Limiting empirical singular value distribution of restrictions of discrete Fourier trans- form matrices.Journal of Fourier Analysis and Applications, 17(4):733–753, 2011.doi:10.1007/ s00041-010-9156-z
2011
-
[18]
Mixon, Miriam J
Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, and Nate Strawn. Constructing all self-adjoint matrices with prescribed spectrum and diagonal.Advances in Computational Mathematics, 39(3–4):585– 609, 2013.doi:10.1007/s10444-013-9298-z
2013 doi
-
[19]
Goyal, Jelena Kovačević, and Jonathan A
Vivek K. Goyal, Jelena Kovačević, and Jonathan A. Kelner. Quantized frame expansions with erasures. Applied and Computational Harmonic Analysis, 10(3):203–233, 2001.doi:10.1006/acha.2000.0340
2001
-
[20]
Convexity properties of the moment mapping.Inventiones Mathematicae, 67(3):491–513, 1982.doi:10.1007/BF01398933
Victor Guillemin and Shlomo Sternberg. Convexity properties of the moment mapping.Inventiones Mathematicae, 67(3):491–513, 1982.doi:10.1007/BF01398933
1982 doi
-
[21]
Polytopes of eigensteps of finite equal norm tight frames.Discrete & Computational Geometry, 56(3):727–742, 2016.doi:10.1007/s00454-016-9799-x
Tim Haga and Christoph Pegel. Polytopes of eigensteps of finite equal norm tight frames.Discrete & Computational Geometry, 56(3):727–742, 2016.doi:10.1007/s00454-016-9799-x
2016 doi
-
[22]
Marina Haikin, Ram Zamir, and Matan Gavish. Random subsets of structured deterministic frames have MANOVA spectra.Proceedings of the National Academy of Sciences of the United States of America, 114(26):E5024–E5033, 2017.doi:10.1073/pnas.1700203114
2017 doi
-
[23]
Hitchin, Anders Karlhede, Ulf Lindström, and Martin Roček
Nigel J. Hitchin, Anders Karlhede, Ulf Lindström, and Martin Roček. Hyperkähler metrics and super- symmetry.Communications in Mathematical Physics, 108(4):535–589, 1987.doi:10.1007/BF01214418
1987 doi
-
[24]
Holmes and Vern I
Roderick B. Holmes and Vern I. Paulsen. Optimal frames for erasures.Linear Algebra and its Applica- tions, 377:31–51, 2004.doi:10.1016/j.laa.2003.07.012
2004 doi
-
[25]
King, and Dustin G
John Jasper, Emily J. King, and Dustin G. Mixon. Game of Sloanes: Best known packings in complex projective space. In Yue M. Lu, Manos Papadakis, and Dimitri Van De Ville, editors,Wavelets and Sparsity XVIII, page 111381E, San Diego, United States, 2019. SPIE.doi:10.1117/12.2527956
2019 doi
-
[26]
Reduction of symplectic manifolds with symmetry.Reports on Mathematical Physics, 5(1):121–130, 1974.doi:10.1016/0034-4877(74)90021-4
Jerrold Marsden and Alan Weinstein. Reduction of symplectic manifolds with symmetry.Reports on Mathematical Physics, 5(1):121–130, 1974.doi:10.1016/0034-4877(74)90021-4
1974 doi
-
[27]
Oxford Graduate Texts in Mathematics
Dusa McDuff and Dietmar Salamon.Introduction to Symplectic Topology. Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, UK, 1995.doi:10.1093/oso/9780198794899.001. 0001
1995
-
[28]
Kenneth R. Meyer. Symmetries and integrals in mechanics. InDynamical Systems (Proc. Sympos., Univ. Bahia, Salvador, 1971), pages 259–272. Academic Press, New York, NY, USA, 1973
1971
-
[30]
The geometry of constrained random walks and an application to frame theory
Clayton Shonkwiler. The geometry of constrained random walks and an application to frame theory. In2018 IEEE Statistical Signal Processing Workshop (SSP), pages 343–347, Freiburg, Germany, 2018. IEEE.doi:10.1109/SSP.2018.8450816
2018
-
[31]
Stratified symplectic spaces and reduction.The Annals of Mathe- matics, Second Series, 134(2):375–422, 1991.doi:10.2307/2944350
Reyer Sjamaar and Eugene Lerman. Stratified symplectic spaces and reduction.The Annals of Mathe- matics, Second Series, 134(2):375–422, 1991.doi:10.2307/2944350
1991 doi
-
[32]
Robert L. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions.Operations Research, 32(6):1296–1308, 1984.JSTOR:170949
1984
-
[33]
Normalized tight frames in finite dimensions
Georg Zimmermann. Normalized tight frames in finite dimensions. In Werner Haussmann, Kurt Jetter, and Manfred Reimer, editors,Recent Progress in Multivariate Approximation, pages 249–252. Birkhäuser, Basel, 2001.doi:10.1007/978-3-0348-8272-9_20. 23
2001 doi
-
[1979]
European Congress on Operations Research
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.