Bidirectional Random Projections

This paper studies distributed sketching for ordinary least squares (OLS) regression, an approach that distributes small sketches of a large data set over multiple machines to separately construct OLS estimators and average them. Unlike prior studies that consider sketching on the whole data set, we consider sketching on partitioned subsets to further reduce computational cost. Under the fixed design setting, we characterize the exact excess loss of the averaged OLS estimator. Results show that this loss is comparable to the established loss for sketching on the whole data set when the divergence among subset covariances is small.

We consider the effect of Gaussian perturbations on least-squares residuals, orthogonal projections, and QR-type algorithms. The problem that motivated our investigations is as follows: suppose that a full column-rank matrix $B\in\mathbb{R}^{m\times n}$ has already been computed, and suppose that a new normalized column $q=(x+y)/\|x+y\|_2$ is to be appended to $B$, where $x\perp\operatorname{span}(B)$ is the ideal orthogonal component and $y$ represents the orthogonalization error. How large can the condition number $κ([B,q])$ of the resulting matrix $[B,q]$ become? While we provide a Weyl-type bound on the singular values of $[B,q]$, in terms of the extremal singular values of $B$ and the quantity $\|B^T y\|_2/\|x+y\|_2$, we also derive exact probability laws for norms and projection residuals under Gaussian perturbations. Finally, we use these probability laws to derive probabilistic condition-number bounds for QR-type processes with imperfect orthogonalization and exact normalization.

Regression estimates from observational data can depend on specification under multicollinearity, while sequential sums of squares (SS) depend on term order. We introduce Retrospective Orthogonal Design (ROD), which reconstructs conditional mean surfaces on a probability-balanced lattice. ROD preserves observed cell means, completes unsupported cells, applies weighted tensor-product contrasts, and evaluates the reconstructed surface through piecewise-affine interpolation over Freudenthal polyhedra. Resolution and completion are selected jointly by validation among rank-admissible candidates, followed by refitting and evaluation on an untouched test set. For an admissible lattice, $\mathbf{X}^{\top}\mathbf{W}\mathbf{X}=c\mathbf{I}$, yielding specification-invariant contrast effects and unique, order-independent SS within the retained contrast space. Response-free projection calibration maps the fixed reconstruction onto a declared scientific basis and corrects finite-resolution recovery loss. Across 6,480 simulation conditions spanning nine data-generating processes, ROD matched or exceeded polynomial regression in five processes and performed strongest on threshold, sign-interaction, and localized surfaces. For the quadratic-interaction process, mean out-of-sample $R^2$ differed by only $0.0001$, while calibrated coefficient bias remained small across prespecified targets. A Rao-based information adjustment provides dependence-aware sample-size guidance for ROD planning. In a weighted Mincer application, ROD produced the highest out-of-sample $R^2$ point estimate, with substantial interval overlap with polynomial regression, and provided exhaustive SS allocations invariant to term-entry order.