# Inequality on outer product

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.

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$$.