# L1 least squares minimization with a sparse matrix

I have the following problem:

$$\min_{x\in \mathbb{R}^n}\|Ax-b\|_1$$

where the matrix $$A$$ is large and sparse. I am looking for methods/code that can minimize this efficiently. References are very welcome.

• It sounds like what you need is sparse SVD. Just search for those words, there are methods and libraries for it. Oct 8 '20 at 16:13
• @MaximUmansky Could you elaborate how having the SVD would help solve this problem? Note that it is a L1 norm. Oct 8 '20 at 18:20
• Ah, I missed that it is specifically the L1 norm that we need here. SVD solution would do the trick for L2. Oct 8 '20 at 19:03
• You can reformulate this as a linear program with the help of slack variables. Oct 8 '20 at 19:36
• @WolfgangBangerth Thank you for mentioning that it can be reformulated as a linear program, I have done so in the answer. Do you have any recommendations for libraries (C/C++) that can solve such LP problems with sparse matrices? Or easy to implement such methods? Oct 8 '20 at 20:53

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.

• I will definitely try IRLS since I already solve least squares problems quite efficiently with the conjugate gradient method. As far as my matrix goes, at the moment I am working with a very sparse square matrix. Also why do you suggest not implementing IPM? Is the code complexity high for it to work well? Oct 9 '20 at 8:57
• I assume the "w" in Barrowdale was a typo, and that you meant that paper? epubs.siam.org/doi/abs/10.1137/0710069 Oct 9 '20 at 9:08
• Yes- I've fixed the spelling in the answer. Oct 9 '20 at 13:34
• A good interior point code will be a little less complex than a good simplex code (I've written a research level interior point solver for LP), but not by much. Look at the COIN-OR package clp (which implements both simplex and interior point methods) to see how much complexity we're talking about. Oct 9 '20 at 13:42

Thanks to Wolfgang Bangerth for pointing out that this can be rewritten as a linear problem. My reformulation would be:

$$\min_{x\in\mathbb{R}^N}\|Ax-b\|_1 \implies$$ $$\min_{(x,y)\in\mathbb{R}^{N+M}}\sum_{i=1}^N y_i,$$ $$Ax - y \leq b$$ $$-(Ax+y) \leq -b$$ $$y\geq0$$

• You don't actually need the last constraint $y\ge 0$. It is implied by the two others. Oct 9 '20 at 15:12