High-dimensional regression with random design, including sparse superposition codes

The dissertation studies variable selection for a linear regression model. We focus on high-dimensional setting where the number of explanatory variables is much greater than the number of observations. For the independent variables, we assume a random design.;The first chapter of the dissertation evaluates the performance of an out-of-sample prediction estimator when the complexity of candidate models is controlled relative to the sample size. We refine an upperbound to a tail probability for the distance between the out-of-sample prediction and its estimate in Lech (2008) in order to deal with models of varying complexity relative to the sample size. We construct a. modified model selection criterion that will allow us to guarantee the performance over a large class of candidate models.;The second chapter of the dissertation is an application of variable selection to the mathematical theory of communication We focus on a problem of high rate sparse superposition codes (sparse regression codes) for the additive white Gaussian noise channel with a power control. This problem can be interpreted as a variable selection with a special structure of the sparse coefficient vector beta. We propose a fast and reliable algorithm of iterative updates for estimating the coefficient vector motivated by Bayes optimal estimates.