2
$\begingroup$

I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting. Firstly, I would like to make the variables I used in the problem and their dimensions clear.

There are $Q$ outputs, $N$ samples, and $P$ covariates (features).

$\hat{Y}\in\mathbb R^{Q\times N}$ is the prediction matrix,

$$\hat{Y}=WX$$

where $W\in\mathbb R^{Q\times P}$ is the parameter matrix. These are the parameters we estimate in the regression.

$X\in\mathbb R^{P\times N}$ is the data matrix

My requirement:

I want to preserve the correlation structure in multi-output regression, i.e., the correlation structure of the predictions and the correlation structure of the data should remain close. I had two formulations for it. I am assuming that the $Y$'s are standardized, Hence $YY^{T}$ is equal to the correlation matrix of the data.

Formulation 1: Minimize the Frobenius norm of the difference between the correlation matrices of the data and the predictions

$$W^{*}=\underset{w}{\mathrm{argmin}}\frac{1}{\mathcal{N}}\|YY^{T}-\hat{Y}\hat{Y}^{T}\|_{F}^{2}$$

Formulation 2: Maximize the correlation between the correlation matrices of the data and the predictions

$$W^{*}=\underset{w}{\mathrm{argmax}} \operatorname{cor}\left(Y{Y}^{T}, \hat{Y}\hat{Y}^{T}\right)$$

where $\operatorname{cor}$ is the correlation function.

Now I have to prove the convexity of the above formulations:

My attempts: (I am giving a very brief description of what I have done and I can elaborate if it helps, kindly ask in the comments section)

I didn't try to generalize the proof for matrices of any size. I started with a matrix $W$ of very small dimensions ($2\times 1$) and $X$ of dimension($1\times 2$) and then tried to prove that the Hessian matrix for both above formulations is PSD (positive semi-definite). The result tends to depend on the values of the matrix $X$ and $Y$.

I am stuck with generalizing this proof. Kindly give your valuable suggestions to prove the convexity/nonconvexity of both the above formulations.

UPDATE: In Formulation 2 I was wondering if I could use the positive semi definiteness properties of the matrices $YY$$^{T}$,$XX$$^{T}$ so I tried the following:

Note: i am replacing the feature correlation matrix $XX$$^{T}$ with $B$ and the output correlation matrix $YY$$^{T}$ with $C$ \begin{align} W=\begin{bmatrix} \alpha_{11}&\alpha_{12}\\ \alpha_{21}&\alpha_{22}\\ \end{bmatrix} \end{align}

\begin{align} B=\begin{bmatrix} b_{11}&b_{12}\\ b_{21}&b_{22}\\ \end{bmatrix} \end{align} \begin{align} C=\begin{bmatrix} c_{11}&c_{12}\\ c_{21}&c_{22}\\ \end{bmatrix} \end{align} $\hat{Y}\hat{Y}^{T}=WXX^{T}W^{T}=WBW^{T}$

now i am rewriting $\operatorname{cor}\left(Y{Y}^{T}, \hat{Y}\hat{Y}^{T}\right)$ as $Vec(C)\cdot\!Vec(WBW^{T})$

now this is my new loss function : $L(\alpha)=Vec(C)\cdot\!Vec(WBW^{T})$.(as $W$ is a function of $\alpha$ and . here is the dot product between the two vectors)

I have calculated the Hessian of the above loss function $L(\alpha)$ for dimensions of $W$($2\times2$),$C$($2\times2$),$B$($2\times2$) and ultimately the Hessian turns out to be $2*C\otimes B$ .Where $\otimes$ is the Kronecker product between two matrices. As both $B$ and $C$ are PSD matrices the Kronecker product of them should also be a PSD matrix (please find the link to the proof below) which means my loss function $L(\alpha)$ should be convex. But however, this may not hold for larger examples as I didn't generalize the proof.

Look at Corollary 2.4 for proof

$\endgroup$
  • $\begingroup$ Are you saying in your penultimate paragraph that for the 2 by 1, 1 by 2 case that whether Hessian is PSD depends on values of X and Y? I.e., that those formulations ate not convex? So conclusion is non-convex? If so, going to higher dimensions won't make things become convex. $\endgroup$ – Mark L. Stone Feb 6 at 14:09
  • $\begingroup$ @Mark L.stone .yes sir. in formulation 1 above for the dimensions of W being 2*1 and X being 1*2, the determinant of the hessian can go negative depending on the values of X and Y matrices, hence it should be non-convex. but I want help in generalizing it and giving a formal proof. $\endgroup$ – venkat Feb 6 at 16:02
  • $\begingroup$ @MarkL.Stone I have updated my question adding some other insights I got, this says my second formulation is convex but I am not sure as I didn't generalize. Please have a look at this $\endgroup$ – venkat Feb 7 at 19:43
  • $\begingroup$ The Kronecker product of 2 PSD matrices is PSD. However, I'm not buying your formula for the Hessian. Are you sure you are not applying some rules which are valid only in one dimension to a higher dimensional matrix? If elements of W are optimization variables, and dimension of W is > 1, the Hessian of a function involving $WW^T$ is generally not going to be convex, and I doubt it is here. $\endgroup$ – Mark L. Stone Feb 7 at 20:45
  • $\begingroup$ The formula I am using for cor function i.e $L(\alpha) =vec(C).vec(WBW^{T})$ just flattens both arrays into vectors and finds the correlation between the two vectors, which I think will hold for finding the correlation between any two same sized matrices. I am not able to understand what I have assumed wrong $\endgroup$ – venkat Feb 8 at 6:55

Your Answer

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

Browse other questions tagged or ask your own question.