1
$\begingroup$

Problem setting :

$ \underset{x}{\text{min}} \|Ax-b\|$, where $A \in \mathcal{R}^{m \times n}, m\gg n $, full rank.

L1 loss is used for robust estimation using IRLS. The corresponding equation to solve turns out to be $ A^{T}WAx=A^{T}Wb$, where $W=\mathrm{diag}(d_i), d_i=1/|e_{i}|$, $e_{i}=a_{i}^{T}x-b_{i}$, $a_{i}$ is the ith row of $A$, $b_{i}$ is the ith element of $b$. For $e_{i}$ close to $0$, the value of $d_{i}$ is very large. For my specific case, the range of $d_i$ is from $10^{-3}$ to $10^5$.

To avoid high values of $d_i$, it is taken as $d_i=1/(|e_i|+\delta)$ where $\delta>0$ is a small number near $0$. Let $\delta=10^{-3}$. This brings the range of $d_i$ as $10^{-3}$ to $10^3$. The range of values of $d_i$ is still high to bring numerical stability. It makes $ A^{T}WA$ a near singular matrix.

Please suggest a way to avoid numerical instability.

Thanks in advance!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You are essentially using normal equations to solve the least-squares problem $\min \|W^{1/2}(Ax-b)\|_2$ resulting from IRLS. Normal equations are known not to be a backward stable algorithm. Use other standard algorithms for LS problems instead, like the QR factorization or the SVD of $W^{1/2}A$ instead. Those are guaranteed to be backward stable.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for your answer. I'll update on this. For m>>n, e.g., m=10000, n=100, SVD computation of W^(1/2) * A will be expensive both in terms of memory and time taken when compared to A^T * W * A. Can you suggest any method to reduce the computation time? $\endgroup$
    – lalit
    Commented Dec 5, 2020 at 14:44
  • $\begingroup$ QR. Anyway, are you sure SVD is that expensive? It should be at most a factor 2 slower than A^TWA. $\endgroup$
    – Federico Poloni
    Commented Dec 5, 2020 at 14:47
  • $\begingroup$ The problem statement says L1 loss, not least squares (L2) loss. $\endgroup$
    – Mark L. Stone
    Commented Dec 5, 2020 at 17:35
  • $\begingroup$ @MarkL.Stone No, IRLS is an iterative method to solve a L1 loss problem in which a L2 problem is solved at each iteration. $\endgroup$
    – Federico Poloni
    Commented Dec 5, 2020 at 17:41
  • 1
    $\begingroup$ To add to @FedericoPoloni's excellent answer, there are loads of other ways of solving L1-type problems besides IRLS. Proximal algorithms, such as FISTA, are often very effective and quite simple to implement. $\endgroup$
    – Daniel Shapero
    Commented Dec 5, 2020 at 18:31
2
$\begingroup$

Why not solve this L1 norm minimization problem as a Linear Programming (LP) problem? Unless $A$ has non-zero elements many orders of magnitude from one, it should be easy to numerically solve reliably using an off the shelf LP solver.

Using the question's notation, $e_i = a_i^Tx-b_i$, introduce the variables $t_1,...,t_m$. Then

$\text{minimize}_{x,t_1,..,t_m} \Sigma_{i=1}^m t_t$

subject to

$e_i \le t_t,-e_i \le t_i, i=1,...,m$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .