MSE of correlations

Question

These might be dumb questions but I am having trouble to wrap my head around of a particular problem. I have a sparse count matrix $G $ that I want to optimize which is $N \times p$. Also, I have correlation matrix $C_{ij}$ which is $N \times N$ that I want matrix $G$ to be optimized for. So, without any constraints I have the following loss function:

$$ \text{loss} = \sum_i\sum_j (\operatorname{corr}(G_i, G_j) - C_{ij})^2 $$

where $G_i$ is a vector $1 \times p$ and $i = j = 1,\ldots,N$.

So, my first question is how can I solve/implement this particular problem?

My second question is related to my lack of knowledge regarding defining optimization problems :)

First of all, as I mentioned above $G$ is a count matrix and it is very sparse and I also want to keep the distribution of each $G_i$ while optimizing, not just randomly change it as it is described above because the initial values are important. So, my question is that is there a way for me to add these information into the problem design?

Answer 1

As far as i see, this problem has similarities with Non-Negative Matrix Factorization (NMF) as data $G$ matrix has non negative entries with many zeros.

$$G_{i,j}= \sum_n W_{i,k} H_{k,j}$$

Where $W$ and $H$ are $n×k$ and $k×n$ matrices and $G$ is approximated/represented with $WH$. The major caveat here $W$ and $H$ have to have only non negative entities too. If your end results is to have a kind of "transformed" non negative correlation matrix C factorized into two non negative vector $W, H$ , then NMF might help..

Element of Statistical Learning page 553, section 14.6 represents an optimization setup based on minimising a divergence objective function where $G_{i,j}$ has a Poisson distribution .

Answer 2

Analysis:

1. Sample correlation is a highly-nonlinear function, so it is unlikely we will be able to solve the optimization problem analytically. So we will need to look for a numerical solution.
2. The unconstrained problem clearly has multiple extrema, because there are multiple ways to achieve the same correlation value. Further, since you require an integer solution to your matrix coefficients, some extremas may be better than other because they are closer to integer values and introduce less loss when rounded off. It must be noted that exact solutions to optimization problems over integers are often NP-hard, so only an approximate solution may be feasible.

So, if you don't want to delve too deep into mathematics and only need an approximate solution, you might try some standard optimization techniques (e.g. scipy). The strategy would be to optimize the loss function over non-negative floating-point numbers, then round them off to nearest integers. Since there are multiple extrema in place, it would be beneficial to run the algorithm for multiple random initial conditions. Finally, if performance is an issue, you may consider computing Jacobian and/or Hessian of your loss function analytically, as some methods can perform significantly faster if such information is provided.

Also you mentioned very sparse solutions. Sparsity of a numerical solution is typically controlled by introducing additional L1 Norm to the loss function, and regulating the desired accurracy/sparsity ratio by changing the prefactor in front of the L1 Norm. In your case, if you require independent sparsity constraints on each row, you may consider adding an independent penalty for each row.