A New Look at Compressed Ordinary Least Squares

The prospect of carrying out data mining on cheaply compressed versions of high dimensional massive data sets holds tremendous potential and promise. However, our understanding of the performance guarantees available from such computationally inexpensive dimensionality reduction methods for data mining and machine learning tasks is currently lagging behind the requirements. In this paper we take a new look at randomly projected ordinary least squares regression, and give improved bounds on its expected excess risk. Our bounds are derived from first principles and use elementary techniques.