caa a22 4500 47575056X CHVBK 20180406123522.0 cr unu---uuuuu 170329e20001201xx s 000 0 eng 10.1023/A:1026562601717 doi (NATIONALLICENCE)springer-10.1023/A:1026562601717 Accurate Solution to Overdetermined Linear Equations with Errors Using L1 Norm Minimization [Elektronische Daten] [J. Rosen, Haesun Park, John Glick, Lei Zhang] It has been known for many years that a robust solution to an overdetermined system of linear equations Ax ≈ b is obtained by minimizing the L1 norm of the residual error. A correct solution x to the linear system can often be obtained in this way, in spite of large errors (outliers) in some elements of the (m × 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 ≥ 2k/σ, where σ > 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. Kluwer Academic Publishers, 2000 overdetermined linear systems nationallicence robust approximation nationallicence minimum error nationallicence zero error conditions nationallicence outliers nationallicence 1-norm nationallicence linear programming nationallicence Rosen J. Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut Park Haesun Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut Glick John Department of Mathematics and Computer Science, University of San Diego, 92110, San Diego, CA, USA aut Zhang Lei Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut Computational Optimization and Applications Kluwer Academic Publishers 17/2-3(2000-12-01), 329-341 0926-6003 17:2-3<329 2000 17 10589 https://doi.org/10.1023/A:1026562601717 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1026562601717 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Rosen J. Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut NATIONALLICENCE 700 1- Park Haesun Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut NATIONALLICENCE 700 1- Glick John Department of Mathematics and Computer Science, University of San Diego, 92110, San Diego, CA, USA aut NATIONALLICENCE 700 1- Zhang Lei Computer Science Department, University of Minnesota, 55455, Minneapolis, MN, USA aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 17/2-3(2000-12-01), 329-341 0926-6003 17:2-3<329 2000 17 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer