                             Technical Report
                              26 October 2001

Signed frames and Hadamard products of Gram matrices

Irine Peng, Shayne Waldron

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand e–mail: irine@math.auckland.ac.nz e–mail: waldron@math.auckland.ac.nz (http:www.math.auckland.ac.nz/˜ waldron)

ABSTRACT

This paper concerns (redundant) representations in a Hilbert space H of the form

f = ∑_{j} c_{j}⟨f, ϕ_{j}⟩ϕ_{j}, ∀f ∈ H.

These are more general than those obtained from a tight frame, and we develop a general theory based on what are called signed frames. We are particularly interested in the cases where the scaling factors c_{j} are unique and the geometric interpretation of negative c_{j}. This is related to results about the invertibility of certain Hadamard products of Gram matrices which are of independent interest, e.g., we show for almost every v_{1}, …, v_{n} ∈ C^{d}

rank([⟨v_{i}, v_{j}⟩^{r}\overline{⟨v_{i}, v_{j}⟩}^{s}]) = min\{\binom{r + d − 1}{d − 1}\binom{s + d − 1}{d − 1}, n\}, r, s ≥ 0.

Applications include the construction of tight frames of bivariate Jacobi polynomials on a triangle which preserve symmetries, and numerical results and conjectures about the class of tight signed frames in a finite dimensional space.

Key Words: frames, wavelets, signed frames, Hadamard product, Gram matrix, generalised Hermitian forms, multivariate Jacobi polynomials, Lauricella functions

AMS (MOS) Subject Classifications: primary 05B20, 41A65, 42C15, secondary 11E39, 33C50, 33C65, 42C40

1. Introduction

Over the last decade there has been renewed interest in frame representations because of their applications in wavelet theory (cf [D92]). Often when an orthogonal wavelet with certain desired properties doesn’t exist it is possible to find a frame representation which has them. More recently the redundancy built into a frame representation has been seen to be desirable for computations (when a term in the representation is removed, not all the information associated with it is lost).

This paper concerns the question: when can a set of vectors {ϕ_{j}} in a Hilbert space H be scaled to obtain a tight frame {α_{j}ϕ_{j}}, and hence a representation of the form

f = ∑_{j} c_{j}⟨f, ϕ_{j}⟩ϕ_{j},  ∀f ∈ H,  (1.1)

where c_{j} = |α_{j}|^{2} > 0? When dim(H) < ∞ this is equivalent to writing the identity matrix as a linear combination of the orthogonal projections ϕ_{i}ϕ_{i}^{∗}. Such representations are of interest because they share many features of an orthogonal expansion (which may not be available). Our motivation was the construction of tight frames of multivariate Jacobi polynomials which share the symmetries of the weight (no such orthonormal bases exist).

It turns out that representations of the form (1.1) can exist with some c_{j} negative, and these correspond to what we call signed frames. We first develop the basic theory of signed frames and give examples. Next we consider Hadamard products of Gram matrices which occur in the scaling question. Here we give a number of results of independent interest, e.g., for almost every v_{1}, …, v_{n} ∈ C^{d}

rank([⟨v_{i}, v_{j}⟩^{r}\overline{⟨v_{i}, v_{j}⟩}^{s}]) = min\{\binom{r + d − 1}{d − 1}\binom{s + d − 1}{d − 1}, n\}, r, s ≥ 0.

We then give answers to the scaling question. For example, if H is d–dimensional, then almost every set of

n = \{ \begin{matrix}d(d + 1)/2, & H real; \\ d^{2}, & H complex \end{matrix}

vectors can be scaled to obtain a unique representation of the form (1.1). This includes a discussion on the particular choice of n and the geometric interpretation of negative c_{j}. We conclude with some applications including the construction of tight frames of bivariate Jacobi polynomials on a triangle (which preserve symmetries), and some numerical results and conjectures about the class of tight signed frames in a finite dimensional space.

2. Basic theory of signed frames

Throughout, H denotes a real or complex Hilbert space, with the linearity in the first variable of the inner product. The following motivates the definition of signed frames and provides the connection with Hadamard products of Gram matrices.

Lemma 2.1. Let ϕ_{j} ∈ H and c_{j} be scalars. Then there exists a representation

f = ∑_{j} c_{j} ⟨f, ϕ_{j}⟩ ϕ_{j},  ∀f ∈ H,  (2.2)

if and only if

∥f∥^{2} = ∑_{j} c_{j} |⟨f, ϕ_{j}⟩|^{2},  ∀f ∈ H.  (2.3)

If the choice of the c_{j} is unique for given ϕ_{j}, then c_{j} ∈ IR, ∀j. When H is finite–dimensional

dim(H) = ∑_{j} c_{j} ∥ϕ_{j}∥^{2}.  (2.4)

Proof: The forward implication is immediate, and the reverse follows from the polarisation identity. If the c_{j} are unique, then they can be solved for by applying Gauss elimination to (a suitable subsystem of)

∑_{j} |⟨f, ϕ_{j}⟩|^{2}c_{j} = ∥f∥^{2}, ∀f,

and so are real. Let (e_{i}) be an orthonormal basis and use Parseval’s formula to obtain

dim(H) = ∑_{i} ∥e_{i}∥^{2} = ∑_{i} ∑_{j} c_{j}|⟨e_{i}, ϕ_{j}⟩|^{2} = ∑_{j} c_{j} ∑_{i} |⟨e_{i}, ϕ_{j}⟩|^{2} = ∑_{j} c_{j}∥ϕ_{j}∥^{2}.

The condition (2.3) can be rewritten as

∥f∥^{2} = ∑_{j} σ_{j} |⟨f, ψ_{j}⟩|^{2}, σ_{j} := sign(c_{j}), ψ_{j} := \sqrt{|c_{j}|}ϕ_{j},

which motivates the following.

Definition. A family (ψ_{j}) in a Hilbert space is called a signed frame with signature σ = (σ_{j}), σ_{j} ∈ {−1, 1} if there exists A, B > 0 with

A ∥f∥^{2} ≤ ∑_{j} σ_{j} |⟨f, ψ_{j}⟩|^{2} ≤ B ∥f∥^{2},  ∀f ∈ H,  (2.5)

and (ψ_{j}) is a Bessel set, i.e., there exists C > 0 with

∑_{j} |⟨f, ψ_{j}⟩|^{2} ≤ C ∥f∥^{2},  ∀f ∈ H.  (2.6)

The signed frame operator S = S^{+} − S^{−} is the self adjoint operator defined by

Sf := ∑_{j} σ_{j} ⟨f, ψ_{j}⟩ ψ_{j},  ∀f ∈ H,  (2.7)

where its positive and negative parts are

S^{+}f := ∑_{σ_{j}=1}⟨f, ψ_{j}⟩ ψ_{j},  S^{−}f := ∑_{σ_{j}=−1}⟨f, ψ_{j}⟩ ψ_{j}.  (2.8)

Since {ψ_{j}} is a Bessel set, only countably many of the coefficients ⟨f, ψ_{j}⟩ are nonzero, and so the above sums (and those that follow) can be interpreted in the usual way.

When A = B we say (ψ_{j}) is a tight signed frame, and the polarisation identity implies the representation

f = \frac{1}{A} ∑_{j} σ_{j}⟨f, ψ_{j}⟩ ψ_{j}, ∀f ∈ H.

The theory of frames (cf [HW89]) can be extended to signed frames in the obvious way.

Theorem 2.9. The following are equivalent

(a) (ψ_{j}) is a signed frame with signature σ and frame bounds A, B and Bessel bound C.

(b) S^{+} and S^{−} are bounded linear operators with

AI ≤ S = S^{+} − S^{−} ≤ BI, S^{+} + S^{−} ≤ CI.

Proof: The implication (a) ⟹ (b) holds since

⟨If, f⟩ = ∥f∥^{2}, ⟨Sf, f⟩ = ∑_{j} σ_{j} |⟨f, ψ_{j}⟩|^{2}.

(b) ⟹ (a). Consider a sequence s_{n} of partial sums for Sf

∥s_{n} − s_{m}∥^{2} = sup_{∥g∥=1} |⟨s_{n} − s_{m}, g⟩|^{2} = sup_{∥g∥=1} |⟨ ∑_{j=m+1}^{n} σ_{j}⟨f, ψ_{j}⟩ψ_{j}, g⟩|^{2}

= sup_{∥g∥=1} | ∑_{j=m+1}^{n} σ_{j}⟨f, ψ_{j}⟩⟨ψ_{j}, g⟩|^{2}

≤ sup_{∥g∥=1}( ∑_{j=m+1}^{n} |⟨f, ψ_{j}⟩|^{2})( ∑_{j=m+1}^{n} |⟨ψ_{j}, g⟩|^{2}) (Cauchy–Schwartz)

≤ C ∑_{j=m+1}^{n} |⟨f, ψ_{j}⟩|^{2} → 0, n > m → ∞,

so Sf ∈ H is well defined, as are S^{+}f, S^{−}f. The bounds ∥S^{+}∥, ∥S^{−}∥ ≤ ∥S∥ ≤ C follow from a similar calculation, and the relations AI ≤ S ≤ BI, S^{+} + S^{−} ≤ CI from the signed frame definition.

In particular, we have the following signed frame representation.

Theorem 2.10 (Signed frame representation).

(a) S is invertible with

(1/B) I ≤ S^{−1} ≤ (1/A) I.

(b) Let ψ̃_{j} := S^{−1}ψ_{j}, then (ψ̃_{j}) is a signed frame with signature σ and frame bounds 1/A, 1/B and Bessel bound C/A^{2}, which we call the dual signed frame.

(c) Each f ∈ H can be represented

f = ∑_{j} σ_{j} ⟨f, ψ̃_{j}⟩ψ_{j} = ∑_{j} σ_{j} ⟨f, ψ_{j}⟩ψ̃_{j}.

Proof: Since AI ≤ S ≤ BI, ∥I − (1/B)S∥ ≤ (B − A)/B < 1, so S is invertible, and it is positive since

⟨S^{−1}f, f⟩ = ⟨S^{−1}f, S(S^{−1}f)⟩ ≥ A∥S^{−1}f∥^{2} ≥ 0, ∀f.

Multiplying AI ≤ S ≤ BI by S^{−1} (which commutes with I and S) gives (a). Since S^{−1} is self adjoint,

S̃f := ∑_{j} σ_{j}⟨f, ψ̃_{j}⟩ψ̃_{j} = S^{−1}(∑_{j} σ_{j}⟨S^{−1}f, ψ_{j}⟩ψ_{j}) = S^{−1}S(S^{−1}f) = S^{−1}f,

(S̃^{+} + S̃^{−})f := ∑_{j}⟨f, ψ̃_{j}⟩ψ̃_{j} = S^{−1}(∑_{j}⟨S^{−1}f, ψ_{j}⟩ψ_{j}) = S^{−1}(S^{+} + S^{−})S^{−1}f.

Hence

(1/B) I ≤ S̃ ≤ (1/A) I,  S̃^{+} + S̃^{−} ≤ (C/A^{2}) I,

and we obtain (b) from Theorem 2.9. Part (c) follows by expanding

f = S(S^{−1}f) = S^{−1}(Sf).

Corollary 2.11 (Equivalence). Let c_{j} ∈ IR and ϕ_{j} ∈ H. The following are equivalent a) There exists a representation

