## 2 Least Squares Problems  
For \(m\times n\) observation matrix \(C\), \(m\times 1\) vector of measurements \(y\)\(y\), the least squares estimate \(aa\) is the solution of  
\[\min_{\mathbf{\alpha}}\ \ (\mathbf{y}-C\mathbf{\alpha})^{\top}(\mathbf{y}-C\mathbf{\alpha}).\]  
The QR factorisation of \(C\) expresses \(C=QR\) as a product of an \(m\times m\) orthogonal matrix \(Q\) and an upper triangular matrix \(R\). If  
\[C=[Q_{1}\ Q_{2}]\left[\begin{array}{c}R_{1}\\ \mathbf{0}\end{array}\right]=Q_{1}R_{1},\]where \(Q_{1}\) is the submatrix constructed from the first \(n\) columns of \(Q\) and \(Q_{2}\) that is constructed from the remaining \(m-n\) columns, then  
\[\mathbf{a}=(C^{\top}C)^{-1}C^{\top}\mathbf{y}=R_{1}^{-1}Q_{1}^{\top}\mathbf{y},\]  
\[\mathbf{\hat{y}}=C\mathbf{a}=C(C^{\top}C)^{-1}C^{\top}\mathbf{y}=Q_{1}Q_{1}^{\top}\mathbf{y},\]  
\[\mathbf{r}=\mathbf{y}-C\mathbf{a}=(I-Q_{1}Q_{1}^{\top})\mathbf{y}=Q_{2}Q_{2}^{\top}\mathbf{y},\]  
are the least squares solution, model approximant, and associated residual vector. The QR factorisation enables \(\mathbf{a}\) to be given by the solution of \(R_{1}\mathbf{a}=Q_{1}^{\top}\mathbf{y}\) and this solution can be constructed using back substitution, solving for \(a_{n}\) first, then \(a_{n-1}\), etc., exploiting the upper-triangular form of \(R_{1}\). The QR factorisation also avoids the numerical loss of accuracy that can occur in forming \(C^{\top}C\) and its inverse in the case in which \(C\) is ill-conditioned (Chapters, 2016) (Chapter 5). The computational cost of evaluation the least-squares solution in \(O(mn^{2})\).  
The \(n\times m\) matrix \(S=R_{1}^{-1}Q_{1}^{\top}\) is the sensitivity matrix of the solution parameters \(\mathbf{a}\) with respect to the data \(\mathbf{y}\) with \(s_{ji}=\partial a_{j}/\partial y_{i}\). If the variance matrix associated with \(\mathbf{y}\) is \(V_{\mathbf{y}}\), then the variance matrix associated with the solution \(\mathbf{a}\) is  
\[V_{\mathbf{a}}=SV_{\mathbf{y}}S^{\top}.\]  
For the case \(V_{\mathbf{y}}=I\),  
\[V_{\mathbf{a}}=SS^{\top}=(R_{1}^{\top}R_{1})^{-1}=(C^{\top}C)^{-1}.\]  
For this case, the trace of the variance matrix is given by  
\[\text{Tr}(V_{\mathbf{a}})=\sum_{j}\sum_{i}s_{ji}^{2},\]  
the variance associated with \(a_{j}\) is \(u^{2}(a_{j})=\sum_{i}s_{ji}^{2}\) and \(\sum_{j}s_{ji}^{2}\) is the contribution of the uncertainty associated with the \(i\)th observation to the trace of \(V_{\mathbf{a}}\).  
The least-squares solution \(\mathbf{a}\) is the maximum likelihood estimate of \(\mathbf{a}\) for the model \(\mathbf{y}\in\mathcal{N}(C\mathbf{a},I)\). If \(\mathbf{y}\) is associated with the variance matrix \(V_{\mathbf{y}}\), i.e., \(\mathbf{y}\in\mathcal{N}(C\mathbf{a},V_{\mathbf{y}})\), and \(V_{\mathbf{y}}\) is full rank and has Cholesky decomposition \(V_{\mathbf{y}}=LL^{\top}\), where \(L\) is lower triangular ([PERSON], 2016), then the maximum likelihood estimate \(\mathbf{a}\) of \(\mathbf{a}\) solves the Gauss-Markov problem  
\[\min_{\mathbf{\alpha}}(\mathbf{y}-C\mathbf{\alpha})^{\top}V_{\mathbf{y}}^{-1}(\mathbf{y}-C\mathbf{ \alpha}). \tag{3}\]  
If  
\[\tilde{C}=L^{-1}C,\quad\tilde{\mathbf{y}}=L^{-1}\mathbf{y},\]  
then the solution of (3) is the least-squares solution of \(\tilde{C}\mathbf{\alpha}\approx\tilde{\mathbf{y}}\):  
\[\mathbf{a}=\left(\tilde{C}^{\top}\tilde{C}\right)^{-1}\tilde{C}^{\top}\tilde{\mathbf{ y}}.\]  
In particular, if \(V_{\mathbf{y}}\) is a diagonal matrix with \(u_{i}^{2}>0\) in the \(i\)th diagonal element, then \(\tilde{C}\) is constructed from the weighted rows of \(C\), and similarly for \(\tilde{\mathbf{y}}\):  
\[\tilde{\mathbf{c}}_{i}=w_{i}\mathbf{c}_{i},\quad\tilde{y}_{i}=w_{i}y_{i},\quad w_{i}= 1/u_{i}.\]  
In general, the cost of evaluating the Cholesky factorisation of \(V_{\mathbf{y}}\) is \(O(m^{3})\), which could be problematic for large \(m\). Often, \(V_{\mathbf{y}}\) has a structure that enables the factorisation to be performed in \(O(m)\), as in the simple but common case of a diagonal variance matrix.