Bidirectional Random Projections

This paper analyzes bidirectional random projections for ordinary least squares (OLS) regression under the fixed design setting. Let (X,Y) ∈ ℝn × p × ℝn be a sample and R ∈ ℝn1 × n, W ∈ ℝp × p1 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 Oleft( p1 + C frac1p1 right), where C scales with n1/n and can be negative for small n1/n. Its implications are confirmed by numerical results on real-world data.