f = ∑_{j} c_{j} ⟨f, ϕ_{j}⟩ ϕ_{j}, ∀f ∈ H.

b) (\sqrt{|c_{j}|}ϕ_{j}) is a tight signed frame with signature σ = sign(c) and frame bound A = 1.

Proof: The forward implication follows since

∥f∥^{2} = ⟨∑_{j} c_{j}⟨f, ϕ_{j}⟩ϕ_{j}, f⟩ = ∑_{j} c_{j}|⟨f, ϕ_{j}⟩|^{2} = ∑_{j} σ_{j}|⟨f, \sqrt{|c_{j}|}ϕ_{j}⟩|^{2}.

Conversely, taking ψ_{j} := \sqrt{|c_{j}|}ϕ_{j} in Theorem 2.10 gives

f = ∑_{j} σ_{j}⟨f, \sqrt{|c_{j}|}ϕ_{j}⟩\sqrt{|c_{j}|}ϕ_{j} = ∑_{j} c_{j}⟨f, ϕ_{j}⟩ϕ_{j}.

Example 1 (Frames). A signed frame with zero negative part, i.e., σ_{j} = 1, ∀j, is frame in the usual sense (and conversely). Here B = C and the Bessel property (2.6) is a consequence of (2.5). Also the positive part of a signed frame {ϕ_{j}}_{σ_{j}=1} is a frame.

Example 2 (Nonharmonic Fourier signed frames). A system of complex exponentials e_{λ_{j}} : t ↦ e^{iλ_{j}t}, λ_{j} ∈ C is a signed frame with signature (σ_{j}) for L_{2}[−π, π] if

A ∫_{−π}^{π} |f|^{2} ≤ ∑_{j} σ_{j} |∫_{−π}^{π} fe_{λ_{j}} |^{2} ≤ B ∫_{−π}^{π} |f|^{2}, ∑_{j} |∫_{−π}^{π} fe_{λ_{j}} |^{2} ≤ C ∫_{−π}^{π} |f|^{2}, ∀f.

By the Paley–Weiner theorem, this is equivalent to

A ∫_{−∞}^{∞} |g|^{2} ≤ ∑_{j} σ_{j} |g(λ_{j})|^{2} ≤ B ∫_{−∞}^{∞} |g|^{2}, ∑_{j} |g(λ_{j})|^{2} ≤ C ∫_{−∞}^{∞} |g|^{2},

for every function g from the Paley–Weiner space (cf [Y80]).

Example 3. Take any three unit vectors in IR^{2} none of which are multiples of each other. These can be scaled in a unique way (up to ±1) to a tight signed frame, with the c_{j} for a vector given by

c_{j} = \frac{cos(β − α)}{sin α sin β},

where −π/2 ≤ α < β ≤ π/2 are the (acute) angles from the subspace spanned by this vector to those spanned by the other two. This is negative if α < 0, β > 0, β − α < π/2, i.e., the subspace generated by the vector lies in the region between the acute angle made by the other two.

Fig. 1. Tight signed frames of three vectors in IR^{2} with the signature indicated.

Example 4. Almost all choices of four unit vectors in C^{2} can be scaled uniquely to a tight signed frame. The possible signatures are ++++ (a frame), +++− and ++−−.

Examples 3 and 4 are special cases of the scaling results in Section 4.

Example 5 (Associated tight signed frame). Given a signed frame (ψ_{j}) with signature σ, let v_{j} := S^{−1/2}ψ_{j}. Then (v_{j}) is a tight signed frame with signature σ and frame bound 1, since

∑_{j} σ_{j}⟨f, v_{j}⟩v_{j} = S^{1/2} ∑_{j} σ_{j}⟨S^{−1/2}f, ψ_{j}⟩ψ̃_{j} = S^{1/2}S^{−1/2}f = f, ∀f ∈ H.

We call (v_{j}) the associated tight signed frame.

Example 6 (Possible signatures). Since the positive part of a signed frame is a frame, the signature σ of a signed frame in H = IR^{d}, C^{d} must have at least d positive entries, say σ_{1} = ⋯ = σ_{d} = 1. A tight signed frame can have any signature σ which satisfies this restriction. For example, let (ψ_{j})_{j=1}^{d} be any orthonormal basis, then

∑_{j=1}^{d} σ_{j}|⟨f, ψ_{j}⟩|^{2} = ∥f∥^{2},  | ∑_{j=d+1}^{n} σ_{j}|⟨f, ψ_{j}⟩|^{2}| ≤ ( ∑_{j=d+1}^{n} ∥ψ_{j}∥^{2})∥f∥^{2},

and so any choice of the remaining ψ_{j} with ∑_{j=d+1}^{n} ∥ψ_{j}∥^{2} < 1 will give a signed frame with signature σ. Now take the associated tight signed frame (which has the same signature).

3. Hadamard products of Gram matrices

It follows from (2.3) of Lemma 2.1 that a necessary condition for a scaling of {ϕ_{j}} to a tight signed frame to exist is that there are c_{j} satisfying

∑_{j} |⟨ϕ_{i}, ϕ_{j}⟩|^{2}c_{j} = ∥ϕ_{i}∥^{2},  ∀i.  (3.1)

Thus we are interested in the matrix

