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


$\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)$.

  • $\begingroup$ 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$. $\endgroup$ – jachilles Jan 18 '17 at 2:58
  • $\begingroup$ I think I made a mistake above. $\endgroup$ – user35593 Jan 19 '17 at 6:59
  • $\begingroup$ replaced the erroneous solution with a different one $\endgroup$ – Markus Sprecher Jan 23 '17 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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