The Theory of Fusion Frames

In the following we will give a short introduction into the theory of fusion frames, during which sensor networks will serve as our main example. Our aim will be to develop a mathematical theory which models the structure of sensor networks. Our theory is further used, for instance, to model the behavior of the neural cells of our brain while processing and storing information and to derive efficient processing for large data sets.

In wireless sensor networks, sensors of limited capacity and power are spread in an area sometimes as large as an entire forest to measure the temperature, sound, vibration, pressure, motion and/or pollutants. In some applications, wireless sensors are placed in a geographical area to detect and characterize chemical, biological, radiological, and nuclear material. Such a sensor system is typically redundant, and there is no orthogonality among sensors, therefore each sensor functions as a frame element in the system. Due to practical and cost reasons, most sensors employed in such applications have severe constraints in their processing power and transmission bandwidth. They often have strictly metered power supply as well. Consequently, a typical large sensor network necessarily divides the network into redundant sub-networks -- forming a set of subspaces. The primary goal is to have local measurements transmitted to a local sub-station within a subspace for a subspace combining. An entire sensor system in such applications could have a number of such local processing centers. They function as relay stations, and have the gathered information further submitted to a central processing station for final assembly.

Fusion frame systems are created to model sensor networks perfectly. The sensors in each sub-network are modeled as frame vectors, which form a frame for a subspace in a Hilbert space. The subspaces, i.e., the sub-networks, have to satisfy a certain overlapping property, which ensures that the overlaps are not too large. In practise this condition will always be fulfilled, since we are mostly dealing with finite-dimensional Hilbert spaces, and finite sets of subspaces. The reconstruction in such a system is done in two steps. Inside the subspaces the conventional frame reconstruction is employed. These local reconstructions then serve as the inputs for the fusion frame reconstruction, which reconstructs the initial signal completely.

In the following we will first describe the basic definitions and notations related to fusion frames, and the focus on reconstruction issues.

Definition of a Fusion Frame

Let I be some index set, let {Wi}i ∈ I be a family of closed subspaces in H, and let {vi}i ∈ I be a family of weights, i.e., vi > 0 for all i ∈ I. Further we denote the orthogonal projections onto Wi by Pi. Then {(Wi,vi)}i ∈ I is a fusion frame, if there exist positive, finite constants C and D such that

C||f||2Σi ∈ I vi2 ||Pi(f)||2 ≤ D||f||2 for all f ∈ H.

Let {Wi}i ∈ I be a fusion frame for H, and let {fij}j ∈ Ji, i ∈ I be a frame for Wi for each i ∈ I. Then we call {(Wi,vi,{fij}j ∈ Ji)}i ∈ I a fusion frame system for H.

In frame theory an input signal is represented by a collection of scalar coefficients that measure the projection of that signal onto each frame vector. The representation space employed in this theory equals l2(I). However, in fusion frame theory an input signal is represented by a collection of vector coefficients that represent the projection (not just the projection energy) onto each subspace. Therefore the representation space employed in this setting is

i ∈ I ⊕ Wi)l2 = {{fi}i ∈ I | fi ∈ Wi and {||fi||}i ∈ Il2(I)}.

Let {(Wi,vi)}i ∈ I be a fusion frame for H. In order to map a signal to the representation space, i.e., to analyze it, the analysis operator T is employed, which is defined by
T : H → i ∈ I ⊕ Wi)l2 with T(f) = {vi Pi(f)}i ∈ I .

It can easily be shown that the synthesis operator T*, which is defined to be the adjoint operator, is given by
T* : i ∈ I ⊕ Wi)l2 → H with T*(f) = Σi ∈ I vi fi, where f = {fi}i ∈ Ii ∈ I ⊕ Wi)l2.

Now we can give the definition of a fusion frame operator. The fusion frame operator S for {(Wi,vi)} i ∈ I is defined by
S(f) = T* º T (f) = Σi ∈ I vi2 Pi(f).

This is a positive and invertible operator on H.

Finite frame setting:
For computational needs, let us further consider the fusion frame operator in finite frame settings, where the fusion frame operator will become the sum of (weighted) matrices of each subspace frame operator. Let Fi be the frame matrices formed by frame vectors {fij}j ∈ Ji in the column-by-column format [Fi ≡ (fi1, fi2,...,fiji)]. Similarly, let Gi be defined in the same way by the dual frame {gij}j ∈ Ji. Then the fusion frame operator associated with finite frames has the expression

S(f) = Σi ∈ I vi2 FiGiH = Σi ∈ I vi2 GiFiH,

where MH stands for the Hermitian transpose of a matrix M. Therefore, the evaluation of the fusion frame operator and the inverse fusion frame operator in finite frame settings are quite straightforward. In practical applications, this will turn out to be very convenient.

Reconstruction using a Fusion Frame

The first fundamental observation we make consists of the fact that distributed fusion processing is feasible in an elegant way by employing the inverse fusion frame operator. Let {(Wi,vi)}i ∈ I be a fusion frame for H with fusion frame operator S. Then we have the reconstruction formula

f = Σi ∈ I vi2 S-1 º Pi(f) for all f ∈ H.

The fusion frame theory in fact provides two different approaches for distributed fusion procedures. For this, let {(Wi,vi,{fij}j ∈ Ji)}i ∈ I be a fusion frame system for H, let S be the associated fusion frame operator, and let {gij}j ∈ Ji, i ∈ I be associated local dual frames.
One distributed fusion procedure is from the local projections of each subspace:
f = Σi ∈ I vi2 S-1 º Pi(f) = Σi ∈ I vi2 S-1 j ∈ J i <f,fij> gij) for all f ∈ H.

In this procedure, the local reconstruction takes place first in each subspace Wi, and the inverse fusion frame is applied to each local reconstruction and combined together.
Another form of distributed fusion actually acts like a global reconstruction if the coefficients of signal/function decompositions are available:
f = Σi ∈ I vi2 Σj ∈ J i <f,fij> (S-1gij) for all f ∈ H.

The difference in this fusion procedure compared with global frame reconstruction lies in the fact that the (global) dual frame {S-1gij} is first calculated at the local level, and then fused into the global dual frame by applying the inverse fusion frame operator. This makes the evaluation of (global) duals much more efficient.


We hope that this short introduction arouse your interest in fusion frames! For further aspects of the theory and further results we refer to our publications!