  We study the problem of estimating an unknown deterministic signal that is
observed through an unknown deterministic data matrix under additive noise. In
particular, we present a minimax optimization framework to the least squares
problems, where the estimator has imperfect data matrix and output vector
information. We define the performance of an estimator relative to the
performance of the optimal least squares (LS) estimator tuned to the underlying
unknown data matrix and output vector, which is defined as the regret of the
estimator. We then introduce an efficient robust LS estimation approach that
minimizes this regret for the worst possible data matrix and output vector,
where we refrain from any structural assumptions on the data. We demonstrate
that minimizing this worst-case regret can be cast as a semi-definite
programming (SDP) problem. We then consider the regularized and structured LS
problems and present novel robust estimation methods by demonstrating that
these problems can also be cast as SDP problems. We illustrate the merits of
the proposed algorithms with respect to the well-known alternatives in the
literature through our simulations.
