# Tight frame completions with prescribed norms.

AbstractLet H be a finite dimensional (real or complex) Hilbert space and let [{[a.sub.i]}.sup.[infinity].sub.i=1] be a non-increasing sequence of positive numbers. Given a finite sequence of vectors F = [{[f.sub.i]}.sup.p.sub.i=1] in H we find necessary and sufficient conditions for the existence of r [member of] N [union] {[infinity]} and a Bessel sequence G = [{[g.sub.i].sup.r.sub.i=1] in H such that F [union] G is a tight frame for H and [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] for every i. Moreover, in this case we compute the minimum r [member of] N [union] {[infinity]} with this property. We also describe algorithms that perform completions of a given set of vectors to tight frames.

Keywords and phrases: frame, tight frame completion, majorization.

1 Introduction

In recent years the study of frames in finite dimensional Hilbert spaces has been motivated by a large variety of applications, such as signal processing, multiple antenna coding, perfect reconstruction filter banks, and Sampling Theory.

Some particular frames, called tight frames, are of special interest since they allow simple reconstruction formulas. For practical purposes, it is often useful to obtain tight frames with some extra "structure," specifically, with the norms of its elements prescribed (controlled) in advance.

The existence of such customized tight frames is shown in [3] (also see [2]). The necessary and sufficient condition is that the norms must satisfy an inequality (called fundamental inequality). This can be extended for general customized frames and can also involve algorithmic constructions for such frames (see [1, 2, 4, 5], and [12]).

In [9] D. Feng, L. Wang, and Y. Wang considered the problem of computing tight completions of a given set of vectors. More explicitly, given a finite sequence F = [{[f.sub.i]}.sup.P.sub.i] of vectors in H, how many vectors must we add in order to obtain a tight frame, and how to find those vectors? Theorem 1.1 in [9] provides a complete answer to this question. But when the norms of the additional vectors are required to be one (with the initial set of given vectors of norm one) the authors obtained a lower bound for the number of unit norm vectors to add ([9],Theorem 1.2); but they showed that their lower bound is not sharp in some cases.

In this note we calculate the minimum number of vectors we must add to F to obtain a tight completion. Moreover, we do not require the vectors to be of norm one; we look for tight completions with sequences of vectors whose squared norms are prescribed by a non-increasing sequence of positive numbers denoted a = [{[a.sub.i]}.sub.i [member of] N].

It turns out that this problem may not have a positive solution for a given set of initial vectors and a fixed sequence of "prescribed norms." In Proposition 3.7 we characterize when it is possible to complete F with a Bessel sequence G = [{g.sub.i]}.sup.r.sub.i=1] such that F [union] G is a tight frame and [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] = [[for all]i. The minimum r with this property is then not difficult to calculate and is established in Proposition 3.8.

We end this note by considering two algorithms that produce tight frame completions of a given set of vectors. The first one computes such a completion with the optimal number of vectors that appears in Proposition 3.8, but it depends on the diagonalization of a matrix. The second algorithm avoids the diagonalization of matrices using Cholesky's decomposition, but adds more vectors to the completion.

2 Preliminaries on Frames and Majorization

Throughout the paper H will denote a finite dimensional (real or complex) Hilbert space with dim H = n [member of] N and L[(H).sup.+] will denote the cone of bounded positive semi-definite operators on H. Finally, by [M.sub.nxm](C) we denote the complex n x m rectangular matrices.

Given m [member of] N [union] {[infinity]}, a sequence F = {[f.sub.i].sup.m.sub.i=1] [subset] H is a frame for H if there exist numbers A, B > 0 such that, for every [f [member of] H,

A [[parallel]f[parallel].sup.2] [less than or equal to] [m.summation over (i=1) [[absolute value of <f, [f.sub.i]>].sup.2] [less than or equal to] B [[parallel]f[parallel].sup.2]. (1)

The optimal constants (see below) in (1) are called the frame bounds. If the frame bounds A, B coincide, the frame is called A-tight (or simply tight). Finally, tight frames with all their elements having the same norm are called equal norm tight frames.

The sequence F is Bessel if there exists B > 0 such that the upper bound condition in (1) is satisfied. Given a Bessel sequence F, we define its frame operator by

[S.sup.F] f = [m.summation over (i=1] <f, [f.sub.i]> [f.sub.i]. (2)

It is easy to see that [S.sup.F] is a positive semi-definite bounded operator on H. Moreover, F is a frame if and only if its frame operator [S.sup.F] is invertible. Indeed, the optimal frame bounds A, B in (1) are [[lambda].sub.min]([S.sup.F]) and [[lambda].sub.max]([S.sup.F], the minimum and maximum eigenvalues of [S.sup.F], respectively. In particular, a frame F is A-tight if and only if [S.sup.F] = AI. For an introduction to the theory of frames mid related topics see the books [6, 13].

Given a Bessel sequence F, there is a close relationship between the norms of its elements and the spectrum of [S.sup.F] that can be expressed in terms of majorization (see [1] for details). First, we introduce some definitions. We say that a sequence [{[a.sub.i]}.sup.m.sub.i=1] is summable if m [member of] N, or if m = [infinity] and [{[a.sub.i]}.sup.[infinity].sub.i=1] [member of] [l.sup.1](N).

Similarly, F [{[f.sub.i]}.sup.m.sub.i=1] is summable if [{[[parallel][f.sub.i][parallel].sup.2]}.sup.m.sub.i=1] is summable. It is clear that [S.sup.F] defined by (2) is bounded when F is summable.

Definition 2.1. Let a = [{[a.sub.]i}.sup.m.sub.i=1], b = [{[b.sub.i]}.sup.s.sub.i=1] be non-increasing summable sequences of non-negative numbers, with s, m [member of] N [union] {[infinity]}, such that t = min{s, m} < [infinity]. We say that b majorizes a, noted b > a, if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

If m = s [member of] N in Definition 2.1, then this notion coincides with the usual vector majorization in [R.sup.m] between vectors with non-negative entries which are arranged in non-increasing order (see [11]).

Remark 2.2. Let a, b be as in Definition 2.1, with b > a and m < s. Then [b.sub.j] = 0 for m + 1 [less than or equal to] j. Indeed, since b has non-negative entries

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The claim above follows from this last fact.

As we already mentioned, the squared norms of the elements of a frame and the eigenvalues of its frame operator must satisfy certain inequalities. Moreover, those inequalities are also sufficient for the existence of customized frames (see Theorem 2.3 below). When the frame is finite, those inequalities come from the Schur-Horn Theorem (see [1]). A different proof of this result is given in [4]. For infinite vectors (in a finite dimensional Hilbert space) a similar necessary and sufficient condition is required, under the assumption that the squared norms are a summable sequence (see [1]).

These results can be also stated for Bessel sequences:

Theorem 2.3. Let a = [{[a.sub.i]}.sup.m.sub.i=1] (m [member of] N [union] {[infinity]}) be a non-increasing sequence of positive numbers and let S [member of] [L(H).sup.+] with eigenvalues (counted with multiplicity and arranged in non-increasing order) [LAMBDA] = [{[[lambda].sub.j]}.sup.n.sub.j=1. Then the following statements are equivalent:

1. a < A (as defined in 2.1).

2. There exists a (summable) Bessel sequence G = [{[[g.sub.i]}.sup.m.sub.i=1] [subset] H such that [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] [[for all].sub.i] and [S.sup.G] = S.

Proof. If we assume that S > 0 then the case when m [member of] N is Theorem 4.6 in [1] or Theorem 2.1 in [4], while the case when m = [infinity] is Theorem 4.7 in [1]. If the spectrum of S has zeros (note that this is the case whenever m < n) we can reduce to the invertible case, restricting S to the orthogonal complement of ker S.

3 Completing F to a Tight Frame with Prescribed Norms

Let us fix some notation used throughout this section. Let F = [{f.sub.i]}.sup.p.sub.i=1] [subset or equal to] H be a finite sequence with frame operator [S.sup.F] whose eigenvalues (counted with multiplicity) are [[lambda].sub.1] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n], and let a = [{[a.sub.i]}.sub.i [member of] N] be a non-increasing sequence of positive real numbers. Finally, let [alpha] = tr([S.sup.F]).

Theorem 2.3 implies a simple relation between the squared norms of the vectors of a Bessel sequence G for which F [union] G is a tight frame, and the spectrum of [S.sup.F]. We state this in the following Theorem:

Theorem 3.1. Let G = [{[g.sub.i]).sup.m.sub.i=1] be a summable Bessel sequence in H and let c > 0. Then the following conditions are equivalent:

1. F [union] G is a c-tight frame.

2. [S.sup.G] = cI - [S.sup.F].

Therefore, there exists G such that [S.sup.F [union] G] = cI and [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i], = [for all]i, if and only if

[{[a.sub.i]}.sup.m.sub.i=1] < (c - [[lambda].sub.n], c - [[lambda].sub.n-1], ..., c - [[lambda].sub.1]. (4)

Proof. It is easy to see that [S.sup.F [union] G] = [S.sup.G] + [S.sup.F]. This shows that 1 [left and right arrow] 2. The equivalence between the existence of a sequence G verifying condition 2 and Eq. (4) follows from Theorem 2.3.

Definition 3.2. We say that F is (a, r)-completable if there exists r [member of] N [union] {infinity]} and a Bessel sequence G = [{[g.sub.i]}.sup.r.sub.i=1] [subset] H with [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] [for all]i, and such that F [union] G is a tight frame. We say that G = [{[g.sub.i]}.sup.r.sub.i=1] is an (a, r)-completion of F.

Remark 3.3. If G = [{[g.sub.i]}.sup.r.sub.i=1] is an (a, r)-completion of F then the frame bound c [member of] R for F [union] G is determined by the number r E N [union] {[infinity]} and the norms of the vectors of F. In fact tr([S.sup.F [union] G]) = nc, and simple computations show that

tr([S.sup.F [union] G]) = [p.summation over (i=1)] [[parallel][f.sub.i][parallel].sup.2] + [r.summation over (i=1)] [a.sub.i]

so we have that c = 1/n ([summation].sup.r.sub.i=1] [a.sub.i] + [alpha]).

As a consequence of Theorem 3.1 we have:

Corollary 3.4. Let r [member of] N [union] {[infinity]}. Then F is (a, r)-completable if and only if

i. [[lambda].sub.1] [less than or equal to] 1/n ([r.summation over {i=1)] [a.sub.i] + [alpha]) < [infinity]

ii. For t = min {n, r},

1/k [k.summation over (i=1)] ([a.sub.i] + [[lambda].sub.n-i+1]) [less than or equal to] 1/n ([r.summation over (i=1)] [a.sub.i] + [alpha]), 1 [less than or equal to] k [less than or equal to] t. (5)

In particular if r [member of] N is such that r [greater than or equal to] n and F is (a, r)-completable, then F is (a, k )-completable for every k [member of] N, k [greater than or equal to] r.

Proof. Assume that there exists r [member of] N and a finite sequence G = [{[g.sub.i].sup.r.sub.i=1] such that [S.sup.F [union] G] = [S.sup.F] + [S.sup.G] = cI and [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] for 1 [less than or equal to] i [less than or equal to] r. Then cI - [S.sup.F] = [S.sup.G] [greater than or equal to] 0; in particular we have c [greater than or equal to] [parallel]S[parallel] = [[lambda.sub.1]. On the other hand, we see that the eigenvalues of [S.sup.G] arranged in non-increasing order are c - [[lambda].sub.n] [greater than or equal to] ... greater than or equal to] c - [[lambda].sub.1] [greater than or equal to] 0, since the eigenvalues of [S.sup.F] are arranged in non-increasing order. By Theorem 2.3 we have

(c - [[lambda].sub.n], c - [[lambda].sub.n-1], ..., c - [[lambda].sub.1]) > ([a.sub.1], ..., [a.sub.r]. (6)

Then, by Definition 2.1 we see that 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]) [greater than or equal to] [[lambda].sub.1] and (5) hold, using that c = 1/n ([[summation].sup.r.sub.i=1 [a.sub.i] + [alpha]) by Remark 3.3.

Conversely assume that 1/n ([[summation].sup.r.sub.i=1 [a.sub.i] + [alpha]) [greater than or equal to [[lambda].sub.1] = [parallel][S.sup.F][parallel] and (5) hold for r [member of] N. Set c = 1/n ([[summation].sup.r.sub.i=1 [a.sub.i] + [alpha]) and note that the spectrum of the positive operator cI - [S.sup.F], (c - [[lambda].sub.n], c - [[lambda].sub.n-1], ..., c - [[lambda].sub.1]), majorizes (in the sense of Definition 2.1) [{[a.sub.i]}.sup.r.sub.i=1]. By Theorem 2.3 we conclude that there exists a finite Bessel sequence G = [{[g.sub.i].sup.r.sub.i=1] with [S.sup.G] = cI - [S.sup.F] and [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] for 1 [less than or equal to] i [less than or equal to] r and we are done.

Suppose now that G is (a, [infinity])-completable with an infinite Bessel sequence G. This implies that a must be summable. Indeed, tr([S.sup.F [union] G]) = [[summation].sup.[infinity].sub.i=1] [a.sub.i] + [alpha] = nc, where c is the tight frame constant. As in the case r < [infinity], [[lambda].sub.1] = [parallel][S.sup.F][parallel] [less than or equal] to c so item i. follows from this fact and Remark 3.3. By Theorems 3.1 and 2.3 a < (c - [[lambda].sub.n], c - [[lambda].sub.n-1], ..., c - [[lambda].sub.1]), so item ii. also holds in this case.

On the other hand, if i. and ii. hold for r = [infinity], then, as in the finite case, cI - [S.sup.F] is a positive semi-definite linear operator whose spectrum majorizes a so by Theorem 2.3, F is (a, [infinity])-completable.

Remark 3.5. From Corollary 3.4, if [[summation].sup.[infinity].sub.i=1] [a.sub.i] diverges, then every set of initial vectors F is (a, r)-completable for some r [member of] N. We shall consider this in section 4 where we have [a.sub.i] = 1 for i [member of] N.

By Remark 2.2 and Theorem 3.1, we see that an (a, r)-completion with r < n is possible only if the first n - r eigenvalues of [S.sup.F] are equal:

Corollary 3.6. F is (a, r)-completable with r < n if and only if, for 1 [less than or equal to] i [less than or equal to ] n - r and 1 [less than or equal to] k [less than or equal to] r,

[[lambda.sub.i] = 1/n ([r.summation over (j=1)] [a.sub.j] + [alpha]), and [[lambda].sub.1] [greater than or equal to] 1/k [k.summation over (j-1)]([a.sub.j] + [[lambda].sub.n-j+1]). (7)

In particular, F is not (a, k)-completable for any k < n other than r.

Both results can be summarized in the following Proposition, which shall be useful for computing the minimum number r such that F is (a, r)-completable.

First, we define inductively the following numbers: let [c.sub.0] = [[lambda].sub.1] and for 1 [less than or equal to] k [less than or equal to] n let

[c.sub.k] = max ([c.sub.k-1], 1/k [k.summation over (i=1)]([a.sub.i] + [[lambda.sub.n-i+1)). (8)

It is clear from definition that [[lambda].sub.1] [less than or equal to] [c.sub.1] [less than or equal to] ... [less than or equal to] [c.sub.n].

Proposition 3.7. Let r [member of] N [union] {[infinity]}. F is (a, r)-completable if and only if

[c.sub.r] = 1/n ([r.summation over (i=1)] [a.sub.i] + [alpha]) for r < n (9)

or

[c.sub.n] [less than or equal to] 1/n ([r.summation over (i=1)] [a.sub.i] + [alpha]) < [infinity] for r [greater than or equal to] n. (10)

Moreover, if [c.sub.r] = 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha] for some r < n, then [c.sub.r] = [[lambda].sub.1].

Proof. Assume that F is (a, r)-completable. If r < n, note that by (7) in Corollary 3.6 we have [[lambda].sub.1] = [c.sub.0] [less than or equal to] ... [less than or equal to] [c.sub.r] = [[lambda].sub.1] and [[lambda].sub.1] = 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]), so (9) holds. If r [greater than or equal to] n, then min{n, r} = n and Corollary 3.4 together with the definition of [c.sub.n] imply that

1/n ([r.summation over (i=1)] [a.sub.i] + [alpha]) [greater than or equal to] [c.sub.n]

So in this case (10) holds. Conversely, if we assume (10), then it is clear F is (a, r)-completable by Corollary 3.4. Assume now that for some r < n, [c.sub.r] = 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]. We show that F is (a, r)-completable; indeed, since [nc.sub.r] = [[summation].sup.r.sub.i=1] [a.sub.i] + [alpha], then

[rc.sub.r] + (n - r)[c.sub.r] - [n-r.summation over (i=1)] [[lambda].sub.i] = [r.summation over (i=1)] [a.sub.i] + [r.summation over (i=1)] [[lambda].sub.n-i+1].

So by definition of [c.sub.r] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But then

[[lambda].sub.j] = 1/n ([r.summation over (i=1)] [a.sub.i] + [alpha]) for 1 [less than or equal to] j [less than or equal to] n - r

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so F is (a, r)-completable by Corollary 3.6. The last claim of the proposition is clear from our previous computations.

We are now able to give a formula for the minimum r [member of] N such that 9v is (a, r)-completable, when such an r [member of] N exists.

Proposition 3.8. Let F be a (a, r)-completable for some r [member of] N [union] {[infinity]}. Let [ro.sub.0] [member of] N be the minimum such that F is (a, [r.sub.0])-completable. Then

Case 1 [r.sub.0] < n if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case 2 n [less than or equal to] [r.sub.0] < [infinity] if and only if [c.sub.k] [not equal to] 1/n ([[summation].sup.k.sub.i=1] [a.sub.i] + [alpha]) for every 1 [less than or equal to] k [less than or equal to] n-1 and [r.sub.0] [member of] N is the minimum such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case 3 [r.sub.0] [infinity] if and only if [c.sub.k] [not equal to] 1/n ([[summation].sup.k.sub.i=1] [a.sub.i] + [alpha]) for every 1 [less than or equal to] k [less than or equal to] n - 1 and [c.sub.n] = 1/n ([[summation].sup.[infinity].sub.i=1] [a.sub.i] + [alpha]).

Proof. It follows immediately from Proposition 3.7. The fact that r [greater than or equal to] n in case 2 is implied by [c.sub.n] 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]), since [a.sub.i] > 0 for every i.

The next example shows that it is possible to obtain a set of vectors F and a sequence a such that F is (a, r)-completable for only one r [member of] N.

Example 3.9. Let F = {[square root of [2e.sub.1], [square root of [2e.sub.2][, e.sub.3]} in [C.sup.3] where {[e.sub.i]} is the canonical orthonormal basis and let a = [{[(1/4).sup.i-1]}.sup.[infinity].sub.i=1]. Then, easy computations show that the eigenvalues of [S.sup.F] are [[lambda].sub.1] = 2, [[lambda].sub.2] = 2 and [[lambda]3] = 1, so [alpha] = tr [S.sup.F] = 5. By Corollary 3.6 F is (a, 1)-completable since [[lambda].sub.1] = 1/3 ([a.sub.1] + [alpha]) and [[lambda].sub.1] [greater than or equal to [a.sub.1] + [[lambda].sub.3]. Moreover, it is clear that if we add (a copy of) the vector [e.sub.3] to 9r we obtain a 2-tight frame of four vectors. Note that, also by Corollary 3.6, F is not (a, 2)-completable.

On the other hand, it easy to see that 1/3([[summation].sup.[infinity].sub.i=1] [a.sub.i] + [alpha] = 19/9 < 17/8 = [c.sub.3] so, by Proposition 3.7 F is not (a, r)-completable for any r [greater than or equal to] 3.

Remark 3.10. Is not difficult to show that, if F is (a, r)-completable with r < n, then there exists [r.sub.1] [member of] N [union] {[infinity]} with [r.sub.1] [greater than or equal to] n and such that F is (a, [r.sub.1])-completable if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4 Equal Norm Tight Frames

In this section we consider the particular ease when a = {[a.sub.i]}[i [member of] N is the constant sequence, [a.sub.i] = 1 for every i [member of] N. Note that in this case F is (a, r)-completable for some r [member of] N by Remark 3.5; so we shall compute the minimum natural number r of vectors with norm one we must add to Y in order to obtain a tight frame. We use the notation of the previous section for F = [{[f.sub.i].sup.p.sub.i=1], [S.sup.F], [[lambda].sub.1] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] and [alpha]. We also use the notation [x] for the minimum integer greater than or equal to x.

Remark 4.1. Under our present assumption that [a.sub.i] = 1 for every i [member of] N we have that

[c.sub.r] = max ([[lambda].sub.1], 1 + 1/4 [r.summation over (i=1)] [[lambda].sub.n-1+1]).

Indeed, if j [less than or equal to] k then 1/j [[summation.sup.j.sub.i=1] [[lambda].sub.n-1+1] [less than or equal to] 1/k [[summation].sup.k.sub.i=1] [[lambda].sub.n-1+1] since [[lambda.sub.1] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] [greater than or equal to 0.

This simpler formula for the coefficients [c.sub.j] provides the following characterization for the optimal number of elements for tight completions with norm one vectors.

Proposition 4.2. Let h := [[summation].sup.n.sub.i=2] [[lambda.sub.1] - [[lambda].sub.i] = n[[lambda].sub.1] and denote by [r.sub.0] the minimum number of norm one vectors we need to add to F in order to have a tight frame.

Case 1 Suppose that h < n. Then [r.sub.0] = h if h = 0 or if h [member of] N and 1 + 1/h [[summation].sup.h.sub.i=1] [[lambda].sub.n-1+1] [less than or equal to].sub.1] (in particular, [c.sub.h] = [[lambda].sub.1]. Otherwise, [r.sub.0] = n.

Case 2 If h [greater than or equal to] n, then [r.sub.0] = [h].

Proof. It is clear that if h = 0 then F is already a tight frame. Assume that 0 < h < n; then, since h = [n[[lambda].sub.1] - [alpha], we have that [c.sub.n] = 1 + [alpha]/n by Remark 4.1. If in addition h [member of] N and 1 + 1/h [[summation].sup.h.sub.i=1] [[lambda].sub.n-i+1] [less than or equal to] [[lambda].sub.1] so [c.sub.h] = 1/n (h + [alpha]) = [[lambda].sub.1], then [r.sub.0] = h by Proposition 3.8. Otherwise, [c.sub.k] [not equal to] 1/n (k + [alpha]) for every k < n. Indeed, if [c.sub.k] = 1/n(k + [alpha]) for some k < n, then by Proposition 3.7 [c.sub.k] = [[lambda].sub.1], so h = k and 1 + 1/h [[summation].sup.h.sub.i=1] [[lambda].sub.n-i+1] [less than or equal to] [[lambda].sub.1], which contradicts our assumption; since [c.sub.n] = 1 + [alpha]/n, [[nc.sub.n, - [alpha]] = n, then [r.sub.0] = n by Proposition 3.8.

Finally, h [greater than or equal to] n implies that [c.sub.k] [not equal to] 1/n(k + [alpha]) for every k < n and [c.sub.n] = [[lambda].sub.1] (then [c.sub.k] = [[lambda].sub.1] for all k [less than or equal to] n). Therefore, again by Proposition 3.8, [r.sub.0] = [n[[lambda].sub.1] - [alpha]] = [h].

Example 4.3. This example is taken from [9]. It is interesting because it shows the difference between the cases when we can complete F to a tight frame with r < n or r [greater than or equal to] n vectors. Let [f.sub.1] = (1,0) and [f.sub.2] = (cos [theta], sin [theta]) in [R.sup.2], and consider [a.sub.i] = 1 [for all]i. It easy to see that the eigenvalues of [S.sup.F]= are 1 [+ or -] cos [theta]; hence, h = [[lambda].sub.1] - [[lambda].sub.2] = 2 [absolute value of cos [theta]] ([[lambda.sub.1] [greater than or equal to] [[lambda].sub.2] are the eigenvalues of [S.sup.F]). Therefore, by Theorem 4.2 the minimum number [r.sub.0] of unit vectors we must add to obtain a tight frame is 2, unless [theta] [member of] {k[pi]/3, k = 1,2,4,5}, where [r.sub.0] = 1, or if [theta] [member of] {[pi]/2, 3[pi]/2}, where [r.sub.0] = 0 (the pair is orthogonal).

Note that when [r.sub.0] = 1 the tight frame obtained is the well-known "Mercedes Benz" (it is-up to rigid rotations, reflections, and negation of individual vectors--the only unit norm tight frame on [R.sup.2] with three elements [10]).

5 Algorithm Implementation

Once we have calculated the number of vectors we must add, the process of constructing the completion can be implemented by algorithms such as those proposed by Davies and Higham (see [7]) (when the vectors have norm one), or its generalized version for different norms, the one-sided generalized Bendel-Mickey algorithm (see [8]). Also, the method proposed in [9] using Householder transformations is another option.

We can briefly describe these algorithms as follows: Let X [member of] [M.sub.n x m](C), with the squared norms of its columns listed by the vector b, and suppose that a is a vector [S.sup.F] positive entries such that a [??] b; then there are (at most m - 1) plane rotations[{[U.sub.j]}.sup.k.sub.j] =1 (or Householder matrices, in the algorithm presented in [9]) such that [X.sub.1] = X[U.sub.1] x [U.sub.2] ... x [U.sub.k] has squared column norms listed by a. By construction, X [X.sup.*] = [X.sub.1][X.sup.*.sub.1].

Given a set of vectors F = [{[f.sub.i]}.sup.m.sub.i=1] in [C.sup.n] denote by T the matrix in [M.sub.n x m](C) with [f.sub.i] as columns. Then, [S.sup.F] = [TT.sup.*]. We shall also use the notation [C.sub.i](A) for the i-th column vector of a matrix A.

We present here two different algorithms for completing F (by adding columns to T). Algorithm i computes the minimum number r according to Proposition 3.8 (here we consider r [greater than or equal to] n for simplicity of the computations). Thus, we need to diagonalize [S.sup.F].

In detail, we construct a tight (a, r)-completion of F with prescribed norms in two steps.

Algorithm 1:

Step 1 Diagonalize [S.sup.F] = [TT.sup.*] = U [[LAMBDA]U.sup.*], where [LAMBDA] = diag([[lambda].sub.i])i. Then calculate the minimum number r (under the restriction [greater than or equal to] n) of columns to add to T. Let c = 1/n([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]) and form the matrix R [member of] [M.sub.n x r](C), R = [Z D] with a n x (r - n) block of zeros Z and D is a diagonal matrix with diag D = [([square root of c - [[lambda].sub.i]]).sub.i].

Step 2 Apply the one-sided Bendel-Mickey algorithm to R to obtain [R.sub.1] [member of] [M.sub.n x r](C), with the squared norms of columns given by the vector z = ([a.sub.1], [a.sub.2], ..., [a.sub.r]). Note that this is possible since the column squared norms of R majorize the vector z. This implies [R.sub.1][R.sup.*.sub.1] = [RR.sup.*] = [ZZ.sup.*] + ([C.sub.i]- [LAMBDA]) = cI - [LAMBDA]. Then, (U[R.sub.1])[(U[R.sub.1]).sup.*] = [C.sub.i] - [TT.sup.*].

Finally, [g.sub.i] = [C.sub.i](U[R.sub.1]) for 1 [less than or equal to] i [less than or equal to] r is the completion of F.

As we mentioned before, computations in Step 1 require us to diagonalize the matrix [TT.sup.*]. For large n the process of diagonalization requires a lot of storage and time of calculation.

The next result allows us to replace R in Step 1 with another rectangular matrix (with different number of columns) such that we can apply Step 2 as well. The difference is that we do not need to diagonalize [S.sup.F] in this case (nor multiply by the unitary U in the final step). Instead of it, we factorize cI - [S.sup.F] (for a convenient c) using Cholesky algorithm.

Proposition 5.1. Assume that a is a divergent sequence. Let d [member of] R be any upper bound for [parallel][S.sup.F][parallel] and let t = d + [a.sub.1]. If r [member of] N is such that

[r-1.summation over (i=1)] [a.sub.i] < t x n - tr([S.sup.F]-) [less than or equal to [r.summation over (i=1)] [a.sub.i], (11)

then there exists a sequence G = [{[g.sub.i]}.sup.r.sub.i=l] such that F U G is a tight frame and such that [[parallel][g.sub.i][parallel].sup.2] = [a.sub.i] for 1 < i [less than or equal to] r. This sequence can be constructed without diagonalizing [S.sup.F].

Proof. As usual, denote c = 1/n ([[summation].sup.r.sub.i=1] [a.sub.i] + [alpha]); by hypothesis c [greater than or equal to] t. Then, cI - [S.sup.F] is positive definite since its eigenvalues are: c - [[lambda].sub.n] [greater than or equal to] ... [greater than or equal to] c - [parallel][S.sup.F]:[parallel] > [a.sub.1].

Let [YY.sup.*] be the Cholesky factorization of cI - [S.sup.F]. Note that since the eigenvalues of [Y.sup.*]Y are the same as of [YY.sup.*], the smallest diagonal entry of [Y.sup.*]Y is [greater than or equal to] c - [parallel][S.sup.F][parallel] > [a.sub.1] (by majorization inequalities). In particular, if b [member of] [R.sup.r] is the vector listing the squared norm of the columns of Y (arranged in decreasing order), then b [??] ([a.sub.1], [a.sub.2], ..., [a.sub.r]).

Now we can apply Step 2 to the matrix R = [Z Y] where Z is a block of zeros of size n x (r - n) to obtain a completion of F.

We can describe the pseudo-code for Algorithm 2 in the following way.

Algorithm 2:

Step 1 Let d be an upper bound for [parallel][S.sup.F][parallel]; then compute r satisfying (11). For c = 1/n ([[summation].sup.r.sub.i=]1 [a.sub.i] + [alpha]), obtain the Cholesky's decomposition [RR.sup.*] of cI - [S.sup.F].

Redefine R = [ZR] where Z is a n x (r - n) block of zeros.

Step 2 Apply the one-sided Bendel-Mickey algorithm to R to get [R.sub.1] [M.sub.n x r](C) with the squared norms of columns given by the vector z = [a.sub.1], [a.sub.2], ..., [a.sub.r]).

Finally, [g.sub.i] = [C.sub.i]([R.sub.1]) for 1 [less than or equal to] i [less than or equal to] r is the completion of F.

5.1 Numerical Examples

Algorithms 1 and 2 were implemented using Matlab for the particular case of completions to a unit norm tight frame. In this case, for Algorithm 1, the number r [greater than or equal to] n of vectors to add is computed using Proposition 4.2.

Example 5.2. Given the following six-unit norm vectors in [R.sup.4], generated randomly:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Algorithm 1 completes it with the following tight completion with six-unit norm vectors:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and Algorithm 2 yields:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The frame operators for both completions are, respectively:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Remark 5.3. In this case, when the norms of the added vectors are one, the difference of the number of columns (vectors) added with each algorithm is exactly n. Indeed, by Proposition 4.2, Algorithm 1 produces r = [n[parallel][S.sup.F][parallel] - tr [S.sup.F]] columns, while Algorithm 2 produces r = [n([parallel][S.sup.F][parallel] + 1) - tr [S.sup.F]] by Proposition 5.1.

Still, the number obtained with Algorithm 2 is less than the bound obtained by the authors in [9] since in general:

n x [[parallel][S.sup.F][parallel] + 1] - p [greater than or equal to] [n x ([parallel][S.sup.F][parallel] + 1) -p].

Dedicated to the memory of Mischa Cotlar

ACKNOWLEDGEMENT

We would like to thank Professors Demetrio Stojanoff and Nelida Etchebest for useful suggestions regarding the material in this note. This work was partially supported by CONICET (PIP 5272) and UNLP (11 X472).

References

[1] J. Antezana, P. Massey, M. Ruiz and D. Stojanoff, The Schur-Horn theorem for operators and frames with prescribed norms and frame operator, Illinois Journal of Mathematics, 51(2), 537-560, 2007.

[2] P. G. Casazza, Custom building finite frames, Wavelets, Frames and Operator Theory, 61-86, Contemp. Math., 345, Amer. Math. Soc., Providence, RI, 2004.

[3] P. G. Casazza, J. Kovacevic, M. T. Leon and J. C. Tremain, Custom built flames, preprint, 2002.

[4] P. G. Casazza and M. T. Leon, Frames with a given frame operator, preprint.

[5] P. G. Casazza and M. T. Leon, Existence and construction of finite tight frames, J. Concr. Appl. Math., 4(3), 277-289, 2006.

[6] O. Christensen, An Introduction to Frames and Riesz Bases, Birkhauser, Boston, 2003.

[7] P. I. Davies and N. J. Higham, Numerically stable generation of correlation matrices and their factors, BIT, 40, 640-651, 2000.

[8] I. S. Dhillon, R. W. Heath Jr., M. A. Sustik, J. A. Tropp, Generalized finite algorithms for constructing Hermitian matrices with prescribed diagonal and spectrum, SIAM J. Matrix Anal. Appl., 27(1), 61-71, 2005.

[9] D. J. Feng, L. Wang and Y. Wang, Generation of finite tight frames by Householder transformations, Advances in Computational Mathematics, 24, 297-309, 2006.

[10] V. K Goyal, J. Kovacevic, and J.A. Kelner, Quantized frame expansions with erasures, Journal of Appl. and Comput. Harmonic Analysis, 10(3), 203-233, 2001.

[11] R. Horn and C. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985.

[12] K. Kornelson and D. Larson, Rank-one decomposition of operators and construction of frames, Wavelets, Frames and Operator Theory 203-214, Contemp. Math., 345, Amer. Math. Soc., Providence, RI, 2004.

[13] R. M. Young, An introduction to Nonharmonic Fourier Series (revised first edition), Academic Press, San Diego, 2001.

P. G. Massey

Dpto. de Matematica, Univ. Nac. de La Plata and IAM-CONICET, Calle 50 y 115

1900 La Plata, Argentina

massey@mate.unlp.edu.ar

M. A. Ruiz

Dpto. de Matematica, Univ. Nac. de La Plata and IAM-CONICET, Calle 50 y 115

1900 La Plata, Argentina

mruiz@mate.unlp.edu.ar

Printer friendly Cite/link Email Feedback | |

Author: | Massey, P.G.; Ruiz, M.A. |
---|---|

Publication: | Sampling Theory in Signal and Image Processing |

Article Type: | Technical report |

Geographic Code: | 3ARGE |

Date: | Jan 1, 2008 |

Words: | 6370 |

Previous Article: | An automated method for recovering piecewise smooth functions on spheres free from Gibbs oscillations. |

Next Article: | Hermite distributed approximating functionals as almost-ideal low-pass filters. |

Topics: |