# 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

2
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 Narain 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

## 1 Answer

Intuitively, the statement is obvious. Here is a proof.

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 38, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9340890049934387, "perplexity_flag": "head"}