Technical Summary: Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions

Problem Statement

Randomized numerical linear algebra (RandNLA) employs random sketching techniques, such as random sampling and random projection, to reduce the computational cost of large-scale matrix problems. A fundamental tool in this domain is the random oblique projection $\tilde{P} = X(SX)^\dagger S$, induced by random sampling, which approximates the orthogonal projection $P = XX^\dagger$ onto the column space of a data matrix $X \in \mathbb{R}^{n \times p}$.

Existing analyses of subsampled least squares and fast low-rank approximation methods (like CUR decomposition) primarily rely on subspace embedding guarantees. These guarantees ensure that the sketched Gram matrix $\tilde{X}^\top \tilde{X}$ is close to the full Gram matrix $X^\top X$ with high probability. However, this paper argues that such guarantees are insufficient for characterizing the statistical bias of the resulting estimators. Because the Moore–Penrose pseudoinverse is a nonlinear operator, the condition $\mathbb{E}[\tilde{X}^\top \tilde{X}] = X^\top X$ (first-order moment matching) does not imply that the induced oblique projection is unbiased, i.e., $\mathbb{E}[\tilde{P}] \neq P$. This nonlinearity introduces a systematic statistical bias into downstream solutions, such as subsampled Ordinary Least Squares (OLS) and fast CUR decompositions, which has been overlooked by classical analyses.

Methodology

The authors develop a unified non-asymptotic theory for random oblique projections in high dimensions to precisely characterize and correct this bias.

1. Characterization of Bias: The paper establishes that standard random sampling schemes induce a systematic bias in the oblique projection. Unlike Gaussian random projections, where a simple scalar debiasing factor suffices, random sampling requires a more nuanced approach due to the non-uniform nature of the sampling distribution relative to leverage scores.
2. Debiasing Framework: The authors propose a principled debiasing strategy. They introduce a debiased sampling matrix $\check{S}$, constructed by rescaling the original sampling matrix $S$ with a diagonal matrix dependent on the leverage scores $\ell_i(X)$ and sampling probabilities $\pi_i$:
   $$\check{S} = \text{diag}\left\{ \sqrt{\frac{m\pi_{is}}{m\pi_{is} - \ell_{is}(X)}} \right\}_{s=1}^m \cdot S$$
   This construction is derived using refined leave-one-out and leave-two-out arguments to control the cross-interactions between sampled rows, extending techniques from recent random matrix theory (RMT) literature.
3. Application to OLS and CUR:
   • Subsampled OLS: The debiased projection is applied to the subsampled OLS estimator $\check{\beta} = (\check{S}X)^\dagger \check{S}y$. The authors derive sharp bias-variance characterizations for both classical and debiased estimators.
   • Fast CUR Decomposition: The framework is extended to the fast CUR decomposition, where the middle factor $U$ is estimated via sketching. A debiased estimator $\check{U}$ is proposed to correct the systematic bias in the approximation.

Key Contributions

The paper makes the following specific contributions:

1. Precise Non-Asymptotic Bias Characterization: Theorem 3.1 provides a precise characterization of the bias induced by random oblique projections under general random sampling schemes. It demonstrates that standard schemes generally induce a systematic statistical bias that is not captured by subspace embedding analyses.
2. Debiased Subsampled OLS:
   • Bias Lower Bound: Theorem 4.2 establishes a lower bound of $\Omega(p^2/m^2)$ for the bias of classical subsampled OLS under approximate leverage score sampling, showing that this bias cannot be corrected by a simple scalar rescaling.
   • Debiased Improvement: Theorem 4.4 shows that the proposed debiased estimator $\check{\beta}$ achieves a significantly smaller bias of order $\tilde{O}(\theta_{\max}^3 p^3/m^3)$ while maintaining a variance comparable to the classical solution.
   • Special Cases: The paper analyzes specific sampling schemes. It shows that for exact leverage score sampling and Subsampled Randomized Walsh–Hadamard Transform (SRHT), the bias is naturally small, and the proposed debiasing reduces to a simple scalar rescaling (or is unnecessary), whereas uniform sampling exhibits substantial bias that is effectively reduced by the debiasing framework.
3. Debiased Fast CUR: Theorem 4.8 and Theorem F.1 extend the bias-variance analysis to fast CUR decomposition, providing a debiased estimator with provably improved approximation accuracy.
4. Empirical Validation: Numerical experiments on the Million Song Dataset (MSD), Flight Delay dataset, CIFAR-10, and ImageNet validate the theoretical findings. The results confirm that debiasing significantly reduces bias (particularly for uniform sampling) without increasing variance, and that schemes like leverage score sampling and SRHT are nearly unbiased even without explicit debiasing.

Results

• Bias Reduction: The debiased approach consistently achieves a substantially smaller bias across uniform sampling, leverage score sampling, and SRHT compared to prior bounds. For uniform sampling, the bias is reduced from $\tilde{O}(p^2/m^2)$ to $\tilde{O}(p^3/m^3)$.
• Variance Preservation: The debiased estimators do not incur a larger variance than their classical counterparts. In fact, for many schemes, the variance remains dominated by the same leading-order term $\Delta(X)$.
• SRHT and Leverage Scores: The analysis reveals that widely used schemes like SRHT and approximate leverage score sampling are statistically suboptimal in general but exhibit bias levels close to the debiased optimum, explaining why they often perform well in practice without explicit correction.
• Computational Efficiency: The debiasing procedure involves only a diagonal rescaling of the sampling matrix, adding negligible computational overhead compared to the sketching and inversion steps.

Significance and Claims

The paper claims to address a critical gap in the statistical understanding of RandNLA. By moving beyond coarse subspace embedding guarantees to a fine-grained analysis of bias and variance, the authors reveal that nonlinear interactions between random sampling and pseudoinversion systematically bias solutions.

The significance of this work lies in:

1. Correcting Hidden Bias: It provides a mechanism to correct systematic biases that were previously uncharacterized, leading to more accurate statistical estimators in high-dimensional settings.
2. Refined Theory: It offers a refined non-asymptotic theory that distinguishes between sampling schemes (e.g., showing why uniform sampling is biased while SRHT is not), providing a more nuanced understanding than previous "one-size-fits-all" subspace embedding bounds.
3. Practical Improvement: The proposed debiasing framework is computationally efficient and yields provable improvements in approximation accuracy for both subsampled least squares and fast CUR decomposition, as validated by extensive experiments.

The authors conclude that their results highlight the need for bias-aware analysis in sketching-based algorithms and suggest that this perspective could be extended to other methods, such as sketch-and-solve Newton algorithms and randomized preconditioning, to further advance the statistical understanding of randomized numerical linear algebra.