Minimization of squared norm of a vector sum \( f(x) = ||a + Mx||^2 \)
Problem statement
Given a vector of the form a + Mx, where M is a matrix and a is a vector, we want to find x that minimizes the squared norm of the vector.
\( \text{min}_\amber{x} \ ||\underbrace{a}_{\in R^n} + \underbrace{M}_{\in R^{\text{n x k}}} \amber{\underbrace{x}_{\in R^k}}||^2 \)Find x for which \( ||a + Mx||^2 \) is minimized. Here M is the basis vector \( e_1 \) and x is a scalar. The vector with minimum norm is shown in bold.
Solution
We can write the function as:
\[
\begin{align}
f(x) &= \langle a + Mx, a + Mx \rangle \\
&= \langle a, a \rangle + 2 \langle a, Mx \rangle + \langle Mx, Mx \rangle \\
&= \langle a, a \rangle + 2 \langle M^Ta, x \rangle + \langle M^TMx, x \rangle
\end{align}
\]It then follows that \( \nabla f(\amber{x}) = 2M^Ta + 2M^TM\amber{x} \). Setting it to zero, we get the solution:
\( \amber{x}^* = -(M^TM)^{-1}M^Ta \)
Note that \( M\amber{x}^* \) is the projection of \( a \) onto the column space of \( M \).
Thus the optimal value of \( \amber{x} \) is the negative of the projection of \( a \) onto the column space of \( M \). Ideally, if \( Mx \) were equal to \( -a \), the norm of the sum would be zero. But that may not be possible if \( a \) is not in the column space of \( M \). Simply said, the optimal value of \( \amber{x} \) tries to get \( M\amber{x} \) as close as possible to \( -a \).
Related articles: