1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure there's not a $2$ in front of $\mathop{\textrm{Tr}}(\Theta\Phi)$? Because it would be convex if that were so. In fact, if that is the case, the objective function is just $$\|A+B+\Phi+\Theta\|_F^2-\|A+B\|_F^2$$ Since you say it's a convex quadratic program, I'm guessing that $2$ is supposed to be there. $\endgroup$ – Michael Grant Aug 9 '15 at 21:34
  • $\begingroup$ @MichaelGrant You are absolutely right. There was a 2 missing. I have now reformulated the problem (more like fixed it). Any new insights would be highly appreciated. $\endgroup$ – Amir Aug 9 '15 at 23:42
  • $\begingroup$ Wait, that's significantly different. Why did you break the products apart? $\endgroup$ – Michael Grant Aug 9 '15 at 23:43
  • 1
    $\begingroup$ @MichaelGrant Sure. Give me a couple of minute to sketch the whole problem. To be honest, this is a bit of a sunday adventure. $\endgroup$ – Amir Aug 10 '15 at 0:05
  • 1
    $\begingroup$ Ok, this is cool, but again: what does it look like before Cauchy-Schwarz? I think that is making it harder not easier. $\endgroup$ – Michael Grant Aug 10 '15 at 3:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm a little bit confused here. Doesn't the objective need to be linear for it to be a semidefinite program? As written it looks like there are nonlinear cusps in it. I was thinking one might squaring the objective and use an interior point method - is that not as good? $\endgroup$ – Nick Alger Aug 10 '15 at 23:13
  • $\begingroup$ Well, I'm using the term a bit loosely, yes. A pure semidefinite solver is going to require a linear objective. This is going to require a bit of work to convert to pure semidefinite form, but a modeling framework like CVX or YALMIP (users.isy.liu.se/johanl/yalmip) is going to have no problem with that. Don't square the objective, that's for sure. $\endgroup$ – Michael Grant Aug 10 '15 at 23:15
  • $\begingroup$ What CVX would do, and what I would do if I were doing it by hand, is to linearize the objective by moving the Frobenius norm to a constraint. That constraint is isomorphic to a standard SOCP constraint. Most SDP solvers can handle SOCP constraints natively. $\endgroup$ – Michael Grant Aug 10 '15 at 23:16
  • $\begingroup$ Thanks for following up on this question. I'll go through it thoroughly tomorrow, and let you know. I really appreciate it. $\endgroup$ – Amir Aug 10 '15 at 23:21
  • $\begingroup$ This is a bit confusing, which explains my attempt to use Cauchy Schwarz inequality to establish an upper bound. This may very well be quite trivial but please help me out here. Independence of $X$ and $\tilde{X}$, that is $X\tilde{X}'=0$ does not necessarily imply that $X'\tilde{X}=0$. So is the case with the diagonal matrices. $\endgroup$ – Amir Aug 11 '15 at 14:45

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.