Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Appl
...
Harmon
...
30 (2011) 175–187

Contents lists available at ScienceDirect

Applied and Computational Harmonic Analysis
www
...
com/locate/acha

Constructing tight fusion frames
Peter G
...
Mixon c , Yang Wang d , Zhengfang Zhou d
a

Department of Mathematics, University of Missouri, Columbia, MO 65211, USA
Department of Mathematics and Statistics, Air Force Institute of Technology, Wright-Patterson Air Force Base, OH 45433, USA
Program in Applied and Computational Mathematics, Princeton University, Princeton, NJ 08544, USA
d
Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA
b
c

a r t i c l e

i n f o

Article history:
Received 15 April 2009
Revised 15 February 2010
Accepted 26 May 2010
Available online 8 June 2010
Communicated by Thomas Strohmer
Keywords:
Tight
Fusion
Frames

a b s t r a c t
Tight fusion frames are an emerging concept of frame theory with applications in
distributed processing and communications
...
We completely resolve the question of existence in
the special case where the underlying space is finite-dimensional and the fusion frame’s
subspaces have equal dimension
...
The characterizing set of requirements is very mild,
and as such, these frames often exist
...

Published by Elsevier Inc
...
Introduction
A tight fusion frame (TFF) is a sequence of orthogonal projection operators that sum to a scalar multiple of the identity operator
...
TFFs are robust against additive noise and
erasures [2,5,8], and as such, are well-suited for emerging real-world applications in communications and distributed sensing [7,10,11]
...
To be precise, a sequence { P k }kK=1
of N × N orthogonal projection matrices of rank L is a ( K , L , N )-TFF if there exists A > 0 such that:

AI =

K


Pk
...
Characterizing the
existence of such frames has proven difficult; frame potential arguments [3,9] have shown that for any fixed α > 1 and L,
there exists an index N 0 = N 0 (α , L ) such that ( K , L , N )-TFFs will exist whenever N  N 0 and K  α N
...
To be precise,
our first main result is the following partial characterization:
Theorem 1
...
If L divides N, then ( K , L , N )-TFFs exist if and only if K 
further assume that 2L < N, then:

*

Corresponding author
...
Fickus@afit
...
Fickus)
...

doi:10
...
acha
...
05
...

L

If L does not divide N and we

176

P
...
Casazza et al
...
Comput
...
Anal
...


(ii) If K   NL  + 2, then ( K , L , N )-TFFs exist
...
Next, to fully characterize the existence of
equal-rank TFFs, we employ two distinct methods of taking orthogonal complements of a TFF
...
For each K , L , N ∈ N such that L < N, the existence of ( K , L , N )-TFFs can be completely resolved using Theorem 1 along
with at most one application of the fact that:

( K , L , N )-TFFs exist if and only if ( K , N − L , N )-TFFs exist, provided L < N,
and at most L − 1 repeated applications of the fact that:

( K , L , N )-TFFs exist if and only if ( K , ( K − 1) L − N , K L − N )-TFFs exist, provided L < K L − N
...
Using this idea, we then introduce several basic methods for constructing new
TFFs from existing ones
...
In Section 3, we
introduce a new fundamental technique for constructing unit norm tight frames
...
In the fourth section, this Spectral Tetris construction
is then combined with a new, modulation-based method for building TFFs, yielding modulated fusion frames, whose existence
is the key to proving Theorem 1
...

To be precise, we provide a simple iterative algorithm, dubbed the Tight Fusion Frame Existence Test, that quickly resolves
the existence of equal-rank TFFs in the few cases where Theorem 1 is ambiguous
...
Basic constructions
M
N
M
N
The synthesis operator of a finite sequence of vectors { f m }m
=1 in C is F : C → C ,

Fg =

M


g (m) f m ,

m =1

where, here and throughout, “g (m)” denotes the mth entry of the vector g
...
Generally speaking, frame theory is the study of how { f m }m
=1 should be chosen so as to ensure that the
M
∗
corresponding frame operator F F is well-conditioned
...


