2
$\begingroup$

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.

  • 0
    Good point; I've reworded the question to allow the function $f$ to depend on the $v_i$.2011-09-27

1 Answers 1

2

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

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