A method of virtual displacements for the degenerate discrete $l_{1}$ approximation problem

Abstract:

Given the system of equations \[ \sum \limits _{j = 1}^n {{a_{ij}}{x_j} = {b_i},\quad i = 1, \ldots ,m,} \] let ${A_i} = ({a_{i1}}, \ldots ,{a_{in}})$. It is known that if the matrix $A = ({a_{ij}})$ has rank $k \leqslant n$, then there is a point X which provides a minimum of \[ R(X) = \sum \limits _{i = 1}^m {|{r_i}(X)| = } \sum \limits _{i = 1}^m {|({A_i},X) - {b_i}|} \] such that ${r_i}(X) = 0$ for at least k values of the index i. If ${r_i}(X) = 0$ for exactly k values of the index i, the point or vertex is called ordinary, while if ${r_i}(X) = 0$ for more than k values of i, the vertex is termed degenerate. A necessary and sufficient condition to determine if X minimizes R is valid if X is an ordinary vertex but not if X is degenerate. A degeneracy at X can be removed by applying perturbations to an appropriate number of the ${b_i}$ so that X becomes an ordinary vertex of a modified problem. By noting that the test uses only values of the ${A_i}$, it is possible to avoid actual introduction of the perturbations to the ${b_i}$ with a resulting substantial improvement of the efficiency of the computation.