A := [|⟨ϕ_{i}, ϕ_{j}⟩|^{2}] = B ∘ \overline{B},  B := [⟨ϕ_{i}, ϕ_{j}⟩].  (3.2)

Here ∘ denotes the Hadamard (pointwise) product

(S ∘ T)_{ij} := s_{ij}t_{ij}.

The positive semidefinite matrix B := [⟨ϕ_{i}, ϕ_{j}⟩] is commonly known as the Gram matrix. We will use the Schur product theorem (cf [HJ91]).

Theorem (Schur product). If A and B are positive semidefinite, then so is A ∘ B. If, in addition, B is positive definite and A has no diagonal entry equal to zero, then A ∘ B is positive definite. In particular, if both A and B are positive definite, then so is A ∘ B.

We now provide general results about the rank of Hadamard products of the Gram matrix and its conjugate, of which we will use the particular case (3.2).

Suppose H is d–dimensional, and let

S_{r} := S_{r}(H) := the symmetric r–linear mappings on H,

Π_{r}^{0} := Π_{r}^{0}(H) := the homogeneous polynomials of degree r on H, H_{r} := H_{r}(H) := the restrictions of p ∈ Π_{r}^{0} to the sphere.

These spaces are isomorphic via the association of the symmetric r–linear map L with the homogeneous polynomial p : x ↦ L(x, …, x) and the restriction of p to the sphere {x ∈ H : ∥x∥ = 1}.

Lemma 3.3. Let u_{1}, …, u_{n} be unit vectors in a real or complex Hilbert space H of dimension d, where

n := \binom{d + r − 1}{r} = dim(S_{r}) = dim(Π_{r}^{0}) = dim(H_{r}), r ≥ 0.

Then the following are equivalent

(a) The points {u_{i}} are in general position on the sphere, by which we mean that no nonzero p ∈ H_{r} vanishes at all of them.

(b) There is a unique p ∈ H_{r} which interpolates arbitrary data at the points {u_{i}}.

(c) The n × n positive semidefinite matrix

A := [⟨u_{i}, u_{j}⟩^{r}]

is invertible.

(d) The polynomials {⟨·, u_{i}⟩^{r}} are a basis for Π_{r}^{0} and H_{r}.

(e) The functionals {f ↦ f(u_{i})} are a basis for the dual spaces of Π_{r}^{0} and H_{r}.

(f) The symmetric r–linear mappings on H have a basis given by

(x_{1}, x_{2}, …, x_{r}) ↦ ⟨x_{1}, u_{i}⟩⟨x_{2}, u_{i}⟩ ⋯ ⟨x_{r}, u_{i}⟩, i = 1, …, n.

(g) The functionals L ↦ L(u_{i}, …, u_{i}) are a basis for the dual space of S_{r}.

Proof: The positive semidefiniteness of A = B ∘ ⋯ ∘ B follows from the Schur product theorem. The equivalence of (a),(b),...,(e) is the standard conditions for unique linear interpolation from V = span{⟨·, u_{i}⟩} to the linear functionals f ↦ f(u_{i}). The implications (d) ⟺ (f), (e) ⟺ (g) follow from the isomorphism between S_{r} and Π_{r}^{0}.

Remark 1. Lemma 3.3 also holds with the inner product replaced by the dot product x · y := ∑_{i} x_{i}y_{i} on C^{n}, in which case (c) becomes A is an invertible symmetric matrix.

In the following we use Lebesgue measure on IR^{d} × ⋯ × IR^{d} and C^{d} × ⋯ × C^{d}, and remind the reader that the zero set of a nonzero polynomial has measure zero.

Theorem 3.4. For almost every v_{1}, …, v_{n} ∈ IR^{d} or C^{d}

rank([⟨v_{i}, v_{j}⟩^{r}]) = min\{n, \binom{d + r − 1}{r}\},  r ≥ 0.  (3.5)

Proof: This matrix is the r times Hadamard product of the Gram matrix

A := [⟨v_{i}, v_{j}⟩^{r}] = \underbrace{B ∘ B ∘ ⋯ ∘ B}_{r times},  B = V^{∗}V,  V := [v_{1}, …, v_{n}].

Since B = V^{∗}V is positive semidefinite, it follows from the Schur product theorem that A is also. Almost every choice of {v_{i}}_{i=1}^{n} is in general position, and so we may assume without loss of generality that they are chosen so.

First suppose n ≤ d. Then the {v_{i}} are linearly independent, so B is positive definite, and by the Schur product theorem A is positive definite, giving rank(A) = n, as asserted.

Hence it suffices to suppose n > d. Clearly, rank(A) ≤ n. Since B, V have the same kernel and rank(V) = d, the positive semidefinite matrix B has rank d, and so can be written

B = ∑_{i=1}^{d} u_{i}u_{i}^{∗},

where {u_{1}, …, u_{d}} is an orthogonal basis for the range of B. Now

A = B ∘ ⋯ ∘ B = ∑_{i_{1}=1}^{d} ∑_{i_{2}=1}^{d} ⋯ ∑_{i_{r}=1}^{d}(u_{i_{1}} ∘ u_{i_{2}} ∘ ⋯ ∘ u_{i_{r}})(u_{i_{1}} ∘ u_{i_{2}} ∘ ⋯ ∘ u_{i_{r}})^{∗},

a sum of at most \binom{d+r−1}{r} rank one matrices (∘ is commutative), giving

rank(A) ≤ \binom{d + r − 1}{r}.

Thus, by considering principal submatrices, it suffices to show rank(A) = n, where

n = \binom{d + r − 1}{r}.

Since det(A) is a polynomial in v_{1}, …, v_{n} it will be nonzero for almost every choice of {v_{i}} (giving the result) provided it is nonzero for some choice. Using equivalence with (c) in Lemma 3.3, it is easy to see such choices exist. For example, use (d) and the well known fact that the polynomials Π_{r}^{0} have a basis of ridge functions {⟨·, u_{i}⟩^{r}}.

Example 1. In three dimensions (d = 3), let r = 2. Then the matrix [⟨v_{i}, v_{j}⟩^{2}] is invertible for almost every choice of {v_{1}, …, v_{6}}. If we take v_{1}, v_{2}, v_{3} to be an orthonormal basis and

v_{4} := v_{1} + v_{2}, v_{5} := v_{2} + v_{3}, v_{6} := v_{4} + v_{5} = v_{1} + 2v_{2} + v_{3},

then these {v_{i}} are not in general position (since v_{6} = v_{4} + v_{5}), and satisfy

| det([⟨v_{i}, v_{j}⟩^{2}])| = 8.

Thus, the configurations of points {v_{i}} which give (3.5) are not simply those which are in general position. In Example 2 we give an example where this is the case.

We now give the counterparts to Lemma 3.3 and Theorem 3.4 for complex matrices

A = [⟨v_{i}, v_{j}⟩^{r}\overline{⟨v_{i}, v_{j}⟩}^{s}], r, s ≥ 0.

This requires a generalisation of Hermitian forms and the associated polynomial algebra. We can not find a reference to this in the literature, and so provide the basic results.

Suppose H is a complex Hilbert space. Then a map L : H^{r} × H^{s} → C is called a Hermitian (r, s)–form on H if it is symmetric r–linear in the first r variables and symmetric s–conjugate–linear in the last s variables. Let

S_{r,s} := S_{r,s}(H) := the real vector space of all Hermitian (r, s)–forms.

The map which associates L ∈ S_{r,s} with x ↦ L(x, …, x; x, …, x) is an isomorphism onto

Π_{r,s}^{0} := Π_{r,s}^{0}(H) := Π_{r}^{0} ⊗ \overline{Π_{s}^{0}}

(\overline{f}(z) := \overline{f(z)}), and the restriction of Π_{r,s}^{0} to the sphere is an isomorphism onto

H_{r,s} := H_{r,s}(H) := H_{r} ⊗ \overline{H_{s}}.

Lemma 3.6. Let u_{1}, …, u_{n} be unit vectors Hilbert space H of dimension d, where

n := \binom{r + d − 1}{d − 1}\binom{s + d − 1}{d − 1} = dim(S_{r,s}) = dim(Π_{r,s}^{0}) = dim(H_{r,s}), r, s ≥ 0.

Then the following are equivalent

(a) No nonzero p ∈ H_{r,s} vanishes at all the points {u_{i}}.

(b) There is a unique p ∈ H_{r,s} which interpolates arbitrary data at the points {u_{i}}.