M
A unit norm tight frame (UNTF) is a tight frame { f m }m
=1 which further satisfies  f m  = 1 for all m = 1,
...
UNTFs
are known to exist for any M  N; the standard example is the harmonic frame, whose synthesis operator is obtained by
extracting any N distinct rows from a suitably scaled M × M discrete Fourier transform matrix
...

Fusion frame theory generalizes these concepts
...
Fusion frame theory is the study of sums of projections
of arbitrary rank, leading to the definition of a tight fusion frame given in (1)
...
Letting { f k,l }lL=1 be an orthonormal basis for the range of
P k , we classically know that:

Pk f =

L

 f , f k,l  f k,l
l =1

for all f ∈ C
...
, K yields:
N

P
...
Casazza et al
...
Comput
...
Anal
...
To be precise:
Definition 3
...
, K
...


(3)

k =1 l =1

Equivalently, the rows of the synthesis operator are mutually orthogonal with equal norm:
L
K 


f k,l (n) f k,l

 
n

k =1 l =1


=

A , n = n ,

(4)

n
= n
...
We now exploit this UNTF-based
representation, providing several methods for constructing new TFFs from existing ones
...
1
...
As such, the tensor product of two TFFs is
another TFF:
K

L

K

L

Theorem 4
...

Proof
...


Similarly, writing k, k , l, l in terms of k1 , k 1 , k2 , k 2 , l1 , l 1 , l2 , l 2 , one may easily show that:

hk,l , hk ,l  =  f k1 ,l1 , f k 1 ,l 1  gk2 ,l2 , gk 2 ,l 2 
...
Moreover, if k = k but l
= l , then
either l1
= l 1 or l2
= l 2 , and so (5) gives hk,l , hk,l  = 0, implying that for any fixed k = 1,
...
2
K K L L

Though elementary, this tensor product construction provides a simple proof of the first part of Theorem 1:
Corollary 5
...

L

Proof
...
(⇐) If K  NL , then there exists a UNTF of K elements for C L , see [1]
...
Also, any
orthonormal basis for C L is a (1, L , L )-TFF
...
2

178

P
...
Casazza et al
...
Comput
...
Anal
...
2
...
For the first complement, let { f k,l }kK=1, lL=1
generate a ( K , L , N )-TFF, and for each k = 1,
...
We claim that the vectors from this extension generate another TFF, dubbed the spatial complement of the original
...
If { f k,l }kK=1, lL=1 generates a ( K , L , N )-TFF and L < N, then any { gk,l }kK=1, lN =−1L ⊂ C N such that:

for each k = 1,
...

Proof
...
, K , the sequence { f k,l }lL=1 ∪ { gk,l }lN =−1L is an orthonormal basis for C N , implying { gk,l }kK=1, lN =−1L is
orthonormal and moreover:

f =

L
N
−L


 f , f k,l  f k,l +
 f , gk,l  gk,l
l =1

l =1

for all f ∈ C
...
, K yields:
L
K 

KL
K (N − L)
 f , f k,l  f k,l = K f −
f =
f

 f , gk,l  gk,l = K f −

k =1 l =1

N

k =1 l =1

for all f ∈ C N , as claimed
...
We claim these new vectors also generate a TFF, termed the Naimark
complement of the original, as the construction makes use of Naimark’s argument that every 1-tight frame is the projection
of an orthonormal basis
...
If { f k,l }kK=1, lL=1 generates a ( K , L , N )-TFF and N < K L, then any { gk,l }kK=1, lL=1 ⊂ C K L − N such that:

√
√
K
N
KL − N
f k,l ⊕ √
gk,l
√
KL

KL

L

k =1 , l =1

is an orthonormal basis for C K L

generates a ( K , L , K L − N )-TFF
...
Letting hk,l = √ N f k,l ⊕
KL

hk,l , hk,l  =

N
KL

√
K L−N
√
gk,l , note that for any k = 1,
...
, L,

 gk,l , gk,l 
...
At the same time, since {hk,l }kK=1, lL=1 is an orthonormal basis for C K L , then its synthesis operator is unitary
...
, K L − N, we have:
L
K
KL − N  

KL

gk,l (n) gk,l

 
n

