# Proving convexity of Frobenius norm and correlation function formulations of an optimization problem

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

• 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. – Mark L. Stone Feb 6 '20 at 14:09
• @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. – venkat Feb 6 '20 at 16:02
• @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 – venkat Feb 7 '20 at 19:43
• 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. – Mark L. Stone Feb 7 '20 at 20:45
• 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 – venkat Feb 8 '20 at 6:55