How do I minimize this function?

Question

I have an $n \times 1$ real vector $x$ and an $n \times d$ real matrix $y$. I would like to calculate $$ \min_{\Vert v \Vert = 1} \Vert x - yv \Vert ,$$ where $v$ comes from $\Bbb R^d$. The intuition is that $v$ tells one how to combine the columns of $y$ to make a vector which is as close to $x$ as possible.

I've tried Lagrange multipliers and playing around with the function $$ f(v) = \Vert x - yv \Vert^2.$$

The condition $\Vert v \Vert = 1$ is not required but may make the problem easier, not sure. Any help would be very appreciated!

Answer 1

You know that $\|\cdot\|= 0 $ iff $\cdot=0$, so if you find $v$ such that $x-yv=0$, you have found your minimum. This can be done by means of pseudo-inverses; multiply the equation with $y^T$ to get $$ y^Tx -y^Tyv=0$$, where $y^Ty$ is a $d\times d$ matrix. Then v can be found by $$v=(y^Ty)^{-1}y^Tx$$ where v will solve your problem. This will however lose the constraint that $\|v\|=1$.

Answer 2

Applying Lagrange multipliers, gives us: $x$ is optimal if and only if

$$y^T(x-yv) = 0 $$ iff

$$y^Tyv=y^Tx$$ Therefore to find optimal solution you only need to solve the linear system $$Av=b$$ Where $ A=y^Ty$ and $ b=y^Tx$. Which is much easier that finding pseudo-inverses ( which even may not exist! )

If above equation has not solution then there is no optimal solution!