# Prove that the following two optimization problems are equivalent

I am trying to solve the following optimization problem for the vector $y$, where $A_i$ are some given matrix (maybe low rank) and $x_i$ are unconstrained $$\min_{y, x_i} \sum_{i=1}^J || y - A_i x_i ||_2^2, \;\;\;\;\text{ subject to } ||y||_2 = 1, \;\; || A_i x_i ||_2 = 1 \;\; \forall i$$

I believe that solving the following problem, where I drop the constraints on the projections, would give the same solution for $y$ but I am having a hard time proving it.

$$\min_{y, x_i} \sum_{i=1}^J || y - A_i x_i ||_2^2, \;\;\;\;\text{ subject to } ||y||_2 = 1$$ To be clear, I only care about the value of $y$ and not about the actual values of $x_i$. I know that the values of $x_i$ are going to be different in the two problem but is there a proof/disproof that the values of $y$ are going to be the same ?

• Is $\|\cdot\|_F$ the Frobenius norm? If so, why are you using it on a vector? – Yoav Kallus Jun 10 '15 at 4:40
• aah sorry , yes it should just be the 2 norm. – Pushpendre Jun 10 '15 at 5:16

The optimal values of the two optimization problems are not identical. Consider for example $J=3$, $A_1=\begin{pmatrix} 1 \\0 \end{pmatrix}$ and $A_2=A_3=\begin{pmatrix} 0 \\1 \end{pmatrix}$. The optimal values for the first optimization problem are $y=\frac{1}{\sqrt{5}} \begin{pmatrix}\pm 1\\\pm 2\end{pmatrix}$. The optimal values for the second optimization problem however are $y=\pm \begin{pmatrix}0\\ 1\end{pmatrix}$.