Fast and Robust Algorithms for Compressive Sensing and Other Applications

Efficiency and robustness are often the main concerns in model design and algorithm development. Nowadays a lot of algorithms have been proposed with emphasis on one or the other. This thesis provides several algorithms together with their applications to address these two needs. The first part of the thesis discusses the efficiency concern in video compression and reconstruction. With the increasing demand in real-time data transmission and storage, these two problems are attracting more and more attention. In terms of video compression, classic models often use a fixed temporal compression rate, while there are many potential gains in developing systems and procedures incorporating adaptive temporal compression rate. In Chapter 2, an algorithm based on local patches and polynomial fitting is proposed to adaptively predicts the temporal compression rate given the behavior of a few previous compressed frames. As for the inverse model, Chapter 3 presents a fast total variation based method for reconstructing video compressive sensing data. The regularization in the model is imposed on both the spatial and temporal components, which provides a more consistent approximation of the connection between neighboring frames with little to no increase in model complexity.The second part of the thesis covers a new technique named adaptive outlier pursuit for handling sparsely corrupted data. In many real world applications, noise is often unavoidable during data acquisition and transmission. Some noise can damage part of the data seriously and make it contain no useful information at all. Algorithms robust to this type of noise are strongly needed. The technique adaptive outlier pursuit is introduced to deal with outliers in the acquired measurements. Instead of detecting and removing the outliers before applying classic algorithms, it alternates between the outlier detection and the signal reconstruction task, hence iteratively approaches the true signal in a more accurate way. It is applied to robust 1-bit compressive sensing and exact matrix completion in Chapter 5 and Chapter 6 respectively