I have been studying linear observation models and least squares estimation and I came across this problem that requires some knowledge about linear algebra and vector spaces.

Let the observation model be $y=A\theta+v$ and $\hat{\theta}$ be some least squares solution. Then $S=\left\{ \theta=\hat{\theta}+\omega : \omega\in N(A) \right \}$ is the set of all LS-solutions.

I) prove that $\hat{\theta} \perp N(A) \Rightarrow$ ${\hat\theta}$ is the minimum norm solution.

II) let the observation model be $y_{i}=\theta_{1}x_{i}+\theta_{2}+v_{i}$, $1\leq i\leq n$ and let two observations be $(1,1)$ and $(2,1)$. Write the observation model in matrix form and prove that $S=\left\{ (\theta_{1},\theta_{2})\in\mathbb{R}^2 : \theta_{1}+\theta_{2}=\frac{3}{2} \right \}$ is the set of all LS-solutions.

III) Solve $N(A)$ and draw $S$ and $N(A)$ in $(\theta_{1},\theta_{2})$ coordinates. Use the picture to determine the minimum norm estimate in this case.

I) In this case the number of unknown parameters is $p=2$ and $A\in \mathbb{R}^{n\times2}$. I think $N(A)$ is referring to the null space of $A$ (i.e. the set $\{\tilde{x}\in\mathbb{R}^{2} :A\tilde{x}=0\}$ and $\omega$ represents the 'error term' in some sense. I was able to prove that $\hat{\theta}=(A^{T}A)^{-1}A^Ty$ is the mimimum norm solution by proving that $\hat{\theta}$ does minimize the norm of residual $\left \|r \right \|=\left \|y-A\hat{\theta} \right \|$. However, I don't think that's what the person who posed the question meant as I haven't actually used the fact that $\hat{\theta} \perp N(A)$. Basically, $H\hat\theta$ is the projection of $y$ into the range of $A$

II) This is a piece of cake. In matrix form

$\begin{bmatrix} y_{1}\\ y_{2}\\ \vdots \\ y_{n}\\ \end{bmatrix} = \begin{bmatrix} x_{1}& 1\\ x_{2}&1\\ \vdots\\x_{n}&1 \end{bmatrix} \begin{bmatrix} \theta_{1}\\\theta_{2}\\ \end{bmatrix}+\begin{bmatrix} v_{1}\\ \vdots \\ v_{n}\\ \end{bmatrix}$

Clearly we have overdetermined system of equations (more rows than columns). How would one prove that $S$ is the set of all LS-solutions? I am really bad at linear algebra, so this problem is giving me trouble. Now $A=\begin{bmatrix} 1& 1\\ 1&1\\\end{bmatrix}$,$y=\begin{bmatrix} 2\\ 1\\\end{bmatrix}$ and $A^TA$ is not invertible.


Lets consider a more general case where the columns of $A$ are not independent. We can then partion $A$ as $$A=\begin{bmatrix} A_1 && A_2 \end{bmatrix}$$ where $A_1$ is full column rank, and $A_2$ are linear combinations of the columns of $A_1$, so we can write:$$ A_2=A_1X$$ the Least squares solution can then be expressed as: $$\min_{\theta_1,\theta_2} \vert\vert \begin{bmatrix}A_1 && A_2 \end{bmatrix}\begin{bmatrix}\theta_1 \\ \theta_2\end{bmatrix}-y \vert\vert_2^2 = \min_{\theta_1,\theta_2} \vert\vert A_1(\theta_1+X\theta_2)-y \vert\vert_2^2$$ We introduce an auxillary variable $\zeta=\theta_1+X\theta_2 $ . Because in the minimization argument $A_1$ now has full collumn rank, the optimal solution for $\zeta$ is:$$\hat\zeta=\hat\theta_1+X\hat\theta_2 =(A_1^TA_1)^{-1}A_1^Ty $$ any value for $\theta_2$ fixes the value for $\theta_1$ at $\theta_1=\hat\zeta-X\theta_2$, showing that there are infinitely many solutions. So in III they impose another constraint upon $\theta$ to make in unique, i.e. $\min\vert\vert\theta\vert\vert^2_2$

Oh yeah, for 1. I think it could be usefull, to use the SVD of A to prove that $\hat\theta_{opt}\perp N(A)$ , because the SVD naturally shows the null spaces. If you need help with it, let me know.

  • $\begingroup$ I really think you should show this all the way through as a reference. $\endgroup$ – Royi May 25 '18 at 16:11

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.