Accurate solution to overdetermined linear equations with errors using \(L_1\) norm minimization
type: Item
instance of: scholarly article
title: Accurate solution to overdetermined linear equations with errors using \(L_1\) norm minimization
zbMATH Open document ID: 0972.47008
DOI: 10.1023/A:1026562601717
author: J. B. Rosen
author: Haesun Park
author: John Glick
author: Lei Zhang
published in: Computational Optimization and Applications
publication date: 2001-02-18T00:00:00Z
review text: From authors' introduction: It has been known for many years that a robust solution to an overdetermined system of linear equations \(Ax\approx b\) is obtained by minimizing the \(L_1\) norm of the residual error. A correct solution \(x\) to the linear system can often te obtained in this way, in spite of large errors (outliers) in some elements of the \((m\times n)\) matrix \(A\) and the data vector \(b\). This is in contrast to a least squares solution, where even one large error will typically cause a large error in \(x\). In this paper we give necessary and sufficient conditions that the correct solution is obtained when there are some errors in \(A\) and \(b\). Based on the sufficient condition, it is shown that if \(k\) rows of \([A b]\) contain large errors, the correct solution is guaranteed if \((m-n)/n\geq 2k/\sigma\), where \(\sigma>0\), is a lower bound of singular values related to \(A\). Since \(m\) typically represents the number of measurements, this inequality shows how many data points are needed to guarantee a correct solution in the presence of large errors in some of the data. This inequality is, in fact, an upper bound, and computational results are presented, which show that the correct solution will be obtained, with high probability, for much smaller values of \(m-n\).
reviewed by: Charles W. Groetsch
Mathematics Subject Classification ID: 47A50
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65F05
zbMATH DE Number: 1565506
zbMATH Keywords: overdetermined linear systems
zbMATH Keywords: robust approximation
zbMATH Keywords: minimum error
zbMATH Keywords: zero error conditions
zbMATH Keywords: outliers
zbMATH Keywords: 1-norm
zbMATH Keywords: linear programming
MaRDI profile type: Publication
full work available at URL: a:1026562601717
OpenAlex ID: W1601203987
description: scientific article; zbMATH DE number 1565506