(c) The n × n positive semidefinite matrix

A := [⟨u_{i}, u_{j}⟩^{r}⟨u_{j}, u_{i}⟩^{s}]

is invertible.

(d) The polynomials {⟨·, u_{i}⟩^{r}⟨u_{i}, ·⟩^{s}} are a basis for Π_{r,s}^{0} and H_{r,s}.

(e) The functionals {f ↦ f(u_{i})} are a basis for the dual spaces of Π_{r,s}^{0} and H_{r,s}.

(f) The Hermitian (r, s)–forms on H have a basis given by

(x_{1}, …, x_{r}, y_{1}, …, y_{s}) ↦ ⟨x_{1}, u_{i}⟩ ⋯ ⟨x_{r}, u_{i}⟩⟨u_{i}, y_{1}⟩ ⋯ ⟨u_{i}, y_{s}⟩, i = 1, …, n.

(g) The functionals L ↦ L(u_{i}, …, u_{i}) are a basis for the dual space of S_{r,s}.

Proof: The proof is similar to that of Lemma 3.6.

In particular, a Hermitian (1, 1)–form is a Hermitian form.

Theorem 3.7. For almost every v_{1}, …, v_{n} ∈ C^{d}

rank([⟨v_{i}, v_{j}⟩^{r}\overline{⟨v_{i}, v_{j}⟩}^{s}]) = min\{n, \binom{d + r − 1}{r}\binom{d + s − 1}{s}\},  r, s ≥ 0.  (3.8)

Proof: The proof is similar to that of Theorem 3.4, with

A := [⟨v_{i}, v_{j}⟩^{r}\overline{⟨v_{i}, v_{j}⟩}^{s}] = \underbrace{B ∘ B ∘ ⋯ ∘ B}_{r times} ∘ \underbrace{\overline{B} ∘ \overline{B} ∘ ⋯ ∘ \overline{B}}_{s times} .

This leads to

A = ∑_{i_{1}=1}^{d} ⋯ ∑_{i_{r}=1}^{d} ∑_{j_{1}=1}^{d} ⋯ ∑_{j_{s}=1}^{d}(u_{i_{1}} ∘ ⋯ ∘ u_{i_{r}} ∘ \overline{u_{j_{1}}} ∘ ⋯ ∘ \overline{u_{j_{s}}})(u_{i_{1}} ∘ ⋯ ∘ u_{i_{r}} ∘ \overline{u_{j_{1}}} ∘ ⋯ ∘ \overline{u_{j_{s}}})^{∗}

a sum of at most \binom{d+r−1}{r}\binom{d+s−1}{s} rank one matrices.

We now give an explicit formula for the determinant of [⟨v_{i}, v_{j}⟩^{r}] in two dimensions. Lemma 3.9. Let v_{1}, …, v_{n} be vectors in C^{2}, where n = r + 1. Then

det([⟨v_{i}, v_{j}⟩^{r}]) = C(r) ∏_{1≤i<j≤r+1} | det([v_{i}, v_{j}])|^{2},

det([(v_{i} · v_{j})^{r}]) = C(r) ∏_{1≤i<j≤r+1} det([v_{i}, v_{j}])^{2},

where

C(r) := ∏_{k=0}^{r} \binom{r}{k}.

Proof: Let A := [⟨v_{i}, v_{j}⟩^{r}] and v_{i} = (v_{i1}, v_{i2})^{T}. Then a binomial expansion gives

\begin{aligned}a_{ij} & = (\overline{v_{i1}}v_{j1} + \overline{v_{i2}}v_{j2})^{r} = ∑_{k=0}^{r} \binom{r}{k}(\overline{v_{i1}}v_{j1})^{k}(\overline{v_{i2}}v_{j2})^{r−k} \\ & = ∑_{k=0}^{r}(\overline{v_{i1}})^{k}(\overline{v_{i2}})^{r−k}\binom{r}{k}(v_{j1})^{k}(v_{j2})^{r−k}, \end{aligned}

i.e., A = B^{∗}DB, where

b_{ij} := (v_{j1})^{i−1}(v_{j2})^{r−i+1}, D = diag\{\binom{r}{i − 1}, i = 1, …, n\}.

Similarly, with M := [(v_{i} · v_{j})^{r}], we have M = B^{T} DB. Taking determinants gives

det(A) = C(r) | det(B)|^{2}, det(M) = C(r) det(B)^{2},

and so it remains only to compute the determinant of B.

By unitary invariance we may assume that v_{j2} ≠ 0, ∀j. Divide row j of B by (v_{j2})^{r} to obtain a Vandermonde matrix in the variable v_{j1}/v_{j2}, giving

det(B) = ∏_{1≤j≤n}(v_{j2})^{n−1} det ((\frac{v_{j1}}{v_{j2}} )^{i−1}) = ∏_{1≤i<j≤n}(v_{i1}v_{j2} − v_{i2}v_{j1}).

Example 2. When n = r + 1, d = 2 the conditions of Lemma 3.3 are equivalent to u_{1}, …, u_{n} being in general position, since by Lemma 3.9

[⟨v_{i}, v_{j}⟩^{r}] is invertible ⟺ det([⟨v_{i}, v_{j}⟩^{r}]) ≠ 0
⟺ det([v_{i}, v_{j}]) ≠ 0, 1 ≤ i < j ≤ n
⟺ v_{1}, …, v_{n} are in general position.

Example 1 shows that this is not the case for d ≥ 3.

4. Scaling to obtain a tight signed frame

In this section, we investigate when a set of unit vectors {u_{j}} in H can be scaled

ψ_{j} := α_{j}u_{j},

to obtain a tight signed frame {ψ_{j}}, and hence a representation of the form

f = ∑_{j} σ_{j}⟨f, ψ_{j}⟩ψ_{j} = ∑_{j} c_{j}⟨f, u_{j}⟩u_{j},  ∀f ∈ H.  (4.1)

where c_{j} := σ_{j}|α_{j}|^{2}. Clearly, multiplying the α_{j} by scalars of unit modulus gives a signed frame with the same signature and bounds. Thus we say there is a unique scaling if there is a unique signature σ and |α_{j}| giving a tight signed frame, i.e., there is a unique choice of the c_{j}. If a more than one scaling exists, then there are infinitely many since the set of such c = (c_{j}) is affine. Here we consider a finite set {u_{1}, …, u_{n}} where H has dimension d.

A necessary and sufficient condition for such a scaling to exist is that

∑_{j}⟨e_{i_{1}}, u_{j}⟩⟨u_{j}, e_{i_{2}}⟩c_{j} = ⟨e_{i_{1}}, e_{i_{2}}⟩, ∀i = (i_{1}, i_{2}) ∈ I,

where (e_{i})_{i=1}^{d} is an orthonormal basis of H, and I is the index set

I := {(i_{1}, i_{2}) : 1 ≤ i_{1} ≤ i_{2} ≤ d} (H real),
I := {(i_{1}, i_{2}) : 1 ≤ i_{1}, i_{2} ≤ d} (H complex).

This can be written in matrix form

Mc = b,  m_{ij} := ⟨e_{i_{1}}, u_{j}⟩⟨u_{j}, e_{i_{2}}⟩,  b_{i} := ⟨e_{i_{1}}, e_{i_{2}}⟩,  (4.2)

where M is an I × n matrix. The normal equation for this system

M^{∗}Mc = M^{∗}b  (4.3)

is the necessary condition (3.1) in matrix form, i.e.,

Ac = [1],  A := [|⟨u_{i}, u_{j}⟩|^{2}].  (4.4)

This follows from the calculations

\begin{aligned}(M^{∗}M)_{st} = ∑_{i∈I} \overline{m}_{is}m_{it} & = ∑_{i∈I} \overline{⟨e_{i_{1}}, u_{s}⟩⟨u_{s}, e_{i_{2}}⟩}⟨e_{i_{1}}, u_{t}⟩⟨u_{t}, e_{i_{2}}⟩ \\ & = (∑_{i_{1}}⟨u_{s}, e_{i_{1}}⟩⟨e_{i_{1}}, u_{t}⟩)(∑_{i_{2}} \overline{⟨u_{s}, e_{i_{2}}⟩} \overline{⟨e_{i_{2}}, u_{t}⟩}) = |⟨u_{s}, u_{t}⟩|^{2} \end{aligned}

