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.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ It sounds like what you need is sparse SVD. Just search for those words, there are methods and libraries for it. $\endgroup$– Maxim UmanskyOct 8, 2020 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$– lightxbulbOct 8, 2020 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 UmanskyOct 8, 2020 at 19:03
-
1$\begingroup$ You can reformulate this as a linear program with the help of slack variables. $\endgroup$– Wolfgang BangerthOct 8, 2020 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$– lightxbulbOct 8, 2020 at 20:53
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
4
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.
answered Oct 9, 2020 at 1:35
-
$\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$ Oct 9, 2020 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$ Oct 9, 2020 at 9:08
-
$\begingroup$ Yes- I've fixed the spelling in the answer. $\endgroup$ Oct 9, 2020 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$ Oct 9, 2020 at 13:42
$\begingroup$
$\endgroup$
1
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$$
-
2$\begingroup$ You don't actually need the last constraint $y\ge 0$. It is implied by the two others. $\endgroup$ Oct 9, 2020 at 15:12