DOI

https://doi.org/10.25772/Y4NE-PP95

Author ORCID Identifier

0000-0002-5057-9132

Defense Date

2016

Document Type

Dissertation

Degree Name

Doctor of Philosophy

Department

Engineering

First Advisor

Ruixin Niu

Abstract

In this dissertation, two classes of distributed algorithms are developed for sparse signal recovery in large sensor networks. All the proposed approaches consist of local computation (LC) and global computation (GC) steps carried out by a group of distributed local sensors, and do not require the local sensors to know the global sensing matrix. These algorithms are based on the original approximate message passing (AMP) and iterative hard thresholding (IHT) algorithms in the area of compressed sensing (CS), also known as sparse signal recovery. For distributed AMP (DiAMP), we develop a communication-efficient algorithm GCAMP. Numerical results demonstrate that it outperforms the modified thresholding algorithm (MTA), another popular GC algorithm for Top-K query from distributed large databases. For distributed IHT (DIHT), there is a step size $\mu$ which depends on the $\ell_2$ norm of the global sensing matrix A. The exact computation of $\|A\|_2$ is non-separable. We propose a new method, based on the random matrix theory (RMT), to give a very tight statistical upper bound of $\|A\|_2$, and the calculation of that upper bound is separable without any communication cost. In the GC step of DIHT, we develop another algorithm named GC.K, which is also communication-efficient and outperforms MTA. Then, by adjusting the metric of communication cost, which enables transmission of quantized data, and taking advantage of the correlation of data in adjacent iterations, we develop quantized adaptive GCAMP (Q-A-GCAMP) and quantized adaptive GC.K (Q-A-GC.K) algorithms, leading to a significant improvement on communication savings.

Furthermore, we prove that state evolution (SE), a fundamental property of AMP that in high dimensionality limit, the output data are asymptotically Gaussian regardless of the distribution of input data, also holds for DiAMP. In addition, compared with the most recent theoretical results that SE holds for sensing matrices with independent subgaussian entries, we prove that the universality of SE can be extended to far more general sensing matrices. These two theoretical results provide strong guarantee of AMP's performance, and greatly broaden its potential applications.

Rights

© The Author

Is Part Of

VCU University Archives

Is Part Of

VCU Theses and Dissertations

Date of Submission

12-15-2016

Share

COinS