(M^{∗}b)_{j} = ∑_{i∈I} \overline{m}_{ij}b_{i} = ∑_{i∈I}⟨u_{j}, e_{i_{1}}⟩⟨e_{i_{2}}, u_{j}⟩⟨, e_{i_{1}}, e_{i_{2}}⟩ = ∑_{i_{1}}⟨u_{j}, e_{i_{1}}⟩⟨e_{i_{1}}, u_{j}⟩ = ∥u_{j}∥^{2} = 1,

which show M^{∗}M = A, M^{∗}b = [1].

Morever, the c satisfying (4.4) give a representation which is closest to (4.1) in the following sense

Theorem 4.5 (Best approximation property). The c which minimise the Frobenius (matrix) norm

∥I − ∑_{j=1}^{n} c_{j}P_{j}∥_{F} ,  P_{j}f := ⟨f, u_{j}⟩u_{j}, If := f  (4.6)

are given by Ac = [1].

Proof: Recall the Frobenius inner product is given by

⟨A, B⟩_{F} := trace(AB^{∗}) = _{∑i,j}a_{ij}\overline{b}_{ij},

and so

⟨P_{j}, P_{i}⟩_{F} = trace(u_{j}u_{j}^{∗}u_{i}u_{i}^{∗}) = |⟨u_{i}, u_{j}⟩|^{2}, ⟨I, P_{i}⟩_{F} = trace(u_{i}u_{i}^{∗}) = ∥u_{i}∥^{2} = 1.

The minimum (least squares solution) of (4.6) occurs when (the error) I − ∑_{j} c_{j}P_{j} is orthogonal to all the P_{i}, i.e., ∀i

I −_{∑j}c_{j}P_{j} ⊥ P_{i} ⟺ _{∑j}c_{j}⟨P_{j}, P_{i}⟩_{F} = ⟨I, P_{i}⟩_{F} ⟺ _{∑j}c_{j}|⟨u_{i}, u_{j}⟩|^{2} = 1.

When |I| = n the matrix M is square and the necessary condition Ac = [1] becomes necessary and sufficient for a unique scaling to exist.

By a Hermitian form on H we mean a symmetric bilinear map when H is a real space and a (1, 1)–Hermitian form when H is complex, i.e., one satisfying the conditions of an Hermitian form. This is a real vector space of dimension

