This paper addresses least-squares (LS) problems with uncertain data, where the coefficient matrices \(A\) and \(b\) are known but subject to bounded perturbations. The authors propose a method to minimize the worst-case residual error using second-order cone programming (SOCP) or semidefinite programming (SDP), achieving complexity comparable to one singular value decomposition of \(A\). The method can be interpreted as a Tikhonov regularization procedure, providing an exact bound on the robustness of the solution and a rigorous way to compute the regularization parameter. When the perturbations have a known structure, such as Toeplitz matrices, the problem can be solved in polynomial time using SDP. The paper also considers the case where \(A\) is a rational function of an unknown but bounded perturbed vector, showing how to minimize upper bounds on the optimal worst-case residual using SDP. Numerical examples, including robust identification and interpolation, are provided to illustrate the effectiveness of the proposed methods.This paper addresses least-squares (LS) problems with uncertain data, where the coefficient matrices \(A\) and \(b\) are known but subject to bounded perturbations. The authors propose a method to minimize the worst-case residual error using second-order cone programming (SOCP) or semidefinite programming (SDP), achieving complexity comparable to one singular value decomposition of \(A\). The method can be interpreted as a Tikhonov regularization procedure, providing an exact bound on the robustness of the solution and a rigorous way to compute the regularization parameter. When the perturbations have a known structure, such as Toeplitz matrices, the problem can be solved in polynomial time using SDP. The paper also considers the case where \(A\) is a rational function of an unknown but bounded perturbed vector, showing how to minimize upper bounds on the optimal worst-case residual using SDP. Numerical examples, including robust identification and interpolation, are provided to illustrate the effectiveness of the proposed methods.