This thesis deals with two approaches to building efficient representations of data. The first is a study of compressive sensing and improved data acquisition. We outline the development of the theory, and proceed into its uses in matrix completion problems via convex optimization. The aim of this research is to prove that a general class of measurement operators, bounded norm Parseval frames, satisfy the necessary conditions for random subsampling and reconstruction. We then demonstrate an example of this theory in solving 2-dimensional Fredholm integrals with partial measurements. This has large ramifications in improved acquisition of nuclear magnetic resonance spectra, for which we give several examples.

The second part of this thesis studies the Laplacian Eigenmaps (LE) algorithm and its uses in data fusion. In particular, we build a natural approximate inversion algorithm for LE embeddings using L1 regularization and MDS embedding techniques. We show how this inversion, combined with feature space rotation, leads to a novel form of data reconstruction and inpainting using a priori information. We demonstrate this method on hyperspectral imagery and LIDAR.

We also aim to understand and characterize the embeddings the LE algorithm gives. To this end, we characterize the order in which eigenvectors of a disjoint graph emerge and the support of those eigenvectors. We then extend this characterization to weakly connected graphs with clusters of differing sizes, utilizing the theory of invariant subspace perturbations and proving some novel results.