A method of virtual displacements for the degenerate discrete $l\sb{1}$ approximation problem

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 {\vert{r_i}(X)\vert = } \sum\limits_{i = 1}^m {\vert({A_i},X) - {b_i}\vert}$$

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.