Let $v \in \mathbb{R}^d$ be a vector, whose norm is upper bounded by $n$, and $\overline{v}$ an estimate of $v$ with some noise, such that $\|v- \overline{v}\| < \delta$.
I would like to have a bound on $\left\| vv^T - \overline{v}\overline{v}^T\right\|$.
Recall that $vv^T$ here means an outer product, so it forms a matrix $d \times d$. First, note that $\|vv^T\| = n^2$, and that we can express $\overline{v} = v + e$, where $e$ is a vector such that $\|e\| < \delta$.
From this, we can write:
$$\| vv^T - (v+e)(v+e)^T\| = \| vv^T - (v+e)(v^T+e^T)\| = \| vv^T - (vv^T+ve^T + ev^T+ee^T)\| $$
$$= \|- ve^T - ev^T - ee^T \| $$
From this we can conclude that $\| vv^T - \overline{v}\overline{v}^T \| < 2n\delta + \delta^2$.
Am I right? I have no intuition why an absolute bound of $\delta$ becomes relative (i.e. depends on $n$). I would rather expect it to depend on $d$! Thanks.
Yes your intuition is correct.
You just need to apply the Triangle Inequality to see this: \begin{align*} ||vv^T - \bar{v}\bar{v}^T|| &= ||-ve^T - ev^T - ee^T|| \\ &\color{red}{\leq} ||-ve^T|| + ||-ev^T|| + ||-ee^T|| \quad\color{red}{\text{ triangle inequality}} \\ &= ||ve^T|| + ||ev^T|| + ||ee^T|| \\ &\color{blue}{\leq} n\delta + \delta n + \delta^2 = 2n\delta + \delta^2 \end{align*}
The $\color{blue}{\text{last inequality}}$ results from directly applying the definition of a Matrix Norm.
To recap the norm of a real $p \times q$ matrix $A$ induced by the usual $\Bbb R^q$ vector norm is $$ ||A||_{p \times q} := \sup\{||Ax||_{q} : x \in \Bbb R^q, ||x||_{q} = 1\} $$ where I put subscripts to differentiate between the $p \times q$ matrix norm and the usual $\Bbb R^q$ vector norm.
So for example to bound the quantity $||ve^T||_{d \times d}$, we investigate the $\sup$ of all $||(ve^T)x||_d$ where $||x||_d = 1$. Note that $(ve^T)x = v(e^Tx)$ and $e^Tx$ is a scalar. So $$ ||(ve^T)x||_d = ||v(e^Tx)||_d = \color{red}{||v||_d}|e^Tx| \leq \color{red}{n}|e^Tx| \quad\color{red}{\text{ as $||v||_d \leq n$}} $$ Also $e^Tx$ is the inner product of $e$ and $x$ so by Cauchy-Schwarz $$ |e^Tx| \leq ||e||_d\color{blue}{||x||_d} = ||e||_d \cdot \color{blue}{1} < \delta \quad\color{blue}{\text{ as $||x||_q = 1$}} $$ Thus combining the two results we get $||(ve^T)x||_d < n\delta$ and since this upper bound $n \delta$ holds for all values $||(ve^T)x||_d $ with $||x||_d = 1$, taking the supremum over them gives $$ ||ve^T||_{d \times d} \leq n\delta $$ You can similarly find that $||ev^T||_{d \times d} \leq \delta n$ and $||ee^T||_{d \times d} \leq \delta^2$.