Minimization of squared norm of a vector sum

f(x)=∥a+Mx∥2f(x) = \|a + Mx\|^2

Problem statement

Given a vector of the form a+Mxa + Mx, where MM is a matrix and aa is a vector, we want to find xx that minimizes the squared norm of the vector.

minx ∥a⏟∈Rn+M⏟∈Rn x kx⏟∈Rk∥2\text{min}_{\textcolor{#b45309}{x}} \ \|\underbrace{a}_{\in R^n} + \underbrace{M}_{\in R^{\text{n x k}}} \textcolor{#b45309}{\underbrace{x}_{\in R^k}}\|^2
Mx a

Find x for which ∥a+Mx∥2\|a + Mx\|^2 is minimized. Here M is the basis vector e1e_1 and x is a scalar. The vector with minimum norm is shown in bold.

Solution

We can write the function as:

f(x)=⟨a+Mx,a+Mx⟩=⟨a,a⟩+2⟨a,Mx⟩+⟨Mx,Mx⟩=⟨a,a⟩+2⟨MTa,x⟩+⟨MTMx,x⟩\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 ∇f(x)=2MTa+2MTMx\nabla f(\textcolor{#b45309}{x}) = 2M^Ta + 2M^TM\textcolor{#b45309}{x}. Setting it to zero, we get the solution:

x∗=−(MTM)−1MTa\textcolor{#b45309}{x}^* = -(M^TM)^{-1}M^Ta

Note that Mx∗M\textcolor{#b45309}{x}^* is the projection of aa onto the column space of MM.

Thus the optimal value of x\textcolor{#b45309}{x} is the negative of the projection of aa onto the column space of MM. Ideally, if MxMx were equal to −a-a, the norm of the sum would be zero. But that may not be possible if aa is not in the column space of MM. Simply said, the optimal value of x\textcolor{#b45309}{x} tries to get MxM\textcolor{#b45309}{x} as close as possible to −a-a.

Related articles: