Paperlane

no. 17 · Wednesday 18 November 2026

Bidirectional Random Projections

Chao Lan and Luyuan Yang

math.ST · v2

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 $W \in \mathbb{R}^{n_1\times n}$, $R \in \mathbb{R}^{p\times p_1}$ be two random projections. We develop an expected excess loss bound for the OLS estimator built on $(WXR, WY)$, extending an established bound for the OLS estimator built on $(XR, Y)$. Our analysis shows that our bound is larger and the gap between the two bounds decays at a rate of approximately $O(1/n_1)$. These findings are confirmed by numerical results.

comments
v2: correct the sketching constant, update the bound interpretation and numerical results, release source code
fields
Statistics Theory
pdf ↗ page arXiv:2606.10377 ↗