State reconstruction from partial observations: theory and applications

This thesis considers the problem of signal reconstruction in the setting of partial observations. We consider this in three different contexts. First, we consider the abstract problem of determining the state of a time-varying vector at discrete time instances, in a setting where the changes are sparse (i.e., only a few components of the vector change at each time). Given a collection of observers, each of which is able to provide linear mixtures of a subset of the components, the goal is to determine the vector values at certain desired time instants. We derive conditions on the number of measurements, observers, and their corresponding subsets that lead to exact reconstruction (with high probability) of the signal at the desired time instants. We then propose an iterative algorithm that can achieve such a reconstruction, and present simulation results to demonstrate its performance. Furthermore, we propose an $\ell 1$ relaxed heuristic and simulate its performance.

Second, we study an application of this problem in structured wireless networks, where the overlap between pilot signals impacts channel estimation. Channel estimation is a critical aspect of wireless communications; thus, pilot contamination can significantly reduce the system capacity. We apply the multi-observer signal recovery framework in this setting, and develop algorithms for distributed channel estimation.

Third, we study an application to haplotype assembly, where the haplotype is sequence of (location, nucleotide) pairs in a chromosome that vary over the human population. Here, the underlying signal (halpotype) can be modeled to have binary support, and does not change in time. However, the information about signal -- multiple partially overlapping fragments (each fragment associated with a different virtual observer) -- is noisy and incomplete. We design fast sequence reconstruction algorithms.