Journal article
Robust Solutions to Least-Squares Problems with Uncertain Data
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.
Language: | Undetermined |
---|---|
Year: | 1997 |
Pages: | 1035-1064 |
ISSN: | 10957162 and 08954798 |
Types: | Journal article |
DOI: | 10.1137/S0895479896298130 |