Gradient descent to find closest solution to non-intersecting system of equations

Question

I'm trying to do gradient descent to approximate the point that minimizes the error for a system of $N+k$ equations with $N$ variables, for large values of $N$ and $k$. We're trying to minimize the value of $||Ax - B||^2$, where $A$ is the coefficient matrix with dimensions $[(N + k), N]$, $x$ is the coordinate vector with $N$ entries, and $B$ is the solution vector with $N + k$ entries. Geometrically, this would be the point that minimizes the total distance from some given $3 + k$ planes, for the case $N = 3$. I've looked into the conjugate gradient method, but can't figure out how to amend the algorithm for the additional $k$ equations. The residual vector has $N + k$ entries, while the guesses and search directions should only have $N$ entries, and conjugate gradient assumes they are the same size. I've thought of finding all $N + k\choose N$ intersections and averaging those points, unsure if that would work or if there's a simpler way.

Answer 1

The domain of your problem is $\mathbb{R}^N$, since you want to find $x$. And the range is only $\mathbb{R}$, since you are minimizing $||Ax-B||^2$. Therefore you want to use the G-D to minimize $$ L(x) = ||Ax-B||^2. $$

We want to perform $x_{n+1} = x_n - \gamma_n \nabla L(x_n)$, where $x_{n+1}, x_n, \nabla L(x_n) \in \mathbb{R}^N$ and $\gamma_n\in\mathbb{R}$. The value of $k$ does not matter.

To see how to evaluate $\nabla L(x)$ see this question.