Compressed sensing is an emerging field, which proposes that a small collection of linear projections of a sparse signal contains enough information for perfect reconstruction of the signal. In this thesis, we study the general problem of modeling and reconstructing spatially or temporally correlated sparse signals in a distributed scenario. The correlation among signals provides an additional information, which could be captured by joint sparsity models. After modeling the correlation, we propose two different reconstruction algorithms that are able to successfully exploit this additional information. The first algorithm is a very fast greedy algorithm, which is suitable for large scale problems and can exploit spatial correlation. The second algorithm is based on a thresholding algorithm and can exploit both the temporal and spatial correlation. We also generalize the standard joint sparsity model and propose a new model for capturing the correlation in the sensor networks.

Compressed sensing is an emerging field, which proposes that a small collection of linear projections of a sparse signal contains enough information for perfect reconstruction of the signal. In this thesis, we study the general problem of modeling and reconstructing spatially or temporally correlated sparse signals in a distributed scenario. The correlation among signals provides an additional information, which could be captured by joint sparsity models. After modeling the correlation, we propose two different reconstruction algorithms that are able to successfully exploit this additional information. The first algorithm is a very fast greedy algorithm, which is suitable for large scale problems and can exploit spatial correlation. The second algorithm is based on a thresholding algorithm and can exploit both the temporal and spatial correlation. We also generalize the standard joint sparsity model and propose a new model for capturing the correlation in the sensor networks.

This thesis is divided into two parts. In the first part, we show how problems of statistical inference and combinatorial optimization may be approached within a unified framework that employs tools from fields as diverse as machine learning, statistical physics and information theory, allowing us to i) design algorithms to solve the problems, ii) analyze the performance of these algorithms both empirically and analytically, and iii) to compare the results obtained with the optimal achievable ones. In the second part, we use this framework to study two specific problems, one of inference (compressed sensing) and the other of optimization (information hiding). In both cases, we review current approaches, identify their flaws, and propose new schemes to address these flaws, building on the use of message-passing algorithms, variational inference techniques, and spin glass models from statistical physics. / Esta tese está dividida em duas partes. Na primeira delas, mostramos como problemas de inferência estatística e de otimização combinatória podem ser abordados sob um framework unificado que usa ferramentas de áreas tão diversas quanto o aprendizado de máquina, a física estatística e a teoria de informação, permitindo que i) projetemos algoritmos para resolver os problemas, ii) analisemos a performance destes algoritmos tanto empiricamente como analiticamente, e iii) comparemos os resultados obtidos com os limites teóricos. Na segunda parte, este framework é usado no estudo de dois problemas específicos, um de inferência (compressed sensing) e outro de otimização (ocultação de dados). Em ambos os casos, revisamos abordagens recentes, identificamos suas falhas, e propomos novos esquemas que visam corrigir estas falhas, baseando-nos sobretudo em algoritmos de troca de mensagens, técnicas de inferência variacional, e modelos de vidro de spin da física estatística.

This thesis is divided into two parts. In the first part, we show how problems of statistical inference and combinatorial optimization may be approached within a unified framework that employs tools from fields as diverse as machine learning, statistical physics and information theory, allowing us to i) design algorithms to solve the problems, ii) analyze the performance of these algorithms both empirically and analytically, and iii) to compare the results obtained with the optimal achievable ones. In the second part, we use this framework to study two specific problems, one of inference (compressed sensing) and the other of optimization (information hiding). In both cases, we review current approaches, identify their flaws, and propose new schemes to address these flaws, building on the use of message-passing algorithms, variational inference techniques, and spin glass models from statistical physics. / Esta tese está dividida em duas partes. Na primeira delas, mostramos como problemas de inferência estatística e de otimização combinatória podem ser abordados sob um framework unificado que usa ferramentas de áreas tão diversas quanto o aprendizado de máquina, a física estatística e a teoria de informação, permitindo que i) projetemos algoritmos para resolver os problemas, ii) analisemos a performance destes algoritmos tanto empiricamente como analiticamente, e iii) comparemos os resultados obtidos com os limites teóricos. Na segunda parte, este framework é usado no estudo de dois problemas específicos, um de inferência (compressed sensing) e outro de otimização (ocultação de dados). Em ambos os casos, revisamos abordagens recentes, identificamos suas falhas, e propomos novos esquemas que visam corrigir estas falhas, baseando-nos sobretudo em algoritmos de troca de mensagens, técnicas de inferência variacional, e modelos de vidro de spin da física estatística.

