Below is the description of the problem that I'm stuck on:
Suppose the wide matrix A has linearly independent rows. Find an expression for the point x that is closest to a given vector y (i.e., minimizes ∥x − y∥^22) among all vectors that satisfy Ax = b.
Remark: This problem comes up when x is some set of inputs to be found, Ax = b represents some set of requirements, and y is some nominal value of the inputs. For example, when the inputs represent actions that are re-calculated each day (say, because b changes every day), y might be yesterday’s action, and the today’s action x found as above gives the least change from yesterday’s action, subject to meeting today’s requirements.
This is what I've been able to come up with so far:
A wide matrix is right invertible if and only if its rows are linearly independent. Since the rows of A are linearly independent, A is right invertible. Let B denote the right inverse of A. Then x = Bb satisfies Ax = b.
I don't know whether I'm on the right track, and I don't really know where to go from here. Any help would be appreciated-- thank you!
Assume matrix $A$ is $m \times n$ where $n \gt m$, and $b$ is $m \times 1$, and $x $ is $ n \times 1 $.
I am going to use the Lagrange multiplier method. Let
$J(x) = (x - y)^T (x - y) + \lambda^T (A x - b ) $
Taking the gradient of $J$ with respect to vector $x$
$\nabla_x J = 2 (x - y) + A^T \lambda = 0 \hspace{36pt} (1)$
Taking the gradient of $J$ with respect to vector $\lambda$
$ \nabla_\lambda J = A x - b = 0 \hspace{36pt} (2)$
From $(1)$
$ x = y - \dfrac{1}{2} A^T \lambda \hspace{36pt} (3)$
Substitute $(3)$ into $(2)$
$ A y - \dfrac{1}{2} A A^T \lambda - b = 0 \hspace{36pt} (4)$
Now the matrix $(A A^T) $ is invertible, therefore,
$\lambda = 2 (A A^T)^{-1} (A y - b) \hspace{36pt} (5)$
Substituting $(5)$ into $(3)$
$x = y - A^T (A A^T)^{-1} ( A y - b) = (I - A^T (A A^T)^{-1} A ) y + A^T (A A^T)^{-1} b \hspace{36pt}(6) $
Note that the minimum squared distance between $x$ and $y$ is
$\| x- y \|^2 = (A y - b)^T (A A^T)^{-1} (A y - b) $