Prove that the following two optimization problems are equivalent

Question

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 ?

Answer 1

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}$.