FUSION FRAMES AND PARALLEL PROCESSING

SHIDONG LI

Like many parallel processing mechanisms, splitting a large system into multiple smaller systems for simpler and parallel processing is a common demand. For a more robust subdivision mechanism, one may not want to (sometimes it is impossible to) split the large system in an independent or orthogonal fashion. Nevertheless the subsequent fusion process must take into account a coherent and precise combination after the parallel subsystem processing.

Fusion frame systems are created to fit such needs as well. It allows for subdivision with overlaps for parallel processing, followed by a coherent and precise fusion combination. Fusion frame theory is also equipped with a weighted coherent combination of subsystems. It is designed for applications where losses and/or inaccuracy of some subsystem information occur. Weighted coherent combination can then be used to weigh-in more dependable subspace information and weigh-out less reliable ones for an efficient approximation.

Depending on applications, some may have a set of local projections {PWjf} of the signal at hand, where the fusion process is given by, via the inverse of the fusion frame operator SW,

               ∑         (     )
∀f ∈ H,    f =     v2iS -W1 PWj f  .
                i∈I
(1)

Such applications occur in, e.g., sensor networks,1 and geophones in geophysics measurements.2 Some other applications, on the other hand, may need to have the measurement coefficients of a signal {⟨f,fij⟩} (such as in parallel processing of large frame systems), then the fusion process can also be written as

               ∑    2∑           -1(   )
∀f ∈ H,    f =     vi    〈f,fij〉S W   ˜fij  .
                i∈I   j∈Ji
(2)

The fusion procedures (1) and (2) both have their needs and advantages in actual practical applications. Though much is still to be learned, some superficial computational complexity of (1) and (2) can be assessed. Procedure (1) has Ioperations of SW-1 over local projections, followed by Iscalar-vector multiplications. Meantime, procedure (2) requires i∈IJi operations of SW-1 over local dual frames {˜f ij} and i∈IJi follow-up scalar-vector multiplications. (1) therefore seems to have generally less computational complexity except that the Ioperations of applying SW-1 must be carried out real-time or “on-line”, whereas the largerS W-1 operation requirement in (2) can be carried out “off-line” prior to reconstruction needs, which often-times can be advantageous.

We must point out that much is still to be studied in the application of fusion frames in parallel processing. Some involves inevitable fusion frame modeling and thereby natural parallel processing and fusion operations. These include various sensor network data fusion applications with preliminary reports.3 More challenge problems lie in large system subdivision for the purpose of efficient parallel processing. One must not forget that one key step at measuring the efficiency of the fusion operation is the evaluation of SW-1 itself and the multiplications necessary when SW-1 is applied. Unless S W and SW-1 are sufficiently sparse, all gains in parallel processing may simply be lost in the evaluation and application of SW-1 at the end. This obviously has a lot to so with subspace division of which some have been studied,4 5 which is also highly relevant to sparse representation of fusion frames as well. The subspace division is so delicate that there is no “linearity” here as the fusion frame operators SW, for two extreme cases H = i∈IWi and H = Wi (i ∈ I), are both identities up to a multiple constant.

We would also like to mention that domain decomposition6 is much relevant to the fusion frame mechanism. It might be possible to employ methods from domain decomposition such as Schwartz multiplicative and additive alternating algorithms for computing SW-1 “on-line” by using local inversions.ibid. Details are to be carried out.

1S. S. Iyengar and R. R. Brooks, eds., Distributed Sensor Networks, Chapman & Hall/CRC, Baton Rouge, 2005.

2M. S. Craig and R. L. Genter, Gophone array formation and semblance evaluation, Geophysics 71, 2006, 1–8.

3P. G. Casazza, G. Kutyniok, S. Li, and C. J. Rozell, Modeling Sensor Networks with Fusion Frames, Wavelets XII (San Diego, CA, 2007), 67011M-1–67011M-11, SPIE Proc. 6701, SPIE, Bellingham, WA, 2007.

4A. Pezeshki, G. Kutyniok, and A. R. Calderbank, Fusion frames and Robust Dimension Reduction. 42nd Annual Conference on Information Sciences and Systems (CISS) (Princeton University, NJ, 2008)

5G. Kutyniok, A. Pezeshki, R. Calderbank, and T. Liu, Robust Dimension Reduction, Fusion Frames, and Grassmannian Packings. Appl. Comput. Harmon. Anal., to appear

6A. Toselli and O. Widlund, Domain Decomposition Methods - Algorithms and Theory, Springer Series in Computational Mathematics 34, Springer-Verlag, Berlin, 2005.