k =1 l =1

and so { gk,l }kK=1, lL=1 satisfies (4)
...
For each ( K , L , N ) ∈ N such that L  N,
(i) (Spatial complements) If L < N, then ( K , L , N )-TFFs exist if and only if ( K , N − L , N )-TFFs exist
...


P
...
Casazza et al
...
Comput
...
Anal
...
If ( K , L , N )-TFFs exist and L does not divide N, then K   NL  + 1
...
If ( K , L , N )-TFFs exist, then K L  N
...
Thus, there exist L orthonormal vectors in C K L − N , and as such, L  K L − N
...

Since K is an integer, taking the ceiling of both sides of this equation yields the result
...
In particular, (3, 3, 4)-TFFs do not exist, despite the
fact that 3   43  + 1
...

One may preclude such simple counterexamples to the sufficiency of Corollary 9’s condition by making the further
requirement that 2L < N
...
To be precise, if a (4, 4, 11)-TFF did exist, then its Naimark complement, obtained by
4
applying Corollary 8(ii), would be a (4, 4, 5)-TFF, whose spatial complement would, in turn, be a (4, 1, 5)-TFF; such frames
do not exist since 4 <  51  + 1
...

However, one of the main results of this paper, as encapsulated in the final statement of Theorem 1, is to show that a
very slight strengthening of these conditions is actually sufficient for existence
...
That is, we will show that TFFs indeed exist whenever the number of subspaces K is at least two
more than what is absolutely necessary
...

3
...
The
M
N
key idea is to revisit the simpler problem of constructing UNTFs, that is, sequences { f m }m
=1 of unit vectors in C that
satisfy (2)
...

Despite a decade of study, very few general constructions of finite-dimensional UNTFs are known
...
In this section, we show that constructing certain
examples of UNTFs need not be so difficult
...
The key idea is to iteratively build a matrix F which, at each iteration, exactly
satisfies (i) and (ii), and gets closer to satisfying (iii)
...
Here, an illustrative example is helpful:
Example 10
...
At the same time, we claim in Theorem 1 that a slightly
stronger requirement, K   NL  + 2, is indeed sufficient for existence, provided L does not divide N and 2L < N
...
In this and the following sections, we will show how to explicitly construct such
a TFF, so as to illustrate the simple ideas behind the proof of Theorem 1(ii)
...

The first stage, given in the present example, is to play Spectral Tetris, yielding a sparse UNTF of 11 elements for C4
...

I
...

?⎦
?

(6)

If the remaining unknown entries are chosen so that F has orthogonal rows, then F F ∗ will be a diagonal matrix
...
Also note that if the remainder of the first

...
However, making the third column of F another copy of e 1 would add too much weight, as 3 >

11

...
G
...
/ Appl
...
Harmon
...
30 (2011) 175–187

a way to put 11
− 2 = 34 more weight in the first row without compromising the orthogonality of the rows of F nor the
4
normality of its columns
...
Specifically, we have:

1
T (x) := √
2




√
√
√ x
√ x
,
2−x − 2−x

T (x) T ∗ (x) =





x
0

...


?

?

?

?

?

?

?

⎥
⎥
⎥
0 ? ? ? ? ? ? ?⎦

8

(7)

The diagonal entries of F F ∗ are now { 11
, 5 +?, ?, ?}
...
The second entry is currently falling short by
while the sixth and seventh arise from

⎡

1 1

⎢
⎢
⎢0 0
F =⎢
⎢
⎢0 0
⎣
0

0

√
√3
8
√
√5
8

√
√3
8
√
5
−√

1

0

0

0

0

8

0

T ( 24 ):

0

0

0

√
√2
8
√
√6
8

√
√2
8
√
6
−√

0

0

The diagonal entries of F F ∗ are now { 11
,
4

11
4

− 54 =

= 1 + 24 , and as such, we make the fifth column e 2 ,

⎤

0

0

0

0

0

0

0

0⎥

8

⎥
⎥
⎥
...


and make the final

⎤

⎥
⎥
⎥
⎥
...
Each singleton contributes a value of 1 to a particular diagonal entry of F F ∗ , while
, 11
, 11
, 11
}, from
each pair spreads two units of weight over two entries
...
This construction is reminiscent of the game Tetris, as illustrated in Fig
...