n = |I| = \{ \begin{matrix}\frac{1}{2}d(d + 1), & H real; \\ d^{2}, & H complex. \end{matrix}  (4.7)

Theorem 4.8 (Equivalence). Let u_{1}, …, u_{n} be unit vectors in a Hilbert space H of dimension d, where

n = \{ \begin{matrix}\frac{1}{2}d(d + 1), & H real; \\ d^{2}, & H complex. \end{matrix}

Then the following are equivalent

(a) The n × n positive semidefinite matrix

A := [|⟨u_{i}, u_{j}⟩|^{2}]

is invertible.

(b) The vectors u_{1}, …, u_{n} have a unique scaling which gives a tight signed frame, with the c of (4.1) given by

c = A^{−1}[1], A := [|⟨u_{i}, u_{j}⟩|^{2}].

(c) The Hermitian forms on H have a basis given by

(f, g) ↦ ⟨f, u_{i}⟩⟨u_{i}, g⟩, i = 1, …, n.

(d) The functionals L ↦ L(u_{i}, u_{i}) are a basis for the dual space of the Hermitian forms.

(e) The self adjoint operators on H have a basis given by the rank 1 orthogonal projections

P_{i} : f ↦ ⟨f, u_{i}⟩u_{i}, i = 1, …, n.

Proof: The equivalence of (a),(c),(d) is a special case of Lemmas 3.3 and 3.6. Since |I| = n, there is a unique scaling (given by Mc = b) iff the I × n matrix M is invertible iff A = M^{∗}M is invertible. Since c is then given by (4.4) this gives (a)⟺(b). The self adjoint (Hermitian) operator corresponding to (f, g) ↦ ⟨f, u_{i}⟩⟨u_{i}, g⟩ is P_{i}, which gives (c)⟺(e).

Corollary 4.9 (Scaling to a tight frame). Let H be a Hilbert space of dimension d, and

n = \{ \begin{matrix}\frac{1}{2}d(d + 1), & H real; \\ d^{2}, & H complex. \end{matrix}

Then almost every choice of unit vectors {u_{1}, …, u_{n}} in H has a unique scaling that gives a tight signed frame, with the constants c_{j} in (4.1) given by

c = A^{−1}[1],  A := [|⟨u_{i}, u_{j}⟩|^{2}].  (4.10)

The signature and the scaling factors of the tight signed frame so obtained satisfy

σ = sign(c),  |α_{j}|^{2} = |c_{j}|, ∀j,  ∑_{j} c_{j} = d.  (4.11)

Proof: Since det(A) is a nonzero polynomial in u_{1}, …, u_{n}, A is invertible for almost every choice of {u_{i}}. The equations (4.11) follow from c_{j} = σ_{j}|α_{j}|^{2} and (2.4).

For d = 1 the result is trivial. The examples of three vectors in IR^{2} (being in general position implies there is unique scaling) and four vectors in C^{2} have already been discussed.

Example 1. If n = d(d + 1)/2 unit vectors are in general position on the sphere in IR^{d}, i.e., no homogeneous quadratic vanishes at all of them, then there is a unique scaling of them giving a tight signed frame.

Example 2. With the exception of three vectors in IR^{2}, it is possible to construct a set of n vectors in general position for which more than one scaling to a tight signed frame exists. For example, take two different orthonormal bases (possible for d ≥ 2, H complex and d ≥ 3, H real) whose union is in general position and enlarge this to a set of n vectors in general position. Then this can be scaled to a tight frame (in two different ways) by taking the weights corresponding to one of the orthonormal bases to be 1, and all the others to be zero.

Example 3. It is also possible to construct a set of n vectors for which no scaling to a tight frame exists. This can be done by taking the vectors from a basis which is not orthogonal. Examples where the vectors are in general position also exist, e.g., in C^{2} take

( \begin{matrix}1 \\ 0 \end{matrix} ) , ( \begin{matrix}−i \\ e^{5i} \end{matrix} ) , ( \begin{matrix}e^{−5i} \\ \sqrt{3} + 2 \end{matrix} ) , ( \begin{matrix}e^{\frac{π}{3} i} \\ e^{5i} \end{matrix} ) ,  (4.12)

and in IR^{3} take

( \begin{matrix}1 \\ 1 \\ √ & \overline{2} \end{matrix} ) , ( \begin{matrix}1 \\ 2 \\ √ & \overline{5} \end{matrix} ) , ( \begin{matrix}1 \\ 3 \\ √ & \overline{10} \end{matrix} ) , ( \begin{matrix}1 \\ 4 \\ √ & \overline{17} \end{matrix} ) , ( \begin{matrix}1 \\ 5 \\ √ & \overline{26} \end{matrix} ) , ( \begin{matrix}1 \\ 6 \\ √ & \overline{37} \end{matrix} ) .  (4.13)

The considerations which led to these choices are discussed in the appendix.

Example 4. When H is real a specific choice of {u_{i}} for which A is invertible is

(e_{k} + e_{l})/\sqrt{2}, 1 ≤ k ≤ l ≤ d,

where {e_{i}}_{i=1}^{d} is an orthonormal basis. When H is complex add to this

(e_{k} + i e_{l})/\sqrt{2}, 1 ≤ k < l ≤ d,

to get such a choice.

5. Tight frames of Jacobi polynomials on a triangle

Here we construct tight frames of bivariate orthogonal Jacobi polynomials which share the symmetries of the weight. Though primarily interested in the bivariate case, we give the definitions for IR^{s} (which are no more complicated).

Let V be a set of s + 1 affinely independent points in IR^{s}, i.e., the vertices of an s–simplex which we denote by T. Let ξ = (ξ_{v})_{v∈V} be the corresponding barycentric coordinates, i.e., the unique linear polynomials that satisfy

∑_{v∈V} ξ_{v}(a) = 1,  ∑_{v∈V} ξ_{v}(a)v = a, ∀a ∈ IR^{s}.

For the (standard) triangle with vertices 0, e_{1} = (1, 0), e_{2} = (0, 1), these are

ξ_{0}(x, y) = 1 − x − y,  ξ_{e_{1}}(x, y) = x,  ξ_{e_{2}}(x, y) = y.

We will use standard multi–index notation for indices, so, for example,

ξ^{μ} := ∏_{v∈V} ξ_{v}^{μ_{v}}, μ ∈ IR^{V} , β! := ∏_{v∈V} β_{v}!, β ∈ ZZ_{+}^{V}.

For functions defined on T, we define an inner product by

⟨f, g⟩_{μ} := ∫_{T} fg ξ^{μ}, μ > −1.

The condition μ_{v} > −1 ensures the nonnegative weight ξ^{μ} is integrable over T.

Let S_{V} be the symmetry group of the simplex T with vertices V, i.e., the group of affine maps of T onto T. This is (isomorphic to) the symmetric group on V since an affine map IR^{s} → IR^{s} is uniquely determined by its action on s + 1 affinely independent points (such as V). Let S ∈ S_{V} act on functions f defined on T via S · f := f ∘ S^{−1}. Then S permutes the barycentric coordinates ξ_{v}, and so if all the μ_{v} are equal, the inner product has the symmetries

⟨S · f, S · g⟩_{μ} = ⟨f, g⟩_{μ}, S ∈ S_{V} .

We say that f ∈ Π_{k}(IR^{s}) is a Jacobi polynomial (of degree k) for the simplex T with weight ξ^{μ} (cf [DX01]) if it satisfies the orthogonality condition

⟨f, p⟩_{μ} = ∫_{T} fp ξ^{μ} = 0, ∀p ∈ Π_{k−1}(IR^{s}).

Such a polynomial of exact degree k is uniquely determined by its leading term f_{↑}, i.e., the homogeneous polynomial of degree k for which deg(f − f_{↑}) < k, via

f = f_{↑} − P_{Π_{k−1}}(f_{↑}), P_{Π_{k−1}} := orthogonal projection onto Π_{k−1}(IR^{s}).

Thus the space P_{k}^{μ} of Jacobi polynomials of (exact) degree k has

dim(P_{k}^{μ}) = dim(Π_{k}^{0}(IR^{s})) = \binom{k + s − 1}{s − 1}.

There exist explicit formulae for an orthogonal basis of this space (see [P57] and [KMT91]), and also biorthogonal systems (see [AK26] and [FL74]). But these do not share the symmetries of the weight, i.e., they are not invariant under the action of S_{V} when μ_{v} = μ_{0}, ∀v ∈ V. We now use the scaling results to construct a tight frame of Jacobi polynomials with these symmetries for the triangle.

Let p_{ξ^{β}}^{μ}, |β| = k denote the Jacobi polynomial of degree k with leading term

(ξ^{β})_{↑} = ∏_{v∈V} (ξ_{v}_{↑})^{β_{v}} ∈ Π_{k}^{0}.

Then {p_{ξ^{β}}^{μ} : |β| = k, β ∈ ZZ_{+}^{V}} ⊂ P_{k}^{μ} is an S_{V} –invariant family when μ_{v} = μ_{0}, ∀v. In the bivariate case (s = 2), this consists of (k + 1)(k + 2)/2 Jacobi polynomials of degree k, and so, by Theorem 4.8, they have a unique scaling that gives a tight signed frame provided the matrix

A := [|⟨p_{ξ^{α}}^{μ}, p_{ξ^{β}}^{μ}⟩_{μ}|^{2}]_{|α|,|β|=k}  (5.1)

is invertible. We first give examples where A was inverted and the scaling factors computed exactly, then give the general result suggested by these calculations. Normalise the p_{ξ^{β}}^{μ} so that the tight signed representation is

f = ∑_{{|β|=k \atop β∈Z Z^{V}_{+}}} c_{β}^{μ} \frac{⟨f, p_{ξ^{β}}^{μ}⟩_{μ}}{⟨p_{ξ^{β}}, p_{ξ^{β}}⟩_{μ}} p_{ξ^{β}}^{μ},  ∀f ∈ P_{k}^{μ},  (5.2)

where, by (2.4),

∑_{|β|=k} c_{β}^{μ} = k + 1.  (5.3)

Example 1 (Quadratics). For quadratic Jacobi polynomials the β have two forms: (1, 1, 0) and (2, 0, 0) (three of each). The c_{β} for selected μ = (μ_{0}, μ_{0}, μ_{0}) are (respectively)

c_{β}^{(0,0,0)} = \frac{7}{10}, \frac{3}{10},  c_{β}^{(1,1,1)} = \frac{9}{14}, \frac{5}{14},  c_{β}^{(2,2,2)} = \frac{34}{55}, \frac{21}{55},  c_{β}^{(3,3,3)} = \frac{55}{91}, \frac{36}{91}.

The Jacobi polynomials are

\begin{aligned}p_{ξ_{v}ξ_{w}}^{μ} & = ξ_{v}ξ_{w} − \frac{μ_{0} + 1}{3μ_{0} + 5}(ξ_{v} + ξ_{w}) + \frac{(μ_{0} + 1)^{2}}{(3μ_{0} + 4)(3μ_{0} + 5)}, v ≠ w, \\ p_{ξ_{v}^{2}}^{(0,0,0)} & = ξ_{v}^{2} − \frac{2(μ_{0} + 2)}{3μ_{0} + 5}ξ_{v} + \frac{(μ_{0} + 1)(μ_{0} + 2)}{(3μ_{0} + 4)(3μ_{0} + 5)}. \end{aligned}

Example 2 (Cubics). For cubics the β have three forms (1, 1, 1), (2, 1, 0) and (3, 0, 0) (1,6,3 of each). The c_{β} for selected μ = (μ_{0}, μ_{0}, μ_{0}) are (respectively)

c_{β}^{(0,0,0)} = \frac{24}{35}, \frac{52}{105}, \frac{4}{35}, c_{β}^{(1,1,1)} = \frac{3}{5}, \frac{29}{60}, \frac{1}{6},

c_{β}^{(2,2,2)} = \frac{80}{143}, \frac{68}{143}, \frac{28}{143}, c_{β}^{(3,3,3)} = \frac{15}{28}, \frac{79}{168}, \frac{3}{14}.

The Jacobi polynomials with constant weight (referred to as Legendre polynomials) are

\begin{aligned}p_{ξ_{u}ξ_{v}ξ_{w}}^{(0,0,0)} & = ξ_{u}ξ_{v}ξ_{w} − \frac{1}{7} (ξ_{u}ξ_{v} + ξ_{u}ξ_{w} + ξ_{v}ξ_{w}) + \frac{2}{105}, \\ p_{ξ_{v}^{2}ξ_{w}}^{(0,0,0)} & = ξ_{v}^{2}ξ_{w} − \frac{4}{7}ξ_{v}ξ_{w} − \frac{1}{7}ξ_{v}^{2} + \frac{2}{21}ξ_{v} + \frac{1}{21}ξ_{w} − \frac{1}{105}, \\ p_{ξ_{v}^{3}}^{(0,0,0)} & = ξ_{v}^{3} − \frac{9}{7}ξ_{v}^{2} + \frac{3}{7}ξ_{v} − \frac{1}{35}. \end{aligned}

We now give an explicit formula for a general c_{β}^{μ}. Define a multivariate hypergeometric function with arguments c a scalar, and β, γ, x vectors from IR^{V} by

F (c, β; γ; x) := ∑_{α∈ZZ_{+}^{V}}(c)_{|α|} \frac{(β)_{α}}{(γ)_{α}} \frac{x^{α}}{α!} , c ∈ IR, β, γ, x ∈ IR^{V} ,

where (β)_{α} is the multivariate shifted factorial

(β)_{α} := ∏_{v∈V} (β_{v})_{α_{v}}, (β_{v})_{α_{v}} := β_{v}(β_{v} + 1) ⋯ (β_{v} + α_{v} − 1).

This is the Lauricella function F_{A}. Note that F (c, −β; γ; ξ) is a polynomial of degree |β| in ξ, i.e.,

F (c, −β; γ; ξ) = ∑_{α≤β}(c)_{|α|} \frac{(−1)^{|α|}}{(γ)_{α}} \frac{β!}{(β − α)!} \frac{ξ^{α}}{α!} .

In [AK26] it was shown how in two variables this relates to the Jacobi polynomials with a restricted class of weights (no weight on the third barycentric coordinate), and the general result can be found in [FL74], namely

p_{ξ^{β}}^{μ} := \frac{(−1)^{|β|}(μ + 1)_{β}}{(|β| + |μ| + s)_{|β|}} q_{β}^{μ}, q_{β}^{μ} := F (|β| + |μ| + s, −β; μ + 1; ξ),

where μ + 1 := (μ_{v} + 1)_{v∈V}, |μ| := ∑_{v} μ_{v}.

In [WX01] a technical proof, which uses the orthogonal basis of Proriol [P57] and the Hahn polynomials, is given for the following bivariate result. Let Γ be the multivariate gamma function.

Theorem 5.4 (Tight frame of Jacobi polynomials on a triangle). On the triangle there is a unique scaling of {p_{ξ^{β}}^{μ} : |β| = k} that gives a tight signed frame for P_{k}^{μ}, with the scalars of (5.2) given by

c_{β}^{μ} = C_{k}^{μ} \frac{(μ + 1)_{β}}{β!} ⟨q_{β}^{μ}, q_{β}^{μ}⟩_{μ} > 0, |β| = k, β ∈ ZZ_{+}^{V},

where

C_{k}^{μ} := \frac{(|μ| + s + 1)_{2k}}{(k + |μ| + s)_{k}^{2}} \frac{Γ(|μ| + s + 1)}{Γ(μ + 1)}, s = 2,

and so this is a frame. The representation (5.2) can be written in the compact form

f = C_{k}^{μ} ∑_{|β|=k} \frac{(μ + 1)_{β}}{β!} ⟨f, q_{β}^{μ}⟩_{μ}q_{β}^{μ},  ∀f ∈ P_{k}^{μ}.  (5.5)

This was first observed, by chance, for the Legendre polynomials, i.e., when μ = (0), and (5.5) simplifies to

f = (2k + 2)\frac{((k + 1)!)^{2}}{(2k + 1)!} ∑_{|β|=k}⟨f, q_{β}^{0}⟩_{μ}q_{β}^{0}, ∀f ∈ P_{k}^{0}.

It was then extended whilst proving this case. In [WX01] it is also shown this result holds in all dimensions, where now (5.3) becomes

∑_{|β|=k} c_{β}^{μ} = dim(P_{k}^{μ}) = \binom{k + s − 1}{s − 1}.

In contrast to the bivariate result, our abstract scaling results do not suggest that this should be the case, and the result was proved without determining whether or not the matrix A of (5.1) is invertible.

Since {p_{ξ^{β}}}_{|β|=k} spans P_{k}^{μ} any scalar multiples of these functions forms a frame. The determination of the dual frame (which shares any symmetries) is still an open question in all but the above (most interesting) case.

6. Numerical results and conjectures

Consider the c of minimal norm giving the best approximation of Theorem 4.5, i.e., the least squares solution of the necessary condition (4.4) given by taking the (Moore–Penrose) pseudoinverse

c = c(u_{1}, …, u_{n}) := A^{+}[1],  A := [|⟨u_{i}, u_{j}⟩|^{2}].  (6.1)

This is a continuous function of u_{1}, …, u_{n} except at those points where the number of singular values of A changes (a set of measure zero). By Corollary 4.9, for n greater than or equal to the value (4.7), it has constant trace, i.e., ∑_{j} c_{j} = d for almost all choices of u_{1}, …, u_{n}. When a scaling to a tight signed frame exists this value of c gives the scaling factors with minimal ∑_{j} c_{j}^{2}. In particular, the scaling gives a frame if this is possible.

Thus, one could imagine finding a set of vectors u_{1}, …, u_{n} for which c(u_{1}, …, u_{n}) takes some specified (and allowable) value c^{∗} by taking an initial guess, computing c, then comparing it with the value obtained for some appropriately sized (random) perturbation of u_{1}, …, u_{n}, and keeping whichever set of vectors gives a value closest to c^{∗}. Using MATLAB we implemented this naive scheme. A number of interesting, now mostly proved, conjectures arose from the computations we undertook.

Fig. 1. Tight frames of vectors in IR^{2} which are equally spaced on the circle.

In H = IR^{2}, C^{2} the standard examples of a tight frame of n ≥ 2 vectors are

u_{j} := ( \begin{matrix}cos & \frac{2πj}{n} \\ sin & \frac{2πj}{n} \end{matrix} ) ,  u_{j} := \frac{1}{\sqrt{2}} ( \begin{matrix}w^{j} \\ \overline{w} & j \end{matrix} ) , w := e^{\frac{2πi}{n}} ,  j = 1, …, n.

For each of these the frame representation is of the form

x = \frac{2}{n} ∑_{j=1}^{n}⟨x, u_{j}⟩u_{j}, ∀x ∈ H.

Moreover, the vectors {u_{j}} in IR^{2} are equally spaced on the circle. Thus, it is natural to ask whether there exist frames with all the c_{i} equal in higher dimensions (other than the orthonormal bases), and whether they can be interpreted as points which are equally spaced on the sphere. The answers to these questions are yes and probably not.

Theorem 6.2 (Isometric tight frames). For each n ≥ d, there exist unit vectors u_{1}, …, u_{n} in general position in H = IR^{d}, C^{d} for which

x = \frac{d}{n} ∑_{i=1}^{n}⟨x, u_{i}⟩u_{i}, ∀x ∈ H,

i.e., there exists a tight frame consisting of n vectors of equal length.

This was supported by all our calculations. For example, in IR^{3} we obtained the following vectors U = [u_{1}, …, u_{n}], n = 4, 5, 6 which give a tight frame with equal c_{j} (to 4 sf).

U = ( \begin{matrix}−0.5742 & −0.4972 & −0.5799 & −0.6569 \\ −0.7015 & 0.3905 & 0.7496 & −0.3424 \\ −0.4221 & −0.7748 & 0.3191 & 0.6718 \end{matrix} ) , c_{i} = 0.7500

U = ( \begin{matrix}0.4771 & 0.4732 & 0.7153 & 0.6624 & 0.4955 \\ 0.6468 & −0.8745 & 0.5849 & −0.2450 & −0.2994 \\ 0.5950 & 0.1061 & −0.3825 & −0.7079 & 0.8153 \end{matrix} ) , c_{i} = 0.6000

U = ( \begin{matrix}0.5767 & 0.8003 & 0.6376 & −0.0293 & −0.5824 & 0.5294 \\ −0.5587 & 0.4885 & 0.1064 & 0.7417 & −0.5180 & −0.7871 \\ 0.5961 & −0.3475 & 0.7630 & 0.6701 & 0.6265 & −0.3165 \end{matrix} ) , c_{i} = 0.5000

Here is an example of 8 vectors in IR^{5} (c_{i} = 0.6250)

U = ( \begin{matrix}0.6257 & −0.3562 & −0.2393 & 0.4430 & 0.4650 & 0.0081 & 0.5352 & 0.5522 \\ 0.4655 & 0.1264 & −0.9514 & −0.4910 & −0.2354 & 0.2406 & 0.0612 & −0.3293 \\ −0.0407 & 0.7345 & 0.0480 & 0.4079 & −0.5840 & 0.5357 & 0.3845 & 0.3407 \\ 0.5238 & 0.0028 & 0.1466 & 0.5980 & −0.4689 & −0.5520 & 0.0466 & −0.6521 \\ −0.3403 & 0.5636 & −0.1175 & −0.1966 & 0.4092 & −0.5918 & 0.7482 & −0.2130 \end{matrix} )

In the complex case our naive algorithm converges only when the perturbation of u_{1}, …, u_{n} is taken to be real (here accuracy of 4 sf is typically obtained within 1000 iterations). As yet, we have been unable to explain why this is so in term of the underlying geometry of c(u_{1}, …, u_{n}). It is also observed that the c of iterates tend to approach c^{∗} (equal entries) from below in the cases where the trace of c is need not be d. Here are examples of isometric tight frames of 4 vectors in C^{2} and C^{3} obtained from our calculations

U = ( \begin{matrix}0.5587 + 0.0842i & −0.0848 + 0.0482i & −0.8080 + 0.1602i & −0.8242 − 0.5600i \\ 0.8225 − 0.0657i & −0.9889 + 0.1119i & 0.5467 − 0.1505i & 0.0832 + 0.0157i \end{matrix} )

U = ( \begin{matrix}−0.2995 + 0.2150i & 0.5050 − 0.1116i & 0.9105 + 0.0821i & −0.0492 + 0.3040i \\ 0.6115 + 0.3047i & −0.6113 + 0.3512i & 0.3641 + 0.0847i & −0.3063 + 0.3687i \\ 0.6101 − 0.1581i & 0.4626 − 0.1466i & 0.1271 − 0.0910i & −0.5943 − 0.5677i \end{matrix} )

A proof of Theorem 6.2, which is based on a simple inductive construction, is given in Reams and Waldron [RW01]. After proving this, it was pointed out to us by Matthew Fickus that this result was proved by Goyal, Vetterli and Thao in [GVT98] using discrete overcomplete Fourier series. Further discussion is given Fickus’s thesis [F01], which uses the term ‘normalized tight frame’ for what we call an ‘isometric tight frame’.

Now we consider the question of whether or not a (tight) frame with all c_{j} equal can be interpreted as a set of points which are equally spaced on the sphere. For three vectors in IR^{2} this is the case. Here the intersection of the three subspaces spanned by the {u_{i}} with the circle gives six equally spaced points. However, for four or more points there exist frames where this is not the case. For example, all frames of four vectors with equal c_{j} can be obtained by taking the union of two orthonormal bases. This gives equally spaced points only when the axes corresponding to the bases can be mapped onto each other by rotation through π/4.

Fig. 2. Isometric tight frames of four vectors in IR^{2}.

Fig. 3. Isometric tight frames of five, six and seven vectors in IR^{2}.

An even more extreme example is given by H = C. Here u_{1}, …, u_{n} can be any complex numbers of unit modulus. These can be placed anywhere on the circle, even taken to be all the same. Thus it appears that, except for a few special cases, a randomly generated isometric tight frame can not be interpreted as points which are equally spaced. Many nice examples, such as the roots of unity (in IR^{2}), the vertices of the five Platonic solids in IR^{3} and normalised Eutactic stars (see Coxeter [C63]) and the closely related spherical 2–designs (see [DGS77]) do exist, but the authors can think of no systematic way of finding them.

7. Appendix

Here we provide details on the constructions of Example 3 of Section 4, i.e., we find vectors u_{1}, …, u_{n} which are in general position for which (4.2) has no solution.

To find four vectors in general position in C^{2} for which no scaling to a tight frame exists it suffices to consider ones of the form

u_{1} = ( \begin{matrix}1 \\ 0 \end{matrix} ) , u_{2} = ( \begin{matrix}cos t_{2} \\ sin t_{2} e^{iθ_{2}} \end{matrix} ) , u_{3} = ( \begin{matrix}cos t_{3} \\ sin t_{3} e^{iθ_{3}} \end{matrix} ) , u_{4} = ( \begin{matrix}cos t_{4} \\ sin t_{4} e^{iθ_{4}} \end{matrix} ) ,

where t_{j}, θ_{j} ∈ IR. For these the determinant of the matrix M in (4.2) is scalar multiple of

sin(2t_{2}) sin(2t_{3}) sin(2t_{4}){tan t_{2} sin(θ_{3} − θ_{4}) + tan t_{3} sin(θ_{4} − θ_{2}) + tan t_{4} sin(θ_{2} − θ_{3})},

provided cos t_{j} ≠ 0. It is easy to choose t_{j}, θ_{j} so that the second factor above is zero, and so there is not a unique scaling to a tight signed frame. Moreover, a choice can be made so that there is no solution to Mc = b (hence no scaling), and the {u_{j}} are in general position. One such choice is t_{2} = π/4, t_{3} = tan^{−1}(\sqrt{3}+2), t_{4} = 5π/4, θ_{3} = 5, θ_{2} = π/2+5, θ_{4} = 5 − π/3, which gives (4.12) up to a scalar factor.

The second example (4.13) is a special case of the following.

Proposition 7.1. There exist n := d(d + 1)/2 vectors in general position in IR^{d}, d ≥ 3 for which no scaling to a tight signed frame exists.

Proof: Let V = [u_{1}, …, u_{n}] ∈ IR^{d×n} and {e_{i}} be the standard basis vectors in IR^{d}. With I := {(i_{1}, i_{2}) : 1 ≤ i_{1} ≤ i_{2} ≤ d}, the condition (4.2) becomes

Mc = b,  m_{ij} := ⟨e_{i_{1}}, u_{j}⟩⟨u_{j}, e_{i_{2}}⟩ = v_{i_{1}j}v_{i_{2}j},  b_{i} := ⟨e_{i_{1}}, e_{i_{2}}⟩.

The system Mc = b (which gives the scalings to a tight signed frame) has no solution, i.e., b ∉ ran(M) = ker(M^{∗})^{⊥}, if we can find a vector a ∈ IR^{I} with M^{∗}a = 0 and ⟨a, b⟩ ≠ 0. Let

a_{i} := \{ \begin{matrix}1, & i ∈ \{(1, 1), (2, 2)\}; \\ −1, & i = (3, 3); \\ 0, & otherwise. \end{matrix}

Then ⟨a, b⟩ = 1 ≠ 0, and the condition M^{∗}a = 0 is

v_{1j}^{2} + v_{2j}^{2} = v_{3j}^{2},  j = 1, …, n.  (7.2)

Thus it suffices to find a V ∈ IR^{d×n} whose first three rows satisfy (7.2), and whose columns are in general position. Let

v_{ij} := \{ \begin{matrix}j^{i−1}, & i ≠ 3; \\ \sqrt{j^{2} + 1}, & i = 3. \end{matrix}

Then this satisfies (7.2), and it columns are in general position since any d × d submatrix is a Vandermonde matrix (for distinct integer points) with the third row modified in such a way that it can not be written as a linear combination of the others.

Acknowledgement

The authors would like to thank Brad Baxter for emphasizing the connection between the invertibility of Hadamard products of Gram matrices and multivariate polynomial interpolation. The referee provided helpful comments including the nice proof for det(B) in the proof of Lemma 3.9.

References

[AK26] P. Appell and J. Kampé de Fériet, “Fonctions Hypergéométriqes et Hypersphériques”,

Gauthier–Villars, Paris, 1966.

[C63] H. S. M. Coxeter, “Regular polytopes”, Macmillan, New York, 1963.

[D92] I. Daubechies, “Ten Lectures on Wavelets”, CBMS Conf. Series in Appl. Math., vol. 61, SIAM, Philadelphia, 1992.

[DGS77] P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geom. Dedicata 6(3) (1977), 363–388.

[DS52] R. J. Duffin and A. C. Schaeffer, A Class of Nonharmonic Fourier Series, Trans. Amer. Math. Soc. 72(2) (1952), 341–366.

[DX01] C. F. Dunkl and Y. Xu, “Orthogonal polynomials of several variables”, Cambridge University Press, Cambridge, 2001.

[FL74] E. D. Fackerell and R. A. Littler, Polynomials biorthogonal to Appell’s polynomials, Bull. Austral. Math. Soc. 11 (1974), 181–195.

[F01] M. Fickus, “Finite normalised tight frames and spherical equidistribution”, disserta-

tion, University of Maryland, 2001.

[GVT98] V. K. Goyal, M. Vetterli, and N. T. Thao, Quantized overcomplete expansions in R^{N}: analysis, synthesis, and algorithms, IEEE Trans. Inform. Theory 44(1) (1998), 16–31.

[HW89] C. E. Heil and D. F. Walnut, Continuous and discrete wavelet transforms, SIAM Review 31(4) (1989), 628–666.

[HJ91] R. A. Horn and C. R. Johnson, “Topics in matrix analysis”, Cambridge University

Press, Cambridge, 1991.

[KMT91] E. G. Kalnins, W. Miller, and M. V. Tratnik, Families of orthogonal and biorthogonal

polynomials on the N-sphere, SIAM J. Math. Anal. 22 (1991), 272–294.

[P57] J. Proriol, Sur une famille de polynomes à deux variables orthogonaux dans un trian-

gle, C. R. Acad. Sci. Paris 245 (1957), 2459–2461.

[RW01] R. Reams and S. Waldron, Isometric tight frames, Preprint, 2001.

[WX01] S. Waldron and Y. Xu, Tight frames of Jacobi polynomials on a simplex, Preprint,

2001.

[Y80] R. M. Young, “An introduction to nonharmonic Fourier series”, Academic Press, New York, 1980.