# A quantitative orthogonality argument

Let $S={\rm span}(v_1,\ldots,v_k)$ be a subspace of $R^n$, and let $P_S$ be the orthogonal projection matrix onto $S$. If for some $x$ we have $x^T v_i = 0$ for all $i=1,\ldots,k$, then we can conclude that $P_S x=0$.

I would like a quantitative version of this statement which I'll now describe. Suppose that instead we just know that $|x^T v_i| \leq \epsilon$ for all $i=1,\ldots,k$; and moreover $||x||_2=1$, $||v_i||_2=1$ for all $i=1,\ldots,k$. I'd like an argument that concludes $||P_S x||_2 \leq f(\epsilon, v_1, \ldots, v_n)$ where $f(\epsilon, v_1, \ldots, v_n)$ is some function which approaches $0$ as $\epsilon \rightarrow 0$ and the other arguments are kept fixed. Naturally, the faster rate of decay as $\epsilon \rightarrow 0$, the better.

-
There are many projection matrices onto a given subspace. Is $P_S$ the orthogonal projection onto $S$? –  robjohn Sep 27 '11 at 2:28
Yes; thanks - I edited this into the question. –  robinson Sep 27 '11 at 3:08
You're going to need additional assumptions on how close the $v_i$ are allowed to be to each other. Otherwise, you could have $v_1 = (1,0,0)$, $v_2 = (\sqrt{1-\epsilon^2},\epsilon,0)$, and $x = (0,1,0)$ with $\lVert P_S x\rVert_2 = 1$. –  Rahul Sep 27 '11 at 4:00
Good point; I've reworded the question to allow the function $f$ to depend on the $v_i$. –  robinson Sep 27 '11 at 5:30

Let $A=(v_1,v_2,...,v_k)\in\mathbb{R}^{n\times k}$. Then the orthogonal projection matrix $P_S$ is $$P_S=A(A^TA)^{-1}A^T\in\mathbb{R}^{n\times n}$$
Denote $y=A^Tx\in\mathbb{R}^k$. Then $|v_i^Tx|<\epsilon$ implies $|y_i|<\epsilon$ and $$\|y\|^2<k\epsilon^2$$
Moreover, $$\|P_Sx\|^2=x^TP_Sx=y^T(A^TA)^{-1}y$$ Let $(A^TA)^{-1}=U^T\Sigma U$ be an SVD of $(A^TA)^{-1}$ with $\Sigma=\mathrm{diag}(\sigma_1,...,\sigma_k)$. Denote $z=Uy$. Then $$\|P_Sx\|^2=y^T(A^TA)^{-1}y=z^T\Sigma z=\sum_{i=1}^k \sigma_i z_i^2\le \sigma_1\sum_{i=1}^k z_i^2=\sigma_1\|z\|^2=\sigma_1\|Uy\|^2=\sigma_1\|y\|^2<\sigma_1k\epsilon^2$$ where $\sigma_1$ is the largest singular value of $(A^TA)^{-1}$.