Fig
...
The Spectral Tetris construction of a UNTF of 11 elements for C4 , as detailed in Example 10
...
For example, the
single frame element { f 2 } contributes {1, 0, 0, 0} to the diagonal, while the pair { f 6 , f 7 } contributes {0, 24 , 64 , 0}
...
In order for { f m }m
=1 to be a UNTF for C , these blocks needed to stack to a uniform height of 4
...


P
...
Casazza et al
...
Comput
...
Anal
...
In particular, we have that f m and f m
are orthogonal whenever m − m  5
...
These orthogonality relations will play a
the resulting frame elements satisfy  f m , f m  = 0 whenever m − m   M
N
critical role in the next section, where Spectral Tetris UNTFs will be modulated to form modulated TFFs
...
We say that a sequence { f m }m
=1 is an (m0 , n0 )-proto unit norm tight frame (PUNTF) for C if:


1, m  m0 ,
2
|
f
(
n
)|
=
n=1 m
0, m > m0 ,
M
) = 0 for all n, n = 1,
...

N
(i)

N

M
N
That is, { f m }m
=1 is an (m0 , n0 )-PUNTF for C precisely when its N × M synthesis matrix F vanishes off of its upper-left
n0 × m0 submatrix, its nonzero columns have unit norm, and its frame operator F F ∗ is diagonal, with the first n0 − 1 diagonal
, the n0 th entry lying in [1, M
], and the remaining entries being zero
...
As seen in Example 10, the
goal of Spectral Tetris is to iteratively create larger PUNTFs from existing ones, continuing until (m0 , n0 ) = ( M , N ), at which
point the PUNTF is a UNTF
...
Let 2N  M, let { f m }m
=1 be an (m0 , n0 )-PUNTF for C , and let λ :=

(i) If λ 

M
N

M

m=1 | f m (n0 )|

2


...

M
−1<λ< M
, then m0 < M − 2, n0 < N and { gm }m
(ii) If M
=1 ,
N
N

⎧
fm,
⎪
⎪

⎪
⎪
⎪
⎨ 1 ( M − λ)en0 + 1 − 1 ( M − λ)en0 +1 ,
2 N
2 N
gm := 

⎪
1 M
⎪
⎪
( − λ)en0 − 1 − 12 ( M
− λ)en0 +1 ,
⎪
2 N
N
⎪
⎩
0,

m  m0 ,
m = m 0 + 1,
m = m 0 + 2,
m > m 0 + 2,

is an (m0 + 2, n0 + 1)-PUNTF for C N
...

M
N
and n0 = N, then { f m }m
(iv) If λ = M
=1 is a UNTF for C
...
We first determine a relationship between m0 , n0 and λ
...


(10)

182

P
...
Casazza et al
...
Comput
...
Anal
...


(11)

Equating (10) and (11) then gives:

λ = m0 − n0

M
N

+

M
N

(12)


...

We focus on (ii), as it is the least trivial
...


(13)

If n0 = N, then (13) implies 0 < M − m0 < 1, a contradiction of the fact that M , m0 ∈ N
...
Moreover,
substituting the fact that n0  N − 1 into the left-hand inequality of (13) gives:

0 < n0

M
N

− m 0  ( N − 1)

M
N

− m0 = M −

M
N

− m0  M − 2 − m0 ,

where the last inequality follows from the global assumption that 2N  M
...
To continue, note
M
that since m0 < M − 2 and n0 < N, then m0 + 1 < M, m0 + 2 < M and n0 + 1  N, and so the sequence { gm }m
=1 given in
M
indeed
satisfies
the
four
properties
of
an
(
m
+
2
,
n
+
1
)
-PUNTF
...
We now verify that { gm }m
0
0
=1
M
f
m
m
is
an
(
m
,
n
)
-PUNTF
and
since
=
g
for
all
=


m
+
1
and
=


