Subsampling In Information Theory And Data Processing

Download or read book Subsampling in Information Theory and Data Processing written by Yuxin Chen and published by . This book was released on 2014 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: An ubiquitous challenge in modern data and signal acquisition arises from the ever-growing size of the object under study. Hardware and power limitations often preclude sampling with the desired rate and precision, which motivates the exploitation of signal and/or channel structures in order to enable reduced-rate sampling while preserving information integrity. This thesis is devoted to understanding the fundamental interplay between the underlying signal structures and the data acquisition paradigms, as well as developing efficient and provably effective algorithms for data reconstruction. The main contributions of this thesis are as follows. (1) We investigate the effect of sub-Nyquist sampling upon the capacity of a continuous-time channel. We start by deriving the sub-Nyquist sampled channel capacity under periodic sampling systems that subsume three canonical sampling structures, and then characterize the fundamental upper limit on the capacity achievable by general time-preserving sub-Nyquist sampling methods. Our findings indicate that the optimal sampling structures extract out the set of frequencies that exhibits the highest signal-to-noise ratio and is alias-suppressing. In addition, we illuminate an intriguing connection between sampled channels and MIMO channels, as well as a new connection between sampled capacity and MMSE. (2) We study the universal sub-Nyquist design when the sampler is designed to operate independent of instantaneous channel realizations, under a sparse multiband channel model. We evaluate the sampler design based on the capacity loss due to channel-independent sub-Nyquist sampling, and characterize the minimax capacity loss. This fundamental minimax limit can be approached by random sampling in the high-SNR regime, which demonstrates the optimality of random sampling schemes. (3) We explore the problem of recovering a spectrally sparse signal from a few random time-domain samples, where the underlying frequencies of the signal can assume any continuous values in a unit disk. To address a basis mismatch issue that arises in conventional compressed sensing methods, we develop a novel convex program by exploiting the equivalence between (off-the-grid) spectral sparsity and Hankel low-rank structure. The algorithm exploits sparsity while enforcing physically meaningful constraints. Under mild incoherence conditions, our algorithm allows perfect recovery as soon as the sample complexity exceeds the spectral sparsity level (up to a logarithmic gap). (4) We consider the task of covariance estimation with limited storage and low computational complexity. We focus on a quadratic random measurement scheme in processing data streams and high-frequency signals, which is shown to impose a minimal memory requirement and low computational complexity. Three structural assumptions of covariance matrices, including low rank, Toeplitz low rank, and jointly rank-one and sparse structure, are investigated. We show that a covariance matrix with any of these structures can be universally and faithfully recovered from near-minimal sub-Gaussian quadratic measurements via efficient convex programs for the respective structure. All in all, the central theme of this thesis is on the interplay between economical subsampling schemes and the structures of the object under investigation, from both information-theoretic and algorithmic perspectives.