Ordinary Least-Squares Problem
DefinitionThe Ordinary Least-Squares (OLS, or LS) problem is defined as ![]() where Note that the problem is equivalent to one where the norm is not squared. Taking the squares is done for convenience of the solution. InterpretationsInterpretation as projection on the rangeExamples: Interpretation as minimum distance to feasibilityThe OLS problem is usually applied to problems where the linear The OLS can be interpreted as finding the smallest (in Euclidean norm sense) perturbation of the right-hand side, ![]() becomes feasible. In this sense, the OLS formulation implicitly assumes that the data matrix Interpretation as regressionWe can also interpret the problem in terms of the rows of ![]() In this sense, we are trying to fit of each component of Examples: Solution via QR decomposition (full rank case)Assume that the matrix ![]() This can be seen by simply taking the gradient (vector of derivatives) of the objective function, which leads to the optimality condition We can also prove this via the QR decomposition of the matrix ![]() and exploiting the fact that ![]() Thus, to find the solution based on the QR decomposition, we just need to implement two steps:
In Matlab, the backslash operator finds the (unique) solution when Matlab syntax
>> x = A\y; Optimal solution and optimal setRecall that the optimal set of an minimization problem is its set of minimizers. For least-squares problems, the optimal set is an affine set, which reduces to a singleton when In the general case ( ![]() The formal expression for the set of minimizers to the least-squares problem can be found again via the QR decomposition. This is shown here. |