m
+
2,
then
Definition
11(i)
must
only
since { f m }m
0
0
m
m
0
0
=1
be verified for m = m0 + 1 and m = m0 + 2:
N


 fm

(n)
0 +1

n =1

 

 
 




N

2 1 M

1 M
1 M
1 M
 f m +2 (n)2
...
Definition 11(ii) is also immediately satisfied in the case where n > n0 + 1, as f m (n) = 0
for all m = 1,
...
, n0 − 1 and n = n0 + 1, as the supports of the corresponding
row vectors are disjoint
...
, n0 − 1, and n = n0 , in which:
M


m 0 +2



gm (n) gm (n0 ) =

m =1

gm (n) gm (n0 ) =

m =1

m0

m =1

and the case n = n0 and n = n0 + 1, in which:
M


gm (n0 ) gm (n0 + 1) =

m =1

m 0 +2

m0


gm (n0 ) · 0 +

m =1



f m (n) f m (n0 ) +

 

0 · gm (n0 ) = 0 + 0 = 0,

m=m0 +1

1

M

2

N


−λ

1−

1
2



M
N

 


−λ −

1

M

2

N


−λ

1−

1
2



M
N


− λ = 0
...
For n < n0 or n > n0 + 1, this follows
M
immediately from the fact that { f m }m
=1 is an (m0 , n0 )-PUNTF
...
Finally, we verify that { gm }m
=1 satisfies Definition 11(iv) where “n0 ” is n0 + 1
...
In particular, since 2N  M, then 1  λ∗  M
, as needed
...


P
...
Casazza et al
...
Comput
...
Anal
...
The proof of the fact that { gm }m=1 is a UNTF is very
similar to, but simpler than, the parallel argument above in the proof of (ii), and as such, is omitted
...
Therefore, { gm }m
note that (12) gives M
=1 is well-defined;
N
N
N
N
N
the proof that it is a UNTF is also left to the reader
...
2
N

Note that the assumption 2N  M is crucial to the proof of Theorem 12; in the case where λ is slightly smaller than M
,
N
the (n0 + 1)th diagonal entry of F F ∗ must accept nearly two spectral units of weight, which is only possible when the
is at least 2
...
Indeed, UNTFs of redundancy M
 32 can be constructed
N
using 3 × 3 Spectral Tetris submatrices, as we now have two diagonal entries over which to spread at most three units of
spectral weight; the blocks themselves are obtained by scaling the rows of a 3 × 3 discrete Fourier transform matrix
...
Note that these lower
levels of redundancy are only bought at the expense of a loss in sparsity, and in particular, a loss of orthogonality relations
between the frame elements themselves
...
In particular, by
playing Spectral Tetris with only 1 × 1 and 2 × 2 submatrices, that is, by repeatedly applying the rules of Theorem 12, one
obtains a UNTF in which many frame elements are mutually orthogonal:
M
N
Theorem 13
...

N
(1)

(1)

M
N
One may quickly verify that
Proof
...

j) M
this sequence is a (1, 1)-PUNTF
...
, J according
to Theorem 12
...
Take J  M to be the last iteration, namely the first j such that
( J) M
M
and n0 ( J ) = N, and so by (iv), { f m }m
m0 ( j )  M
...

( j)
Now, fix m = 1,
...
Considering (i), (ii) and (iii), we see that either m0 ( j ) = m or m0 ( j ∗ ) = m + 1
...
Recall that after constructing f m , we proceeded to construct f m for m > m using repeated applications of (i), (ii)
and (iii)
...
Therefore, we applied (i) precisely  M
− λ( j ∗ ) times
...
That is,  f m , f m  = 0 whenever m is greater
− λ( j ∗ ) and then further increasing m0 ( j ∗ ) by either 1 or 2, using
than the value obtained by first increasing m0 ( j ∗ ) by  M
N
rules (iii) or (ii), respectively
...


(14)

Noting that the definition of a PUNTF gives λ( j ∗ )  1 and recalling that m0 ( j ∗ )  m + 1, the left-hand side of (14) can be
bounded above by:

 

m0 j ∗ +



M
N


 


 
M
M
− λ j ∗ + 2  (m + 1) +
−1 +2=m+
+ 2
...

