# How represent correlation of $(f_i - f_j)$ and some $y$ by $cov(f_i, f_j)$, $cov(f_i, y)$ and $cov(f_j, y)$?

I am reading this paper: Face Alignment by Explicit Shape Regression.

One of the significant step of algorithm which proposed in these paper connected with correlation. But my knowledge about probability theory are extremely limited.

I need to compute $cor((f_i - f_j), y)$ for $i, j \in [1..N]$

where $cor(a, b)$ - correlation of two random variables (i don't know which symbol used to denote correlation), $f_i \in \{f_1, f_2, ..... f_N\}$ - set of random variables, $y$ - some random variable. For every random variable i have some set of measurements so it seems to i can estimate expectation and variance

Of course in rude way i need to compute $O(N^2)$ correlations. But paper says (part 2.4. "Correlation-based feature selection") that i can reduce complexity to $O(N)$ because

The correlation between a scalar y and a pixel-difference feature $(f_i − f_j)$ can be represented as the function of three terms: $cov(f_i, f_j)$, $cov(y, f_i)$, and $cov(y, f_j)$.

From wikipedia i know that i can represent $cov((f_i - f_j), y)$ as $cov(f_i, y) - cov(f_j, y)$ and trying ro compute correlation.

But i cannot derive why i need $cov(f_i, f_j)$.

So how i can represent correlation from things above ?

PS Sorry for my poor English and math skills

The correlation between two random variables $X, Y$ is given by: $$\rho = \frac{Cov(X, Y)}{\sqrt{Var(X)}\sqrt{Var(Y)}}$$ In your case, \begin{eqnarray*} \rho &=& \frac{Cov(f_i - f_j, y)}{\sqrt{Var(f_i - f_j)}\sqrt{Var(y)}} \\ &=& \frac{Cov(f_i,y) - Cov(f_j, y)}{\sqrt{Var(f_i - f_j)}\sqrt{Var(y)}} \\ &=& \frac{Cov(f_i,y) - Cov(f_j, y)}{\sqrt{Var(f_i) -2 Cov(f_i,f_j) + Var(f_j)}\sqrt{Var(y)}} \\ \end{eqnarray*}
Note that $Cov(f_i,f_j) = Var(f_i)$ when $i=j$.