Find point in the image of a linear function that is closest to some other point

Solution 1:

The vector $x$ that you are looking for is known as the least squares solution to the equation $M \cdot x = p$. It turns out that there is a very straightforward solution to this problem. A vector $x$ is a least solution if and only if we have $$ M^TMx = M^Tp. $$ Thus, if the columns of $M$ are linearly independent, the (unique) solution is $$ x = (M^TM)^{-1}M^Tp. $$ If $M$ has linearly dependent columns, then the solution is no longer unique. If we want the vector $x$ among these solutions for which the Euclidean norm $\|x\|$ is minimized, then we could use the MP pseudoinverse $M^+$ of $M$ to get $$ x = M^+p. $$

Claim: If $x$ is a least squares solution to $Mx = p$, then $M^TMx = M^Tp$.

Proof: Let $x$ denote the least squares solution. As you note, the line connecting $Mx$ to $p$ must be perpendicular to the image of $f$. On the other hand, for $z \in \Bbb R^n$ $$ z^T My = 0 \quad \forall y \in \Bbb R^m \iff z^TM = 0 \iff (z^TM)^T = M^Tz = 0. $$ That is, a vector $z$ is orthogonal to the image of $f$ iff $M^Tz = 0$. Now, the vector $p - Mx$ points from $p$ to the closest point within the image of $f$, so this vector is orthogonal to the image of $f$. That is, we have $$ 0 = M^T(p - Mx) \implies 0 = M^Tp - M^TMx \implies M^TMx = M^Tp, $$ which was what we wanted.