N
N

2

When M = 11, N = 4, the previous result states that the UNTF of Example 10 satisfies  f m , f m  = 0 whenever m − m  5
...

Also note that although this section’s results were proved in complex Euclidean space for the sake of consistency, the
frames obtained by playing Spectral Tetris with 1 × 1 and 2 × 2 submatrices are, in fact, real-valued
...
In particular, Spectral
Tetris provides a very simple proof of the existence of real UNTFs for any M  N: when 2N  M, the construction is direct;
Naimark complements then give real UNTFs with redundancy less than two
...
Modulated fusion frames
In this section, we provide the second half of a general method for constructing ( K , L , N )-TFFs when K   NL  + 2
...
G
...
/ Appl
...
Harmon
...
30 (2011) 175–187

Theorem 14
...

Proof
...
In particular, for any k = 1,
...
Furthermore, (4) is also satisfied:
L
K 


 

gk,l (n) gk,l n =

k =1 l =1

=

L
K
L 

N
L
N

e2π i(k−1)n/ K f n (l)e2π i(k−1)n / K f n (l) =

k =1 l =1

 f n , f n 





K,
0,

K | n
K  n

− n,
− n,


=

KL
,
N

0,

L
L 

N

f n (l) f n (l)

l =1

K
−1




e2π ik(n−n )/ K

k =0

n = n ,
n
= n ,

where the final equality follows from the assumption that  f n , f n  = 0 whenever K divides n − n
= 0
...
That is, the analysis operator of { gk,l }kK=1, lL=1 is obtained by vertically stacking modulated
copies of the synthesis operator of { f n }nN=1 , as illustrated in the following example
...
Recall that, by Theorem 13, the UNTF { f m }m
=1 for C constructed in Example 10 satisfies  f m , f m  = 0 when
ever m − m  5
...


We now apply this idea in general, using Theorem 14 to modulate the Spectral Tetris constructions of Theorem 13
...
These modulated fusion frames provide the final ingredient for the proof of our first main result:
Proof of Theorem 1
...
The case where L divides N is resolved in Corollary 5
...
For
the sufficient condition, further assume that K   NL  + 2
...
For any K   NL  + 2, applying Theorem 14 to this
UNTF produces a ( K , L , N )-TFF
...
However, this result is not a comprehensive characterization of existence
...

5
...
In particular, we prove Theorem 2
by showing that for a given K , L , N ∈ N with L < N, the Tight Fusion Frame Existence Test (TFFET) given in Table 2 will
terminate in at most L iterations of its “while” loop
...
In short, we now show that no more than L successive applications of Naimark and
spatial complements will inevitably relate an ambiguous triple to one that is not ambiguous:
Proof of Theorem 2
...
As seen in Line 2 of TFFET, let ( K , L 0 , N 0 ) = ( K , L , N ) if 2L  N, and
let ( K , L 0 , N 0 ) = ( K , N − L , N ) otherwise
...
For the ( j + 1)st iteration of the loop that begins on Line 4, note that if L j divides N j , then
the existence of ( K , L j , N j )-TFFs is characterized by Theorem 1, as implemented in Lines 5–7 of TFFET
...
All that remains
j
N
to be resolved is the ambiguous case where 2L j < N j , L j does not divide N j , and K =  L j  + 1
...
G
...
/ Appl
...
Harmon
...
30 (2011) 175–187

185

Table 1
The analysis operator of a (5, 4, 11)-TFF, as described in Example 15
...
The rows of
this matrix form a TFF for C11 consisting of 5 subspaces, each of dimension 4
...


⎡

1

⎢
⎢
⎢1
⎢
⎢
⎢1
⎢
⎢
⎢
⎢1
⎢
⎢
⎢1
⎢
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎢
⎢
⎢
⎢0
⎣
0

√
√3

√
√3

√
√3 w 2
8
√
√3 w 4

√
√3 w 4
8
√
√3 w 3

w4

√
√3 w
8
√
√3 w 3

√
√3 w 2
8
√
√3 w

0

√
√5

− √5

