Dealing with the multiplicity of solutions of the ℓ1 and ℓ∞ regression models

It is well known that the least absolute value (ℓ∞) and the least sum of absolute deviations (ℓ1) algorithms produce estimators that are not necessarily unique. In this paper it is shown how the set of all solutions of the ℓ1 and ℓ∞ regression problems for moderately large sample sizes can be obtained. In addition, if the multiplicity of solutions wants to be avoided, two new methods giving the same optimal ℓ1 and ℓ∞ values, but supplying unique solutions, are proposed. The idea consists of using two steps: in the first step the optimal values of the ℓ1 and ℓ∞ errors are calculated, and in the second step, in case of non-uniqueness of solutions, one of the multiple solutions is selected according to a different criterion. For the ℓ∞ the procedure is used sequentially but removing, in each iteration, the data points with maximum absolute residual and adding the corresponding constraints for keeping these residuals, and this process is repeated until no change in the solution is obtained. In this way not only the maximum absolute residual values are minimized in the modified method, but also the maximum absolute residual values of the remaining points sequentially, until no further improvement is possible. In the ℓ1 case a least squares criterion is used but restricted to the ℓ1 residual condition. Thus, in the modified ℓ1 method not only the ℓ1 residual is minimized, but also the sum of squared residuals subject to the ℓ1 residual. The methods are illustrated by their application to some well known examples and their performances are tested by some simulations, which show that the lack of uniqueness problem cannot be corrected for some experimental designs by increasing the sample size.