Answers are grounded in this paper and cite their sources.
A new algorithm is presented for computing a vector x which satisfies a given m by n(m > n 2) linear system in the sense that the l₁ norm is minimized. That is, if A is a matrix having m columns a₁ , ⋯ ,aₘ each of length n, and b is a vector with components β ₁ , ⋯ ,β ₘ, then x is selected so that \[φ (x) = ||A^T x - b||_1 = ∑ i = 1^m {|a_i^T x - β _i |} \] is as small as possible. Such solutions are of interest for the "robust" fitting of a linear model to data. The function φ 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 AZ stands for the submatrix consisting of those columns aⱼ from A for which the corresponding residuals aⱼT x - β ⱼ are zero, then the discontinuities in the gradient of φ at x are handled by making use of the projector onto the null space of AZT. Attention has been paid both to numerical stability and efficiency in maintaining and updating a factorization of AZ from which the necessary projector is obtainable. The algorithm compares favorably with the best so far reported for the linear l₁ problem, and it can easily be extended to handle linear constraints.
No takes yet. Share an insight, caveat, or question.
Bartels et al. (1978) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: