学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH UNCERTAIN DATA
免费下载此文档

ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH UNCERTAIN DATA

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

ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH UNCERTAIN DATA LAURENT EL GHAOUI y

AND HERVE LEBRET

y

Abstract. We consider least-squares problems where the coe cient matrices A; b are unknown-butbounded. 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 semide nite 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 identi cation and one from robust interpolation. Key Words. Least-squares, uncertainty, robustness, second-order cone programming, semide nite programming, ill-conditioned problem, regularization, robust identi cation, robust interpolation AMS(MOS) subject classi cation. 15A06, 65F10, 65F35, 65K10, 65Y20

Notation. For a matrix X, kX k denotes the largest singular value, and kX kF the Frobenius norm. If x is a vector, maxi jxij is denoted by kxk1. For a matrix A, Ay denotes the Moore-Penrose pseudo-inverse of A. For a square matrix S, S 0 (resp. S> 0) means S is symmetric, and positive semide nite (resp. de nite). For S 0, S 1=2 denotes the symmetric square root of S . For S> 0, and given vector x, we de ne kxkS= kS?1=2xk. The notation Ip denotes the p p identity matrix; sometimes the subscript is omitted when it can be inferred from context. For given matrices X; Y; the notation X Y refers to the block-diagonal matrix with X; Y as diagonal blocks. 1. Introduction. Consider the problem of nding a solution x to an overdetermined set of equations Ax ' b, where the data matrices A 2 Rn m, b 2 Rn are given. The Least Squares (LS) t minimizes the residual k bk subject to Ax= b+ b, result-

ing in a consistent linear model of the form (A; b+ b) that is closest to the original one (in Euclidean norm sense). The Total Least Squares (TLS) solution described by Golub and Van Loan 17] nds the smallest error k A b]kF subject to the consistency equation (A+ A)x= b+ b. The resulting closest consistent linear model (A+ A; b+ b) is even more accurate than the LS one, since modi cations of A are allowed. Accuracy is the primary aim of LS and TLS, so it is not surprising that both solutions may exhibit very sensitive behavior to perturbations in the data matrices (A; b). Detailed sensitivity analyses for the LS and TLS problems may be found in 12, 18, 2, 44, 22, 14]. Many regularization methods have been proposed to dey

(elghaoui, lebret)@ensta.fr

To appear in SIAM Journal on

Matrix Analysis and Applications, 1997. Ecole Nationale Superieure de Techniques Avancees, 32, Bd. Victor, 75739 Paris, France. Internet: 1

第1页

免费下载Word文档免费下载:ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH UNCERTAIN DATA

(下载1-34页,共34页)

我要评论

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部