0
$\begingroup$

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 ?

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

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

$\endgroup$
1
  • $\begingroup$ Thanks a lot, i only thought about the J=2 case where things seemed to work out because of symmetry but i didn't make the logical next step. $\endgroup$ – Pushpendre Jun 10 '15 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.