Underdetermined Linear Systems and the Least Squares Solution

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.

@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.