Compressed sensing is an emerging approach for signal acquisition wherein theory has shown that a small number of linear, random projection of a signal contains enough information for reconstruction of the signal. Despite its potential to enable lightweight and inexpensive sensing hardware that simultaneously combines signal acquisition and dimensionality reduction, the compressed sensing of images and video still entails several challenges, in particular, a sensing-measurement operator which is difficult to apply in practice due to the heavy memory and computational burdens. Block-based random image sampling coupled with a projection-driven compressed-sensing recovery is proposed to address this challenge. For images, the block-based image acquisition is coupled with reconstruction driven by a directional transform that encourages spatial sparsity. Specifically, both contourlets as well as complex-valued dual-tree wavelets are considered for their highly directional representation, while bivariate shrinkage is adapted to their multiscale decomposition structure to provide the requisite sparsity constraint. Smoothing is achieved via a Wiener filter incorporated into iterative projected Landweber compressed-sensing recovery, yielding fast reconstruction. Also considered is an extension of the basic reconstruction algorithm that incorporates block-based measurements in the domain of a wavelet transform. The pro-posed image recovery algorithm and its extension yield images with quality that matches or exceeds that produced by a popular, yet computationally expensive, technique which minimizes total variation. Additionally, reconstruction quality is substantially superior to that from several prominent pursuits-based algorithms that do not include any smoothing. For video, motion estimation and compensation is utilized to promote temporal sparsity. Because video sequences have temporal redundancy in locations in which objects are moving while the background is still, a residual between the current frame and the previous frame compensated by object motion is shown to be more sparse than the orig-inal frame itself. By using residual reconstruction, information contained in the previous frame contributes to the reconstruction of the current frame. The proposed block-based compressed-sensing reconstruction for video outperforms a simple frame-byrame reconstruction as well as a 3D volumetric reconstruction in terms of visual quality. Finally, quantization of block-based compressed-sensing measurements is considered in order to generate a true bitstream from a compressed-sensing image acquisition. Specifically, a straightforward process of quantization via simple uniform scalar quantization applied in conjunction with differential pulse code modulation of the block-based compressed-sensing measurements is proposed. Experimental results demonstrate significant improvement in rate-distortion performance as compared scalar quantization used alone in several block-based compressed-sensing reconstruction algorithms. Additionally, rate-distortion performance superior to that of alternative quantized-compressed-sensing techniques relying on optimized quantization or reconstruction is observed.

Compressed sensing (CS) is an emerging technique that exploits the properties of a sparse or compressible signal to efficiently and faithfully capture it with a sampling rate far below the Nyquist rate. The primary goal of compressed sensing is to achieve the best signal recovery with the least number of samples. To this end, two research directions have been receiving increasing attention: customizing the measurement matrix to the signal of interest and optimizing the reconstruction algorithm. In this thesis, contributions in both directions are made in the Bayesian setting for compressed sensing. The work presented in this thesis focuses on the approximate message passing (AMP) schemes, a new class of recovery algorithm that takes advantage of the statistical properties of the CS problem. First of all, a complete sample distortion (SD) framework is presented to fundamentally quantify the reconstruction performance for a certain pair of measurement matrix and recovery scheme. In the SD setting, the non-optimality region of the homogeneous Gaussian matrix is identified and the novel zeroing matrix is proposed with an improved performance. With the SD framework, the optimal sample allocation strategy for the block diagonal measurement matrix are derived for the wavelet representation of natural images. Extensive simulations validate the optimality of the proposed measurement matrix design. Motivated by the zeroing matrix, we extend the seeded matrix design in the CS literature to the novel modulated matrix structure. The major advantage of the modulated matrix over the seeded matrix lies in the simplicity of its state evolution dynamics. Together with the AMP based algorithm, the modulated matrix possesses a 1-D performance prediction system, with which we can optimize the matrix configuration. We then focus on a special modulated matrix form, designated as the two block matrix, which can also be seen as a generalization of the zeroing matrix. The effectiveness of the two block matrix is demonstrated through both sparse and compressible signals. The underlining reason for the improved performance is presented through the analysis of the state evolution dynamics. The final contribution of the thesis explores improving the reconstruction algorithm. By taking the signal prior into account, the Bayesian optimal AMP (BAMP) algorithm is demonstrated to dramatically improve the reconstruction quality. The key insight for its success is that it utilizes the minimum mean square error (MMSE) estimator for the CS denoising. However, the prerequisite of the prior information makes it often impractical. A novel SURE-AMP algorithm is proposed to address the dilemma. The critical feature of SURE-AMP is that the Stein’s unbiased risk estimate (SURE) based parametric least square estimator is used to replace the MMSE estimator. Given the optimization of the SURE estimator only involves the noisy data, it eliminates the need for the signal prior, thus can accommodate more general sparse models.

