I have an underdetermined linear system, with 3 equations and four unknows. I also know an initial guess for these 4 unknows. The article I am reading says: We can solve the system using the least squares method, starting form a guess. I don't know how can I do this. Thanks.

  • $\begingroup$ Can you post the system? $\endgroup$
    – AnilB
    May 1 '13 at 18:45
  • $\begingroup$ if there are three equations and four unknowns, there really is no need to do least squares. I don't think it even a valid approach since the columns of $A$ are definitely not independent, and least squares assumes that they are. $\endgroup$
    – Brad S.
    Mar 26 '14 at 4:20

Suppose your underdetermined system looks like this: $$Ax=y$$

The least squares solution can be determined using the Moore-Penrose pseudoinverse: $$x=A^T(AA^T)^{-1}y$$ where it is assumed that the inverse of $AA^T$ exists. Royi's answer discusses the case when $AA^T$ is singular.

In any case, you do not need an initial guess. The solution you'll get is the solution with the smallest norm of all possible solutions.

  • $\begingroup$ I am not sure why the downvote, but I suspect that it because the answer is not on point (although it may be true). Maybe it can be improved in this regard. Just trying to provide some helpful hints. Regards $\endgroup$
    – Amzoti
    May 1 '13 at 19:08
  • $\begingroup$ OK, thanks. I've added some info. If my answer is unclear or even wrong I guess (and hope) I'll get some comments instead of downvotes. :) $\endgroup$
    – Matt L.
    May 1 '13 at 19:13
  • $\begingroup$ The solution using the above works only in the case $ {\left( A {A}^{T} \right)}^{-1} $ is invertible. In other case one must use the SVD as I pointed below. $\endgroup$
    – Royi
    Jul 24 '18 at 10:25

@Matt L. solution is correct under the assumption $ A $ is full rank.

If it is otherwise, the solution using the SVD is always well defined which minimizes both the norm of the error and the norm of the solution.


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.