Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections

In this work, we consider the deterministic optimization using random\nprojections as a statistical estimation problem, where the squared distance\nbetween the predictions from the estimator and the true solution is the error\nmetric. In approximately solving a large scale least squares problem using\nGaussian sketches, we show that the sketched solution has a conditional\nGaussian distribution with the true solution as its mean. Firstly, tight worst\ncase error lower bounds with explicit constants are derived for any estimator\nusing the Gaussian sketch, and the classical sketching is shown to be the\noptimal unbiased estimator. For biased estimators, the lower bound also\nincorporates prior knowledge about the true solution.\n Secondly, we use the James-Stein estimator to derive an improved estimator\nfor the least squares solution using the Gaussian sketch. An upper bound on the\nexpected error of this estimator is derived, which is smaller than the error of\nthe classical Gaussian sketch solution for any given data. The upper and lower\nbounds match when the SNR of the true solution is known to be small and the\ndata matrix is well conditioned. Empirically, this estimator achieves smaller\nerror on simulated and real datasets, and works for other common sketching\nmethods as well.\n