Robust Solutions to Least-Squares Problems with Uncertain Data

TLDR

The authors formulate robust least‑squares with bounded uncertainty as a convex second‑order cone program (and, when structure permits, as a semidefinite program), yielding an algorithm with complexity comparable to a single SVD that simultaneously provides an exact robustness bound and a principled regularization parameter. Numerical experiments on robust identification and interpolation confirm the effectiveness of the proposed convex optimization approach.

Abstract

We consider least-squares problems where the coefficient matrices A,b are unknown but bounded. We minimize the worst-case residual error using (convex) second-order cone programming, yielding an algorithm with complexity similar to one singular value decomposition of A. The method can be interpreted as a Tikhonov regularization procedure, with the advantage that it provides an exact bound on the robustness of solution and a rigorous way to compute the regularization parameter. When the perturbation has a known (e.g., Toeplitz) structure, the same problem can be solved in polynomial-time using semidefinite programming (SDP). We also consider the case when A,b are rational functions of an unknown-but-bounded perturbation vector. We show how to minimize (via SDP) upper bounds on the optimal worst-case residual. We provide numerical examples, including one from robust identification and one from robust interpolation.