Robust Solutions to Least-Squares Problems with Uncertain Data

Robust Solutions to Least-Squares Problems with Uncertain Data. El Ghaoui, L. & Lebret, H. SIAM Journal on Matrix Analysis and Applications, 18(4):1035–1064, October, 1997.

Paper doi abstract bibtex

We consider least-squares problems where the coeﬃcient 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 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.

@article{el_ghaoui_robust_1997,
	title = {Robust {Solutions} to {Least}-{Squares} {Problems} with {Uncertain} {Data}},
	volume = {18},
	issn = {0895-4798, 1095-7162},
	url = {http://epubs.siam.org/doi/10.1137/S0895479896298130},
	doi = {10.1137/s0895479896298130},
	abstract = {We consider least-squares problems where the coeﬃcient 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 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.},
	language = {en},
	number = {4},
	urldate = {2022-02-08},
	journal = {SIAM Journal on Matrix Analysis and Applications},
	author = {El Ghaoui, Laurent and Lebret, Hervé},
	month = oct,
	year = {1997},
	keywords = {/unread},
	pages = {1035--1064},
}

Downloads: 0

{"_id":"9SKbxJ5aFvvKZrCHa","bibbaseid":"elghaoui-lebret-robustsolutionstoleastsquaresproblemswithuncertaindata-1997","author_short":["El Ghaoui, L.","Lebret, H."],"bibdata":{"bibtype":"article","type":"article","title":"Robust Solutions to Least-Squares Problems with Uncertain Data","volume":"18","issn":"0895-4798, 1095-7162","url":"http://epubs.siam.org/doi/10.1137/S0895479896298130","doi":"10.1137/s0895479896298130","abstract":"We consider least-squares problems where the coeﬃcient 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 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.","language":"en","number":"4","urldate":"2022-02-08","journal":"SIAM Journal on Matrix Analysis and Applications","author":[{"propositions":[],"lastnames":["El","Ghaoui"],"firstnames":["Laurent"],"suffixes":[]},{"propositions":[],"lastnames":["Lebret"],"firstnames":["Hervé"],"suffixes":[]}],"month":"October","year":"1997","keywords":"/unread","pages":"1035–1064","bibtex":"@article{el_ghaoui_robust_1997,\n\ttitle = {Robust {Solutions} to {Least}-{Squares} {Problems} with {Uncertain} {Data}},\n\tvolume = {18},\n\tissn = {0895-4798, 1095-7162},\n\turl = {http://epubs.siam.org/doi/10.1137/S0895479896298130},\n\tdoi = {10.1137/s0895479896298130},\n\tabstract = {We consider least-squares problems where the coeﬃcient 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 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.},\n\tlanguage = {en},\n\tnumber = {4},\n\turldate = {2022-02-08},\n\tjournal = {SIAM Journal on Matrix Analysis and Applications},\n\tauthor = {El Ghaoui, Laurent and Lebret, Hervé},\n\tmonth = oct,\n\tyear = {1997},\n\tkeywords = {/unread},\n\tpages = {1035--1064},\n}\n\n","author_short":["El Ghaoui, L.","Lebret, H."],"key":"el_ghaoui_robust_1997","id":"el_ghaoui_robust_1997","bibbaseid":"elghaoui-lebret-robustsolutionstoleastsquaresproblemswithuncertaindata-1997","role":"author","urls":{"Paper":"http://epubs.siam.org/doi/10.1137/S0895479896298130"},"keyword":["/unread"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"article","biburl":"https://bibbase.org/zotero/victorjhu","dataSources":["CmHEoydhafhbkXXt5"],"keywords":["/unread"],"search_terms":["robust","solutions","squares","problems","uncertain","data","el ghaoui","lebret"],"title":"Robust Solutions to Least-Squares Problems with Uncertain Data","year":1997}