√
√5 w 2
8
√
√5 w 4

√
− √5 w 3
8
√
− √5 w

√
√5 w
8
√
√5 w 3

√
− √5 w 4
8
√
− √5 w 2

1

8

w
w2
w

3

0
0
0
0

8

8

8

8

8

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

8

8

8

0

0

0

0

0

0

0

0

0

0

0

1

√
√2

√
√2

0

0

0

w

4

√
√2

0

0

0

w

3

√
√2

√
√2 w
8
√
√2 w 2

8

0

0

0

w

2

√
√2

0

0

0

0

0

8

0

1

√
√7

√
√7

√
√7 w 3
8
√
√7 w

√
√7 w 4
8
√
√7 w 3

w3

√
√7 w 4
8
√
√7 w 2

√
√7 w 2
8
√
√7 w

√
√7

− √7

8
8
8

8

8

w

√
√2

√
√2 w 3
8
√
√2 w 4

8

√
− √6

8
8

8

0

0

0

0

√
√6

0

0

0

0

√
√6
8

− √6 w

0

0

0

0

√
√6
8

− √6 w 2

√
√

8
8
8

w2
w4

0

0

0

0

√
√6

0

0

0

0

√
√6

√
− √6 w 3
8
√
− √6 w 4

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

8
8

8

8

8

w

8
8

√
√7 w 3
8
√
√7 w
8

√
√7 w 4
8
√
√7 w 2
8

⎤

⎥
⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
0⎥
⎥
⎥
⎥
0⎥
⎥
⎥
0⎥
⎥
⎥
⎥
1⎥
⎥
⎥
⎥
1⎥
⎥
⎥
1⎥
⎥
⎥
⎥
1⎥
⎦
0⎥

0

√

8

0

8

8

8

√
√

8

− √7 w 4
√

8

− √7 w 3
√

8

− √7 w 2
√

8

− √7 w
8

1

Table 2
The Tight Fusion Frame Existence Test (TFFET)
...


01
02
03
04
05
06
07
08
09
10
11
12

set K , L , N ∈ N, L < N
if 2L > N , L := N − L
exists := ‘unknown’
while exists := ‘unknown’
if L | N
if K  NL , exists := ‘true’
else exists := ‘false’
else
if K >  NL  + 1, exists := ‘true’
else if K <  NL  + 1, exists := ‘false’
else N := K L − N , L := N − L
end while

In this case, we necessarily have L j < K L j − N j , and so we can apply Corollary 8(ii) and then Corollary 8(i) to obtain that
( K , L j , N j )-TFFs exist if and only if ( K , L j +1 , N j +1 ) := ( K , ( K − 1) L j − N j , K L j − N j )-TFFs exist
...
In essence, TFFET’s “while” loop first checks whether Theorem 1
resolves the existence of ( K , L j , N j )-TFFs; in the case where it does not, TFFET instead calculates the alternative triple
( K , L j +1 , N j +1 ) for which the question of TFF existence is equivalent to that of the original
...




Nj
Lj





+ 2 L j + ( K − 2) L j − 2N j )

186

P
...
Casazza et al
...
Comput
...
Anal
...
To show that TFFET completely characterizes the existence of equal-rank TFFs,
we therefore need only show that its “while” loop terminates after a finite number of steps
...
, L 0 − 1, the existence of ( K , L J , N J )-TFFs is resolved by Theorem 1
...
As such, L j decreases by at least 1 at each iteration, and
remains positive
...
2
We conclude this paper by using TFFET to find a closed form expression of all K , L , N ∈ N for which ( K , L , N )-TFFs do
not exist
...
1
...
We define
the level of ambiguity of ( K , L , N ) to be one less than the number of iterations of TFFET’s “while” loop that is necessary to
resolve the existence of corresponding TFFs
...
Triples of higher ambiguity may be characterized by reversing
TFFET’s analysis, that is, by repeatedly taking the Naimark complements of the spatial complements of 1-ambiguous triples:
Theorem 16
...
If ( K , L , N ) is ambiguous, then K  4
...

