Dissertation/Thesis Abstract

Iterative Algorithms for Inference and Optimization, with Applications in Communications and Compressed Sensing
by Rush, Cynthia, Ph.D., Yale University, 2016, 186; 10160875
Abstract (Summary)

This work studies the high-dimensional statistical linear regression model, Y=Xβ+ε, (1) for output Y ε[special characters omitted]n, design matrix X ε [special characters omitted]nxN, noise ε ε[special characters omitted]n, and unknown message β ε [special characters omitted]N. when N larger than the sample size n. The aim is to recover the message with knowledge of the output Y, the design X, and the distribution of the noise ε. In the high-dimensional setting, it is necessary that β have an underlying structure for successful recovery to be possible. We study this problem under two different assumptions on the distributional properties of the unknown message β motivated by practical applications.

The first application studied is communication over a noisy channel. We propose Approximate Message Passing, or AMP, as a fast decoding strategy for sparse regression codes, introduced by Barron and Joseph [1, 2]. We prove that this scheme is asymptotically capacity-achieving with error probabilities approaching zero in the large system limit and good empirical performance at practical block lengths.

In many applications, one wishes to study the model given in (1), when the only assumption made on the message β is that its entries are i.i.d. according to some prior distribution. In this case Approximate Message Passing, or AMP, has been proposed [3-7] as a fast, iterative algorithm to recover β. In [5] it is shown that the performance of AMP can be characterized in the large system limit, meaning as n, N → ∞ simultaneously, via a simple scalar iteration called state evolution . This dissertation analyzes the finite-sample performance of AMP, demonstrating that state evolution still accurately characterizes the algorithm's performance for practically-sized n.

Indexing (document details)
Advisor: Barron, Andrew
School: Yale University
School Location: United States -- Connecticut
Source: DAI-B 78/01(E), Dissertation Abstracts International
Subjects: Statistics, Electrical engineering
Keywords: Communications, Compressed Sensing, Information Theory
Publication Number: 10160875
ISBN: 978-1-369-15770-3
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy