Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear System

Abstract

A new algorithm is presented for computing a vector x which satisfies a given m by $n(m > n \geqq 2)$ linear system in the sense that the $l_1 $ norm is minimized. That is, if A is a matrix having m columns $a_1 , \cdots ,a_m $ each of length n, and b is a vector with components $\beta _1 , \cdots ,\beta _m $, then x is selected so that \[\phi (x) = ||A^T x - b||_1 = \sum _{i = 1}^m {\left|a_i^T x - \beta _i \right|} \] is as small as possible. Such solutions are of interest for the "robust" fitting of a linear model to data. The function $\phi $ is directly minimized in a finite number of steps using techniques borrowed from Conn's approach toward minimizing piecewise differentiable functions. In these techniques if x is any point and $A_\mathcal {Z} $ stands for the submatrix consisting of those columns $a_j$ from A for which the corresponding residuals $a_j^T x - \beta _j $ are zero, then the discontinuities in the gradient of $\phi $ at x are handled by making use of the projector onto the null space of $A_\mathcal {Z}^T $. Attention has been paid both to numerical stability and efficiency in maintaining and updating a factorization of $A_\mathcal{Z} $ from which the necessary projector is obtainable. The algorithm compares favorably with the best so far reported for the linear $l_1$ problem, and it can easily be extended to handle linear constraints.