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.
Keywords
MathematicsSemidefinite programmingBounded functionResidualCondition numberSingular value decompositionApplied mathematicsUpper and lower boundsConvex optimizationTikhonov regularizationMathematical optimizationSingular valueRegular polygonAlgorithmInverse problemMathematical analysisEigenvalues and eigenvectors
Affiliated Institutions
Related Publications
PENNON: A code for convex nonlinear and semidefinite programming
Abstract We introduce a computer program PENNON for the solution of problems of convex Nonlinear and Semidefinite Programming (NLP-SDP). The algorithm used in PENNON is a genera...
Asymptotics for lasso-type estimators
We consider the asymptotic behavior ofregression estimators that\nminimize the residual sum of squares plus a penalty proportional to\n$\\sum|\\beta_j|^{\\gamma}$. for some $\\g...
Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
The nuclear norm (sum of singular values) of a matrix is often used in convex heuristics for rank minimization problems in control, signal processing, and statistics. Such heuri...
Optimal Strategies and Minimax Lower Bounds for Online Convex Games
A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and...
Robust L₁ Norm Factorization in the Presence of Outliers and Missing Data by Alternative Convex Programming
Matrix factorization has many applications in computer vision. Singular value decomposition (SVD) is the standard algorithm for factorization. When there are outliers and missin...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 18
- Issue
- 4
- Pages
- 1035-1064
- Citations
- 1049
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1049
OpenAlex
Cite This
Laurent El Ghaoui,
Hervé Lebret
(1997).
Robust Solutions to Least-Squares Problems with Uncertain Data.
SIAM Journal on Matrix Analysis and Applications
, 18
(4)
, 1035-1064.
https://doi.org/10.1137/s0895479896298130
Identifiers
- DOI
- 10.1137/s0895479896298130