I have the following problem:
where the matrix $A$ is large and sparse. I am looking for methods/code that can minimize this efficiently. References are very welcome.
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.Sign up to join this community
If you have a good LP solver, then the linear programming approach often works well. You don’t want to implement your own simplex or interior point code for LP though.
A specialized variant of the simplex method due to Barrodale and Roberts is a popular approach to this problem, but it takes some effort to implement this efficiently and you might be better off using a high-quality LP solver rather than writing your own implementation of Barrodale and Roberts.
There are other approaches
Iteratively Reweighted Least Squares (IRLS) is particularly easy to implement if you already have a least squares solver such as LSQR.
Subgradient descent methods are also quite easy to implement. If your matrix has far more rows than columns, then random sampling of the rows can produce an approximate subgradient that works well enough.