Tandem source-channel coding is proven to be optimal by Shannon given unlimited delay and complexity in the coders. Under low delay and low complexity constraints, joint source-channel coding may achieve better performance. Although digital joint source-channel coding has shown a noticeable gain in terms of reconstructed signal quality, coding delay, and complexity, it suffers from the leveling-off effect. However, analog systems do not suffer from the leveling-off effect. In this thesis, we investigate the advantage of analog systems based on the Shannon-Kotel’nikov approach and hybrid digital-analog coding systems, which combine digital and analog schemes to achieve a graceful degradation/improvement over a wide range of channel conditions. First, we propose a low delay and low complexity hybrid digital-analog coding that is able to achieve high (integer) expansion ratios ( >3). This is achieved by combining the spiral mapping with multiple stage quantizers. The system is simulated for a 1 : 3 bandwidth expansion and the behavior for a 1 : M (with M an integer >3) system is studied in the low noise level regime. Next, we propose an analog joint source-channel coding system that is able to achieve a low (fractional) expansion ratio between 1 and 2. More precisely, this is an N : M bandwidth expansion system based on combining uncoded transmission and a 1 : 2 bandwidth expansion system (with N < M < 2N).Finally, a 1 : 2 analog bandwidth expansion system using the (Shannon-Kotel’nikov) Archimedes’ spiral mapping is used in the compressed sensing context, which is inherently analog, to increase the system’s immunity against channel noise. The proposed system is compared to a conventional compressed sensing system that assumes noiseless transmission and a compressed sensing based system that account for noise during signal reconstruction. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2011-07-29 02:30:11.978

Electrocardiogram (ECG) is a noninvasive technology widely used in health care systems for diagnosis of heart diseases, and a wearable ECG sensor with long-term monitoring is necessary for real-time heart disease detection. However, the conventional ECG is restricted considering the physical size and power consumption of the system. In this thesis, we propose a Wireless ECG System with Bluetooth Low Energy (BLE) and Compressed Sensing (CS). The proposed Wireless ECG System includes an ECG sensor board based on a BLE chip, an Android application and a web service with a database. The ECG signal is first collected by the ECG Sensor Board and then transmitted to the Android application through BLE protocol. At last, the ECG signal is uploaded to the cloud database from the Android app. We also introduce Compressed Sensing into our system with a novel sparse sensing matrix, data compression and a modified Compressive Sampling Matching Pursuit (CoSaMP) reconstruction algorithm. Experiment results show that the amount of data transmitted is reduced by about 57% compared to not using Compressed Sensing, and reconstruction time is 64% less than using Orthogonal Matching Pursuit (OMP) or Iterative Re-weighted Least Squares (IRLS) algorithm. / Graduate

Purpose: Lung function is typically characterized by spirometer measurements, which do not offer spatially specific information. Imaging during exhalation provides spatial information but is challenging due to large movement over a short time. The purpose of this work is to provide a solution to lung imaging during forced expiration using accelerated magnetic resonance imaging. The method uses radial golden angle stack-of-stars gradient echo acquisition and compressed sensing reconstruction. Methods: A technique for dynamic three-dimensional imaging of the lungs from highly undersampled data is developed and tested on six subjects. This method takes advantage of image sparsity, both spatially and temporally, including the use of reference frames called bookends. Sparsity, with respect to total variation, and residual from the bookends, enables reconstruction from an extremely limited amount of data. Results: Dynamic three-dimensional images can be captured at sub-150 ms temporal resolution, using only three (or less) acquired radial lines per slice per timepoint. The images have a spatial resolution of 4.6 x 4.6 x 10 mm. Lung volume calculations based on image segmentation are compared to those from simultaneously acquired spirometer measurements. Conclusion: Dynamic lung imaging during forced expiration is made possible by compressed sensing accelerated dynamic three-dimensional radial magnetic resonance imaging. (C) 2015 Wiley Periodicals, Inc.

Pendant ma thèse, j’ai eu la chance d’apprendre et de travailler sous la supervision de mon directeur de thèse Rémi, et ce dans deux domaines qui me sont particulièrement chers. Je veux parler de la Théorie des Bandits et du Compressed Sensing. Je les voie comme intimement liés non par les méthodes mais par leur objectif commun: l’échantillonnage optimal de l’espace. Tous deux sont centrés sur les manières d’échantillonner l’espace efficacement : la Théorie des Bandits en petite dimension et le Compressed Sensing en grande dimension. Dans cette dissertation, je présente la plupart des travaux que mes co-auteurs et moi-même avons écrit durant les trois années qu’a duré ma thèse. / During my PhD, I had the chance to learn and work under the great supervision of my advisor Rémi (Munos) in two fields that are of particular interest to me. These domains are Bandit Theory and Compressed Sensing. While studying these domains I came to the conclusion that they are connected if one looks at them trough the prism of optimal sampling. Both these fields are concerned with strategies on how to sample the space in an efficient way: Bandit Theory in low dimension, and Compressed Sensing in high dimension. In this Dissertation, I present most of the work my co-authors and I produced during the three years that my PhD lasted.