Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing

[摘要] In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k << d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly ;;local;; so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties.

[发布机构] Massachusetts Institute of Technology