1*bf2c3715SXin Linamespace Eigen { 2*bf2c3715SXin Li 3*bf2c3715SXin Li/** \eigenManualPage LeastSquares Solving linear least squares systems 4*bf2c3715SXin Li 5*bf2c3715SXin LiThis page describes how to solve linear least squares systems using %Eigen. An overdetermined system 6*bf2c3715SXin Liof equations, say \a Ax = \a b, has no solutions. In this case, it makes sense to search for the 7*bf2c3715SXin Livector \a x which is closest to being a solution, in the sense that the difference \a Ax - \a b is 8*bf2c3715SXin Lias small as possible. This \a x is called the least square solution (if the Euclidean norm is used). 9*bf2c3715SXin Li 10*bf2c3715SXin LiThe three methods discussed on this page are the SVD decomposition, the QR decomposition and normal 11*bf2c3715SXin Liequations. Of these, the SVD decomposition is generally the most accurate but the slowest, normal 12*bf2c3715SXin Liequations is the fastest but least accurate, and the QR decomposition is in between. 13*bf2c3715SXin Li 14*bf2c3715SXin Li\eigenAutoToc 15*bf2c3715SXin Li 16*bf2c3715SXin Li 17*bf2c3715SXin Li\section LeastSquaresSVD Using the SVD decomposition 18*bf2c3715SXin Li 19*bf2c3715SXin LiThe \link BDCSVD::solve() solve() \endlink method in the BDCSVD class can be directly used to 20*bf2c3715SXin Lisolve linear squares systems. It is not enough to compute only the singular values (the default for 21*bf2c3715SXin Lithis class); you also need the singular vectors but the thin SVD decomposition suffices for 22*bf2c3715SXin Licomputing least squares solutions: 23*bf2c3715SXin Li 24*bf2c3715SXin Li<table class="example"> 25*bf2c3715SXin Li<tr><th>Example:</th><th>Output:</th></tr> 26*bf2c3715SXin Li<tr> 27*bf2c3715SXin Li <td>\include TutorialLinAlgSVDSolve.cpp </td> 28*bf2c3715SXin Li <td>\verbinclude TutorialLinAlgSVDSolve.out </td> 29*bf2c3715SXin Li</tr> 30*bf2c3715SXin Li</table> 31*bf2c3715SXin Li 32*bf2c3715SXin LiThis is example from the page \link TutorialLinearAlgebra Linear algebra and decompositions \endlink. 33*bf2c3715SXin LiIf you just need to solve the least squares problem, but are not interested in the SVD per se, a 34*bf2c3715SXin Lifaster alternative method is CompleteOrthogonalDecomposition. 35*bf2c3715SXin Li 36*bf2c3715SXin Li 37*bf2c3715SXin Li\section LeastSquaresQR Using the QR decomposition 38*bf2c3715SXin Li 39*bf2c3715SXin LiThe solve() method in QR decomposition classes also computes the least squares solution. There are 40*bf2c3715SXin Lithree QR decomposition classes: HouseholderQR (no pivoting, fast but unstable if your matrix is 41*bf2c3715SXin Linot rull rank), ColPivHouseholderQR (column pivoting, thus a bit slower but more stable) and 42*bf2c3715SXin LiFullPivHouseholderQR (full pivoting, so slowest and slightly more stable than ColPivHouseholderQR). 43*bf2c3715SXin LiHere is an example with column pivoting: 44*bf2c3715SXin Li 45*bf2c3715SXin Li<table class="example"> 46*bf2c3715SXin Li<tr><th>Example:</th><th>Output:</th></tr> 47*bf2c3715SXin Li<tr> 48*bf2c3715SXin Li <td>\include LeastSquaresQR.cpp </td> 49*bf2c3715SXin Li <td>\verbinclude LeastSquaresQR.out </td> 50*bf2c3715SXin Li</tr> 51*bf2c3715SXin Li</table> 52*bf2c3715SXin Li 53*bf2c3715SXin Li 54*bf2c3715SXin Li\section LeastSquaresNormalEquations Using normal equations 55*bf2c3715SXin Li 56*bf2c3715SXin LiFinding the least squares solution of \a Ax = \a b is equivalent to solving the normal equation 57*bf2c3715SXin Li<i>A</i><sup>T</sup><i>Ax</i> = <i>A</i><sup>T</sup><i>b</i>. This leads to the following code 58*bf2c3715SXin Li 59*bf2c3715SXin Li<table class="example"> 60*bf2c3715SXin Li<tr><th>Example:</th><th>Output:</th></tr> 61*bf2c3715SXin Li<tr> 62*bf2c3715SXin Li <td>\include LeastSquaresNormalEquations.cpp </td> 63*bf2c3715SXin Li <td>\verbinclude LeastSquaresNormalEquations.out </td> 64*bf2c3715SXin Li</tr> 65*bf2c3715SXin Li</table> 66*bf2c3715SXin Li 67*bf2c3715SXin LiThis method is usually the fastest, especially when \a A is "tall and skinny". However, if the 68*bf2c3715SXin Limatrix \a A is even mildly ill-conditioned, this is not a good method, because the condition number 69*bf2c3715SXin Liof <i>A</i><sup>T</sup><i>A</i> is the square of the condition number of \a A. This means that you 70*bf2c3715SXin Lilose roughly twice as many digits of accuracy using the normal equation, compared to the more stable 71*bf2c3715SXin Limethods mentioned above. 72*bf2c3715SXin Li 73*bf2c3715SXin Li*/ 74*bf2c3715SXin Li 75*bf2c3715SXin Li}