Robust Partially-Compressed Least-Squares
  Randomized matrix compression techniques, such as the Johnson-Lindenstrauss
transform, have emerged as an effective and practical way for solving
large-scale problems efficiently. With a focus on computational efficiency,
however, forsaking solutions quality and accuracy becomes the trade-off. In
this paper, we investigate compressed least-squares problems and propose new
models and algorithms that address the issue of error and noise introduced by
compression. While maintaining computational efficiency, our models provide
robust solutions that are more accurate--relative to solutions of uncompressed
least-squares--than those of classical compressed variants. We introduce tools
from robust optimization together with a form of partial compression to improve
the error-time trade-offs of compressed least-squares solvers. We develop an
efficient solution algorithm for our Robust Partially-Compressed (RPC) model
based on a reduction to a one-dimensional search. We also derive the first
approximation error bounds for Partially-Compressed least-squares solutions.
Empirical results comparing numerous alternatives suggest that robust and
partially compressed solutions are effectively insulated against aggressive
randomized transforms.
