Problem Revisited – Edited for conciseness:
We are given two set of data points X [$p \times n$] and Y [$q \times n$].
Let us assume $X = \hat{X} + \tilde{X}$ and $Y = \hat{Y} + \tilde{Y}$
I am trying to minimize the following objective function for $\hat{X}$ and $\hat{Y}$:
\begin{equation*}
\begin{aligned}
& \underset{\hat{X}, \hat{Y}}{\text{minimize }}
& &
\|\hat{X}'\hat{X} – \hat{Y}'\hat{Y}\|_F^2 \\
&& =& Tr((\hat{X}'\hat{X})^2) – 2Tr(\hat{X}'\hat{X}\hat{Y}'\hat{Y}) + Tr((\hat{Y}'\hat{Y})^2)
\end{aligned}
\end{equation*}
subject to the constraints that under the constraints that $X\tilde{X}'=0$ and $Y\tilde{Y}'=0$, and both $\Phi = \tilde{X}\tilde{X}'$ and $\Theta = \tilde{Y}\tilde{Y}'$ are PSD and diagonal.
After expansion of the above equation and application of cauchy-schwarz inequality, the original problem is reduced to the following objective function, subject to the constraint that $\Phi$ [$p \times p$] and $\Theta$ [$q \times q$] are both diagonal matrices and PSD.
$$
\begin{aligned}
& \underset{\Phi, \Theta}{\text{minimize }}
& & f\\
&
& \leq & 2 Tr(XX'\Phi) + Tr(\Phi^2) + 2Tr(YY'\Theta)+ Tr(\Theta^2) \\
&&+& 2Tr(XX')Tr(\Theta) + 2 tr(YY')Tr(\Phi) + 2Tr(\Theta)Tr(\Phi) \\
& \text{subject to}
& & \Phi \text{ and } \Theta \text{ are diagonal and PSD}\\
\end{aligned}
$$
1) Does this equation have a unique solution? If so, how can I find the solution? If not, what are the solution concepts, say w.r.t. minimization of different norms?
2) When I try to encode the problem in terms of the sum of the diagonal elements of $\Phi$ and $\Theta$, the problem is reduced to a convex quadratic program. But what does knowing about the sum of diagonal elements tell about the actual matrix itself, even if we have some extra information about say, the rank of matrices.
Best Answer
This is what I'm thinking. Ignore your attempt to use Cauchy Schwarz. Your problem looks like this: \begin{array}{ll} \text{minimize} & \left\| (X^TX-\Phi) - (Y^TY-\Theta) \right\|_F \\ \text{subject to} & 0 \preceq \Phi \preceq X^T X \\ & 0 \preceq \Theta \preceq Y^T Y \\ & \Phi,\Theta~\text{diagonal} \end{array} where $\preceq$ is the generalized inequality on the semidefinite cone; for instance, $\Phi\preceq X^TX$ means that $X^TX-\Phi$ is positive semidefinite.
This is convex, and in fact a semidefinite program, and is therefore amenable to solution by any semidefinite programming solver.
EDIT: I just realized it can be simplified. Since the variables only concern the diagonal, there's no point in looking at the Frobenius norm of the entire matrix, just look at the diagonal. \begin{array}{ll} \text{minimize} & \left\| \mathop{\textrm{diag}}(X^TX-Y^TY)-\phi+\theta \right\|_2 \\ \text{subject to} & \phi,~\theta_i \geq 0, ~ i=1,2,\dots, n \\ & X^T X - {\mathop{\textrm{diag}}}^{-1}(\phi) \succeq 0 \\ & Y^T Y - {\mathop{\textrm{diag}}}^{-1}(\theta) \succeq 0 \end{array} Not a huge savings, but why not. Now $\phi$ and $\theta$ are just vectors.