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, \(\mathbf{a}\in \mathbb{R}^{n}, \mathbf {z}\in\mathbb{R}^{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 \((\mathbf{x}_{i},z_{i}), \mathbf{x}_{i}= (x_{1}^{(i)},\ldots,x_{n}^{(i)})^{T}\in \mathbb{R}^{n}, z_{i}\in\mathbb{R}, i=1,\ldots,m\), whereby the minimizing functional is of the form

$F(\mathbf{a})=\|\mathbf{z}-\mathbf{Xa}\|_1=\sum_{i=1}^m|z_i-\mathbf {a}^T\mathbf{x}_i|.$

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.