0
$\begingroup$

Is computing the 2-norm of a vector $x$, computed by setting $\alpha = \max_i x_i$ and then computing $|\alpha| \cdot ||x / \alpha ||_2$ (e.g., as in this link) numerically stable?

There are two parts which might be concerning numerically: you have to make $len(x)$ divisions by $\alpha$, and also take a square root. The sum is not concerning with Kahan's algorithm; all the summands are positive and the error induced there is machine epsilon.

$\endgroup$

2 Answers 2

2
$\begingroup$

The link says computing directly on a large vector could result in overflow in float64 type before taking the norm.

However, if the values in the vector vary wildly, e.g., there is a huge value and millions of small values, this will also destroy the answer because of the underflow.

$\endgroup$
2
  • $\begingroup$ Thanks for pointing that out. To your knowledge, is there a more numerically stable or accepted way of computing the 2-norm then? $\endgroup$
    – i901234
    Commented Dec 9, 2023 at 21:38
  • $\begingroup$ @i901234 If you can sort the values first, then there will be no issue after you split the values into large ones and small ones. Then aggregate each group with your mentioned scaling method. $\endgroup$
    – Yimin
    Commented Dec 9, 2023 at 22:40
1
$\begingroup$

It is stable but perhaps not accurate.

There is a decades-long series of papers that were published in ACM Transactions on Mathematical Software that describes algorithms for specifically this problem.

$\endgroup$
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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