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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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