error bound for least square minimization

Let $X = [x_1 \cdots x_N] \in \mathbb{R}^{d \times N}$ and $T= [t_1 \cdots t_N] \in \mathbb{R}^{1 \times N}$. Define $$E(w) = \text{tr}(T - w^TX)(T - w^TX)^T$$ as least square energy. When defining $$\epsilon = T- w_{LS}^T X,$$ with $w_{LS}^T$ being the solution that minimizes $E$, can we find a simple bound for $\epsilon$ in terms of $X$ and $T$ without involving inverse operation? And additionally, can I get a bound (needs to be as small as possible) for each $\epsilon_i$ whereas $\epsilon = [\epsilon_1 \cdots \epsilon_N]$?

In addition to the above, regarding the vectors mentioned above as random ones, would there be any way to impose more conditions on the above to derive that $$\epsilon_i \sim \mathcal{N}(0,I/\sigma^2)$$ with $0<\sigma<<1$.

1 Answer

$\epsilon$ is the orthogonal projection of $T$ onto the orthogonal complement of the space spanned by the rows of $X$. Hence we have $$\|\epsilon\|_\infty=\frac{\|\epsilon\|_\infty}{\|T\|_\infty}\|T\|_\infty \leq \sup_{(u,v)=0,u,v\neq 0} \frac{\|u\|_\infty}{\|u+v\|_\infty} \|T\|_\infty\leq \frac{\sqrt{N}+1}{2}\|T\|_\infty.$$ Here we have used that the supremum is attained at

$u=\left(\frac{\sqrt{N}+1}{2},\frac{1}{2},\dots,\frac{1}{2}\right)$ and $v=\left(\frac{-\sqrt{N}+1}{2},\frac{1}{2},\dots,\frac{1}{2}\right)$.

Regarding the probability distribution: if $X$ is fix and the entries of $T$ are independent and have standard distribution $t_1,\dots,t_N$ then the covariance matrix of the $\epsilon's$ is given by $C_{ij}=(I-X^T(XX^T)^{-1}X)_{ij}t_it_j$. You can derive this from the explicit formula $\epsilon=T\left(I-X^T(XX^T)^{-1}X \right)$.

• Thank you very much for your simple and nice answer. The thing is I need a way smaller bound. I actually need bound for each $\epsilon_i$. – jachilles Jan 18 '17 at 2:58
• I think I made a mistake above. – user35593 Jan 19 '17 at 6:59
• replaced the erroneous solution with a different one – Markus Sprecher Jan 23 '17 at 18:15