Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 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 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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