Exploiting Sparsity for Data Dimensionality-Reduction

Data compression has well-appreciated impact in audio, image and video processing since the increasing data rates cannot be matched by the computational and storage capabilities of existing processing units. The cornerstone modules of modern digital compression systems are those performing dimensionality reduction and quantization. Dimensionality reduction projects the data onto a space of lower dimension while minimizing an appropriate figure of merit that quantifies information loss. Quantization amounts to digitizing the analog-amplitude, reduced-dimensionality data. Typically, dimensionality reduction relies on training vectors to find parsimonious data representations with minimal redundancy without inducing significant distortion in the reconstruction process.;Among other signal characteristics used for compression, a critical one dealt with in this thesis is sparsity. Sparsity is an attribute characterizing many natural and man-made signals, and has been used extensively in signal processing to solve underdetermined systems of equations and perform variable selection. The bulk of existing literature has focused on exploiting sparsity structures that are present in the data. However, sparsity may oftentimes appear in statistical descriptors, such as covariance matrices, and not the data themselves. Statistical descriptors are instrumental when it comes to data dimensionality reduction and compression. Sparsity in such data descriptors can be exploited to boost performance of existing dimensionality reducing and reconstruction modules.;Specifically, the presence of sparsity in the eigenspace of signal covariance matrices is studied and exploited for data compression and denoising. The dimensionality reduction and quantization modules are redesigned to capitalize on such forms of sparsity and achieve improved reconstruction performance compared to existing sparsity-agnostic codecs. Using training data that may be noisy, a novel sparsity-aware linear dimensionality-reduction scheme is developed to fully exploit covariance-domain sparsity and form noise-resilient estimates of the principal covariance eigen-basis. Sparsity is effected via norm-one regularization, and the associated minimization problems are solved using computationally efficient coordinate descent iterations. Adaptive implementations that allow online data processing are also explored. The resulting covariance eigenspace estimator is shown capable of identifying a subset of the unknown support of the eigenspace basis vectors even when the observation noise covariance matrix is unknown, as long as the noise power is sufficiently low. It is established that the sparsity-aware estimator is asymptotically normal, and the probability to correctly identify the signal subspace basis support approaches one, as the number of training data grows large. The sparsity-aware dimensionality reducing scheme is further combined with vector quantization to obtain a sparsity-cognizant transform coding scheme capitalizing on covariance-domain sparsity for data compression, reconstruction and denoising. Finally, simulations using synthetic data and images, corroborate that the proposed algorithms achieve improved reconstruction quality relative to alternatives.