Searching for a Best Least Absolute Deviations Solution of an Overdetermined System of Linear Equations Motivated by Searching for a Best Least Absolute Deviations Hyperplane on the Basis of Given Data

We consider the problem of searching for a best LAD‐solution of an overdetermined system of linear equations Xa=z, X∈ ℝ ^m×n , m≥n, $a\in {ℝ}^n,z\in {ℝ}^m$ . This problem is equivalent to the problem of determining a best LAD‐hyperplane x↦a ^T x, x∈ ℝ ⁿ on the basis of given data $(x_i,z_i),x_i=(x_1^{(i)},\dots ,x_n^{(i)}{)}^T\in {ℝ}^n,z_i\in ℝ,i=1,\dots ,m$ , whereby the minimizing functional is of the form $F(a)=\parallel z‐\mathrm{Xa}{\parallel }_1={\sum }_{i=1}^m\mid z_i‐a^T{x}_i\mid .$ An iterative procedure is constructed as a sequence of weighted median problems, which gives the solution in finitely many steps. A criterion of optimality follows from the fact that the minimizing functional F is convex, and therefore the point a ^*∈ ℝ ⁿ is the point of a global minimum of the functional F if and only if 0∈∂F(a ^*). Motivation for the construction of the algorithm was found in a geometrically visible algorithm for determining a best LAD‐plane (x,y)↦αx+βy, passing through the origin of the coordinate system, on the basis of the data (x i ,y i ,z i ),i=1,…,m.