Sparse Recovery with Fusion Frames

Abstract

Sparse signal structures have become increasingly important in signal processing applications as the technology progresses and a plethora of data needs to be handled. It has been shown in practice that various signals have fewer degrees of freedom compared to their actual sizes, i.e., can be expressed in terms of a small number of elements from some dictionary. Alongside an increase in applications, a recent theory of sparse and compressible signal recovery has been recently developed under the name of Compressed Sensing (CS). This approach states that a sparse signal can be efficiently recovered from a small number of random linear measurements.<br /> Another powerful tool in signal processing is frames which provide redundant representations for signals. Such redundancy is desirable in many applications where resilience to errors and losses in data is important. The increase in data has also significantly increased the demand to model applications requiring distributed processing which goes beyond the classical frames. The recent theory of Fusion Frames, which can be regarded as a generalization of classical frames, satisfies those needs by analyzing signals by projecting them onto multidimensional subspaces. Fusion frames provide a suitable mathematical framework to model large data systems such as sensor networks, transmission of data of communication networks, etc. <br /> In this thesis, we combine these two recent theories and consider the recovery of signals that have a sparse representation in a fusion frame. As in the classical CS, a sparse signal from a fusion frame can be sampled using very few random projections and efficiently recovered using a convex optimization that minimizes the mixed <em>l₁/l₂</em>-norm. This problem has close connections with other similar recovery problems studied in CS literature such as block sparsity and joint sparsity problems. A key contribution in this thesis is to exploit the incoherence of the fusion frame subspaces in order to enhance the existing recovery results by incorporating this structure. In particular, we derive upper and lower bounds for the number of measurements required for the sparse recovery and the error derived by convex optimization. Aside from our results in the fusion frame setup, we also present results in the classical CS where we focus on improving constants appearing in the number of measurements required and prove optimal constants in the nonuniform setting with rather concise and simple proofs.