Deromediqm

2022-07-22

Help in understanding properties of big O notation with norms of vectors
In Fast Exact Multiplication by the Hessian equation 1,
$O\left({‖\mathrm{\Delta }w‖}^{2}\right)$ gets taken from RHS to LHS and $\mathrm{\Delta }w$ is substituted as rv where r is small scalar and v is a vector. I understand that $O\left({‖rv‖}^{2}\right)=O\left({r}^{2}{‖v‖}^{2}\right)$. But what I don't get is how did the sign of O not become negative when it was taken to LHS. And why did ${‖v‖}^{2}$ disappear form O. Is it because as r is tiny it will govern the O term and ${‖v‖}^{2}$ won't matter?

Hassan Watkins

Expert

$O\left(f\left(x\right)\right)$ refers to a quantity that's bounded (in the limit) by some multiple of f(x); it properly (IMHO) represents a set. That is, to say that $g\left(x\right)\in O\left(f\left(x\right)\right)$ means that there's some constant C such that for all sufficiently large (or sufficiently small, depending on the direction of the limit) x, $|g\left(x\right)|. But this means in particular that O() is 'sign-agnostic'; if $g\left(x\right)\in O\left(f\left(x\right)\right)$, then $cg\left(x\right)\in O\left(f\left(x\right)\right)$ for all constants c, positive or negative. This same fact is also what 'removes' the dependency on ${‖v‖}^{2}$; because the limit that's implicit in O() is being taken with respect to r and v doesn't depend on r, the quantity ${‖v‖}^{2}$ is 'constant' and can be absorbed into the constant in O().

Hayley Bernard

Expert

When we write x=O(z), where x is some expression, and z is some other quantity, then we mean that x is a quantity such that $|x|\le Cz$ for some number C. If we have $x=y+O\left(z\right)$, then we really mean x−y=O(z) in the sense I just described. So x−y is equal to some quantity z′ such that $|{z}^{\prime }|\le Cz$. So we can say
$y=x+O\left(z\right)$
too, since $y-x=-{z}^{\prime }$, and $|\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}{z}^{\prime }|=|{z}^{\prime }|\le Cz$. So the minus sign does not need to be kept track of, and it's best to think of O(z) as meaning a quantity, whose absolute value is bounded by a constant times z.

Do you have a similar question?