Filetype PDF | Posted on 24 Jan 2023 | 2 years ago
Authentication
digital resources
156x Filetype PDF File size 0.29 MB Source: framerc.missouri.edu
Algebraic geometry and finite frames
Jameson Cahill and Nate Strawn
Abstract Interesting families of finite frames often admit characterizations in terms
of algebraic constraints, and thus it is not entirely surprising that powerful results
in finite frame theory can be obtained through utilizing tools from algebraic geom-
etry. In this chapter, our goal is to demonstrate the power of these techniques. First,
wedemonstrate that algebro-geometric ideas can be used to formalize the intuition
behind degrees of freedom within spaces of finite unit-norm tight frames (and more
general spaces), and that optimal frames can be characterized by useful algebraic
conditions. In particular, we construct locally well-defined real-analytic coordinate
systems on spaces of finite unit-norm tight frames, and we demonstrate that many
types of optimal Parseval frames are dense and that further optimality can be dis-
covered through embeddings that naturally arise in algebraic geometry.
¨
Key words: Algebraic Geometry, Elimination Theory, Plucker embedding, Finite
Frames
1 Introduction
Our goal in this chapter is to demonstrate that ideas from algebraic geometry can
be used to obtain striking results in finite frame theory. Traditionally, the frame
theory community has focused on tools from harmonic and functional analysis. By
contrast, algebro-geometric techniques have only been exploited in the past few
years because of the relatively recent interest in the theory of finite frames.
Jameson Cahill
University of Missouri, e-mail: jccbd@mail.missouri.edu
Nate Strawn
DukeUniversity, e-mail: nstrawn@math.duke.edu
1
2 Jameson Cahill and Nate Strawn
There are two central reasons why the frame theory community has begun to
develop an extensive theory of finite frames. First, there is a hope within the com-
munity that a deeper understanding of finite frames may help resolve long standing
problemsintheinfinitedimensionalframetheory(suchastheKadison-Singerprob-
lem [8, 25]). Second, computer implementations of frames are necessarily finite,
and we must have a theory of finite frames to demonstrate that these implementa-
tions are accurate and robust (one manifestation of this is in the Paulsen problem
[6]). It turns out that interesting families of finite frames can be identified with al-
gebraic varieties. That is, they are solutions to systems of algebraic equations, or
they live in equivalence classes of solutions to algebraic systems. For example, real
Parseval frames satisfy the algebraic system of equations arising from the entries of
ΦΦT=Id.Inwhatfollows,weshallapplyideasfromalgebraicgeometrytostudy
finite unit-norm tight frames and Parseval frames.
Finite unit-norm tight frames obey length constraints and a frame operator con-
straint. Maintaining the frame operator constraint is the most complex obstruction
to parameterizing these spaces. A rather fruitful perspective on this constraint is
obtained by considering the frame operator as a sum of dyadic products:
M T
S=∑φiφi .
i=1
Supposing that Λ ⊂ [M] contains the indices of a basis inside of the frame Φ, we
then have
φφT =S− φφT.
∑ i i ∑ i i
i∈Λ i∈[M]\Λ
Bycontinuity, we should be able to locally articulate the φi’s with indices in [M]\Λ
while ensuring that the left hand side of this equation remains a viable frame oper-
ator for the basis. As the free vectors move, the basis reacts elastically to maintain
the overall frame operator. Additionally, the basis contributes extra degrees of free-
dom. It turns out that this intuition can be formalized, and tools from elimination
theory can be used to explicitly compute the resulting coordinate systems on spaces
of finite unit-norm tight frames (more generally, frames with fixed vector lengths
and fixed frame operator). It should be noted that the chapter “Constructing finite
frames with a given spectrum” also contained in this volume has coordinate sys-
tems where the free parameters directly control a system of eigensteps. In contrast,
the coordinates derived in our chapter have free parameters that directly control the
spatial location of frame vectors. We provide a technical justification for these co-
ordinate systems by characterizing the tangent spaces (Theorem 3) on the space of
finite unit-norm tight frames (and more general frames), and then applying the real-
analytic inverse function theorem (Theorem 4). An extensive example is provided
to convey the central ideas behind these results.
Parseval frames which are equivalent up to an invertible transform can be iden-
tified with the Grassmannian variety, which allows us to define a concrete notion
of distance between these equivalence classes. Using this distance, we can demon-
strate that equivalence classes of generic frames (robust to M−N arbitrary erasures
Algebraic geometry and finite frames 3
¨
[22]) are dense in the Grassmannian variety. Moreover, the Plucker embedding al-
lows us to construct algebraic equations which characterize generic frames that are
also numerically maximally robust to erasures. Finally, we demonstrate that suffi-
cient redundancy implies that the frames that can be used to solve the phaseless
reconstruction problem form a dense subset.
1.1 Preliminaries
Weshall now discuss the necessary preliminary concepts and notation. The Zariski
topology is a fundamental idea in algebraic geometry. The zero sets of multivariate
polynomials form a basis for the closed sets of the Zariski topology on H n. Thus,
the closed sets are given by
( k )
n \ −1 k
C = C⊂H :C= p ({0})forsomepolynomials{p} . (1)
i i i=1
i=1
It is not difficult to deduce that this induces a topology [15]. An important prop-
erty of this topology is that the nontrivial open sets are dense in the Euclidean topol-
ogy.
Weshalloften use [a] to denote the a-set {1,...,a}, and [a,b] = {a,a+1,...,b].
For sets P ⊂ [M] and Q ⊂ [N] and any M by N matrix X, we let X denote the
Q
matrix obtained by deleting the columns with indices outside of Q, and we let X
P×Q
denote the matrix obtained by deleting entries with indices outside of P×Q. For
any submanifold M embedded in the space of M by N matrices, we set
d
T M = Y :Y = γ(t) for a smooth path γ in M with γ(0) = X .
X dt
t=0
2 Elimination Theory for Frame Constraints
Elimination theory consists of techniques for solving multivariate polynomial sys-
tems. Generally, one successively “eliminates” variables by combining equations.
Variables are eliminated until a univariate polynomial is obtained, and then those
solutions are used to ”backsolve” and acquire all of the solutions to the multivari-
ate system. Gaussian elimination is perhaps the most well-known application of
elimination-theoretic techniques. Given a consistent system of linear constraints,
Gaussian elimination can be carried out to produce a parameterization of the solu-
tion space. For higher-order polynomials systems, generalizing this kind of elimi-
nation can be quite tricky, but simplifies in a few notable cases. For example, square
roots allow us to construct locally well-defined coordinate systems for the space of
4 Jameson Cahill and Nate Strawn
solutions to a single spherical constraint:
N 2 s N 2
∑xi =1=⇒x1=± 1−∑x .
i
i=1 i=2
This example demonstrates that we can parameterize the top or bottom cap of a
hypersphere in terms of the variables x for i = 2,...,N. Note that these parameter-
N i
izations are both valid as long as ∑ x2 ≤1, and that they are also analytic inside
i=2 i
of this region.
The finite unit-norm tight frames of M vectors in RN are completely character-
ized by the algebraic constraints
T N 2 T M
φ φ = φ =1fori=1,...,N andΦΦ = Id ,
i i ∑ ji N N
j=1
and hence the space of finite unit-norm tight frames is an algebraic variety. More-
over, these constraints are all quadratic constraints, so the space of finite unit-norm
tight frames is also a quadratic variety. Computing solutions for a general quadratic
variety is NP-hard [10], but we shall soon see that spaces of finite unit-norm tight
frames often admit tractable local solutions.
Finite unit-normtightframesforR2 admitsimpleparameterizationsbecausethey
can be identified with closed planar chains (see [3]).
2 M
Proposition 1. For any frame Φ of M vectors in R , identify (φ ) with the se-
i i=1
N
quenceofcomplexvariables{z } with Re(z )=φ andIm(z )=φ .ThenΦ isa
i i=1 i 1i i 2i N
2 2
finite unit-norm tight frame if and only if |z | = 1 for i = 1,...,N and ∑ z =0.
i i=1 i
To induce a parameterization on finite unit-norm tight frames with M vectors in
R2, we may place M−2 links in a planar chain starting at the origin, and to close
the chain with two links of length one, there are only finitely many viable solutions.
This parameterization betrays the fact that the local parameterizations arise from
locally arbitrary perturbation of M−2 vectors. This intuition extends to finite unit-
norm tight frames of RN, but the reacting basis for N > 2 has nontrival degrees of
freedom.
More generally, for a list of squared vector lengths µ ∈ RM and a target frame
+
operator S (a symmetric, positive definite N by N matrix), we may extend this in-
tuition to the algebraic variety of frames with squared vector lengths indexed by µ
and with frame operator S. We shall call these frames the (µ,S)-frames, and we let
Fµ,S denote the space of all such frames. The following majorization condition (in-
troduced to the frame community in [7]) characterizes the µ and S such that Fµ,S is
nonempty, and we shall implicitly assume that µ and S satisfy this condition for the
remainder of this section.
Theorem1. Let µ ∈ RM and let S denote an N by N symmetric positive definite
+
operator. The space Fµ,S is not empty if and only if
no reviews yet
Please Login to review.