√
√
Here, α := 12 ( K − 2 + K 2 − 4K ), β := 12 ( K − 2 − K 2 − 4K )
...
Recall that if ( K , L , N ) is ambiguous, then 2L < N, L does not divide N and K =  NL  + 1
...
Having this fact, we next characterize all 1-ambiguous blank triples (ABT) ( K , L 1 , N 1 ), that is, 1-ambiguous
triples for which a corresponding TFF does not exist
...
At the same time, taking Naimark and then spatial
1
complements of ( K , L 1 , N 1 ) yields ( K , ( K − 1) L 1 − N 1 , K L 1 − N 1 ) = ( K , R , L 1 + R )
...

Since K  4 and R is an integer, we may reduce these three conditions to two: either 1  R < KL−1 1 when R divides L 1 or
1  R < KL−1 2 when R does not
...
Thus, we see that ( K , L 1 , N 1 ) is a 1-ABT if and only if 1  R < KL−1 2 and R
= KL−1 1 ,
namely (17)
...
Indeed, recalling TFFET, the spatial complement of the
Naimark complement of a j-ABT is a ( j − 1)-ABT
...
We therefore can use induction to verify (15) and (16) for all
J  1
...
To elaborate, (15) and (16) obviously hold when J = 1 and K = 4
...

= (α − β) 1 −
αβ

Thus (15) and (16) also hold when J = 1 and K > 4
...
Taking Naimark-of-spatial complements of ( K , L J , N J ) produces
( K , L J +1 , N J +1 ) = ( K , N J − L J , K ( N J − L J ) − N J )
...
Next, for K > 4, a straightforward computation reveals that L J +1 = N J − L J satisfies (15)
...
G
...
/ Appl
...
Harmon
...
30 (2011) 175–187

187

is:

(α + 1)α J −1 − (β + 1)β J −1
αJ −βJ
(α + 1)α J −1 − (β + 1)β J −1
N1 − K
L1 −
N1
α−β
α−β
α−β
(α + 1)2 α J −2 − (β + 1)2 β J −2
+
L1
α−β
α J −1 [( K − 1)α − 1] − β J −1 [( K − 1)β − 1]
=
N1
α−β
(α + 1)α J −2 [( K − 1)α − 1] − (β + 1)β J −2 [( K − 1)β − 1]
−
L1
α−β
(α + 1)α J − (β + 1)β J
(α + 1)2 α J −1 − (β + 1)2 β J −1
=
N1 −
L1,
α−β
α−β

N J +1 = K

as claimed in (16)
...
In particular, (4, 25, 53) has 8-ambiguity, meaning
TFFET’s “while” loop runs for 9 iterations:

(4, 25, 53) → (4, 22, 47) → (4, 19, 41) → (4, 16, 35) → (4, 13, 29) → (4, 10, 23) → (4, 7, 17) → (4, 4, 11)
→ (4, 1, 5)
...

Acknowledgments
We thank the anonymous reviewers for their helpful comments and suggestions
...
The views expressed in this
article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department
of Defense, or the U
...
Government
...
J
...
Fickus, Finite normalized tight frames, Adv
...
Math
...

B
...
Bodmann, Optimal linear transmission by loss-insensitive packet encoding, Appl
...
Harmon
...
22 (2007) 274–285
...
G
...
Fickus, Minimizing fusion frame potential, Acta Appl
...
107 (2009) 7–24
...
G
...
Kutyniok, Frames of subspaces, Contemp
...
345 (2004) 87–113
...
G
...
Kutyniok, Robustness of fusion frames under erasures of subspaces and of local frame vectors, Contemp
...
464 (2008) 149–160
...
G
...
Kutyniok, S
...
Comput
...
Anal
...

P
...
Casazza, G
...
Li, C
...
Rozell, Modeling sensor networks with fusion frames, in: Proc
...
6701, 2007, pp
...

G
...
Pezeshki, A
...
Calderbank, T
...
Comput
...

Anal
...

[9] P
...
Ruiz, D
...
Fourier Anal
...
, in press
...
J
...
N
...
H
...
Int
...
Acoust
...
, vol
...
709–712
...
J
...
H
...




---