Bidirectional Random Projections

Abstract

This paper analyzes bidirectional random projections for ordinary least squares (OLS) regression under the fixed design setting. Let $(X,Y)\in {\mathbb{R}}^{n\times p}\times {\mathbb{R}}^n$ be a sample and $R\in {\mathbb{R}}^{n_1\times n},W\in {\mathbb{R}}^{p\times p_1}$ be two properly distributed random projections. We develop an expected excess loss bound for the OLS estimator built on $(WXR,WY)$. Compared to an established bound for OLS estimator built on $(XR,Y)$, the gap is approximately $O\left(p_1+C\frac{1}{p_1}\right)$, where $C$ scales with $n_1/n$ and can be negative for small $n_1/n$. Its implications are confirmed by numerical results on real-world data.

Statistics & Probability Letters (Elsevier)