Practical algorithms for compressive sensing and their applications to multimedia processing

Over the past few years, the Compressive Sensing (CS) framework has been growing very rapidly as it attracts increasingly more interests from researchers in various fields such as statistics, information theory, applied mathematics, signal processing, coding theory and theoretical computer science. Despite major successful achievements, most of these current works focus more on theoretical aspects with simulated settings. There has been little attention and few successes to realize practical CS systems and further, to investigate potential applications of novel lessons and principles in the CS paradigm to other signal processing problems. These unexplored areas are the major emphasis of this dissertation work.;In the first part of this thesis, we propose a practical and flexible design for a complete CS system that includes (i) a new family of sensing matrices/ensembles, namely Structurally Random Matrices, that are fast computable and very easy to implement in hardware and optics; and (ii) a novel sparse signal recovery from an incomplete set of measurements, namely Sparsity Adaptive Matching Pursuit. Our designs meet all requirements of a practical CS system such as: simplicity, real-time and block-based processing support, fast and efficient operation, low-cost implementation. We also present a rigorous theoretical framework to analyze trade-offs between sensing performance and these practical advantages.;In the second part of this thesis, we propose a few successful examples of applying novel principles in the CS theory to design novel applications in multimedia processing. In particular, we first propose a new solution for Distributed Video Coding (DVC). Our key observation comes from the fact that DVC and CS share a common paradigm that computational complexity is shifted from the encoder side to the decoder side. The framework can be regarded as a marriage between the CS theory and the DVC theory that retains best features from both frameworks in order to achieve higher performance and other practical benefits. Finally, we propose a novel framework of robust video transmission that attempts to mitigate the packet-loss effect in packet-switched networks. The proposed approach appears to be competitive with the popular forward error correction (FEC) code as it is more robust to packet-loss and can retain quality of transmitted video signals more stably. Further, these proposed frameworks contain a few novel concept and techniques such as Interframe Sparsity Model for video patches. Sparsity Constraint Block Prediction Algorithm, Sparse Signal Recovery with Side Information, each of which might have independent applications in the field of signal processing.