2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It sounds like what you need is sparse SVD. Just search for those words, there are methods and libraries for it. $\endgroup$ – Maxim Umansky Oct 8 at 16:13
  • 1
    $\begingroup$ @MaximUmansky Could you elaborate how having the SVD would help solve this problem? Note that it is a L1 norm. $\endgroup$ – lightxbulb Oct 8 at 18:20
  • $\begingroup$ Ah, I missed that it is specifically the L1 norm that we need here. SVD solution would do the trick for L2. $\endgroup$ – Maxim Umansky Oct 8 at 19:03
  • 1
    $\begingroup$ You can reformulate this as a linear program with the help of slack variables. $\endgroup$ – Wolfgang Bangerth Oct 8 at 19:36
  • $\begingroup$ @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? $\endgroup$ – lightxbulb Oct 8 at 20:53
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lightxbulb Oct 9 at 8:57
  • $\begingroup$ I assume the "w" in Barrowdale was a typo, and that you meant that paper? epubs.siam.org/doi/abs/10.1137/0710069 $\endgroup$ – lightxbulb Oct 9 at 9:08
  • $\begingroup$ Yes- I've fixed the spelling in the answer. $\endgroup$ – Brian Borchers Oct 9 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Oct 9 at 13:42
2
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You don't actually need the last constraint $y\ge 0$. It is implied by the two others. $\endgroup$ – Wolfgang Bangerth Oct 9 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.