Linear regression and model selection

Many of the sparse recovery algorithms we have described so far in this course were originally developed to address the problem of sparse linear regression and model selection in statistics. In this setting we are given some data consisting of a set of input variables and response variables. We will suppose that there are a total of $N$ input variables, and we observe a total of $M$ input and response pairs. We can represent the set of input variable observations as an $M\times N$ matrix $\Phi$ , and the set of response variable observations as an $M\times 1$ vector $y$ .

In linear regression, it is assumed that $y$ can be approximated as a linear function of the input variables, i.e., there exists an $x$ such that $y\approx \Phi x$ . However, when the number of input variables is large compared to the number of observations, i.e., $M\ll N$ , this becomes extremely challenging because we wish to estimate $N$ parameters from far fewer than $N$ observations. In general this would be impossible to overcome, but in practice it is common that only a few input variables are actually necessary to predict the response variable. In this case the $x$ that we wish to estimate is sparse, and we can apply all of the techniques that we have learned so far for sparse recovery to estimate $x$ . In this setting, not only does sparsity aid us in our goal of obtaining a regression, but it also performs model selection by identifying the most relevant variables in predicting the response.