Accurate solution to overdetermined linear equations with errors using \(L_1\) norm minimization (Q1841564)

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\).