20
$\begingroup$

I was asked this question in an interview.

Lets say we have a correlation matrix of the form
\begin{bmatrix}1&0.6&0.8\\0.6&1&\gamma\\0.8&\gamma&1\end{bmatrix}

I was asked to find the value of gamma, given this correlation matrix.
I thought I could do something with the eigenvalues, since they should be all greater than or equal to 0.(Matrix should be positive semidefinite) - but I don't think this approach will yield the answer. I am missing a trick.

Could you please provide a hint to solve for the same?

$\endgroup$
21
$\begingroup$

We already know $\gamma$ is bounded between $[-1,1]$ The correlation matrix should be positive semidefinite and hence its principal minors should be nonnegative

Thus, \begin{align*} 1(1-\gamma^2)-0.6(0.6-0.8\gamma)+0.8(0.6\gamma-0.8) &\geq 0\\ -\gamma^2+0.96\gamma \geq 0\\ \implies \gamma(\gamma-0.96) \leq 0 \text{ and } -1 \leq \gamma \leq 1 \\ \implies 0 \leq \gamma \leq 0.96 \end{align*}

$\endgroup$
  • 4
    $\begingroup$ @novice You might want to read about Sylvester's Criterion $\endgroup$ – rightskewed Jan 3 '17 at 10:10
  • $\begingroup$ Great answer. I would add the following: The popular way of obtaining gamma is to attempt to find the gamma that would lead to the correlation matrix of smallest nuclear norm (aka ky-fan norm) possible while solving the above equations. For more, look up "matrix completion," "compressive sensing," or check out this report on the topic bit.ly/2iwY1nW. $\endgroup$ – Mustafa S Eisa Jan 3 '17 at 23:26
  • 1
    $\begingroup$ For this to be a proof, you need a result in the other direction: if all nontrivial leading minors are $>0$ and the matrix has determinant $\geq 0$, then the matrix is positive semidefinite. $\endgroup$ – Federico Poloni Jan 4 '17 at 9:47
10
$\begingroup$

Here's a simpler (and perhaps more intuitive) solution:

Think of the covariance as an inner product over an abstract vector space. Then, the entries in the correlation matrix are $\cos\langle\mathbf{v}_i,\mathbf{v}_j\rangle$ for the vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, where the angle bracket $\langle\mathbf{v}_i,\mathbf{v}_j\rangle$ denotes the angle between $\mathbf{v}_i$ and $\mathbf{v}_j$.

It is not hard to visualize that $\langle\mathbf{v}_2,\mathbf{v}_3\rangle$ is bounded by $|\langle\mathbf{v}_1,\mathbf{v}_2\rangle\pm\langle\mathbf{v}_1,\mathbf{v}_3\rangle|$. The bound on its cosine ($\gamma$) is thus $\cos\left[\langle\mathbf{v}_1,\mathbf{v}_2\rangle\pm\langle\mathbf{v}_1,\mathbf{v}_3\rangle\right]$. Basic trigonometry then gives $\gamma\in[0.6\times 0.8 - 0.6\times 0.8, 0.6\times 0.8 + 0.6\times 0.8] = [0, 0.96]$.

Edit: Note that the $0.6\times 0.8 \mp 0.6\times 0.8$ in the last line is really $\cos\langle\mathbf{v}_1,\mathbf{v}_2\rangle\cos\langle\mathbf{v}_1,\mathbf{v}_3\rangle\mp \sin\langle\mathbf{v}_1,\mathbf{v}_3\rangle\sin\langle\mathbf{v}_1,\mathbf{v}_2\rangle$ -- the second appearance of 0.6 and 0.8 occurs by coincidence thanks to $0.6^2+0.8^2=1$.

$\endgroup$
  • 1
    $\begingroup$ +1, A legitimate geometric reasoning (saying it, I didn't check your computations nonetheless). This is exactly what I've proposed in comments to the question (unfortunately, all the comments were moved by moderator to chat, see the link above). $\endgroup$ – ttnphns Jan 3 '17 at 20:52
  • $\begingroup$ It seems to me you have "proven" that all correlations must be non-negative, because it appears your calculation will always give zero for the lower limit. If that's not the case, then could you elaborate on how your computation works in general? I really don't trust--or perhaps don't understand--your bound, because in three or more dimensions you can always find a $v_1$ for which both $v_1\cdot v_2=v_1\cdot v_3=0$ and then your bound implies $v_2\cdot v_3$ is always zero! (cc @ttnphns) $\endgroup$ – whuber Jan 3 '17 at 22:35
  • $\begingroup$ @whuber: Sorry about the confusion. The calculation does not always give zero for the lower limit. I've amended my answer. $\endgroup$ – yangle Jan 4 '17 at 0:14
  • $\begingroup$ How do you respond to my last concern? It seems to indicate your bounds are incorrect. $\endgroup$ – whuber Jan 4 '17 at 0:16
  • $\begingroup$ @whuber: In your case, ⟨v1,v2⟩=⟨v1,v3⟩=π/2, hence the bound |⟨v1,v2⟩±⟨v1,v3⟩| is [0, π] as expected. The bound cos⟨v1,v2⟩cos⟨v1,v3⟩∓sin⟨v1,v3⟩sin⟨v1,v2⟩ on γ also works out to be [-1, 1]. $\endgroup$ – yangle Jan 4 '17 at 0:19
4
$\begingroup$

Here is what I meant in my initial comment to the answer and what I perceive @yangle may be speaking about (although I didn't follow/check their computation).

"Matrix should be positive semidefinite" implies the variable vectors are a bunch in Euclidean space. The case of correlation matrix is easier than covariance matrix because the three vector lengths are fixed to be 1. Imagine 3 unit vectors X Y Z and remember that $r$ is the cosine of the angle. So, $\cos \alpha=r_{xy}=0.6$, and $\cos \beta=r_{yz}=0.8$. What might be the boundaries for $\cos \gamma=r_{xz}$? That correlation can take on any value defined by Z circumscribing about Y (keeping angle $r_{yz}=0.8$ with it):

enter image description here

As it spins, two positions are remarkable as ultimate wrt X, both are when Z falls into the plane XY. One is between X and Y, and the other is on the opposite side of Y. These are shown by blue and red vectors. At both these positions exactly the configuration XYZ (correlation matrix) is singular. And these are the minimal and maximal angle (hence correlation) Z can attain wrt X.

Picking the trigonometric formula to compute sum or difference of angles on a plane, we have:

$\cos \gamma = r_{xy} r_{yz} \mp \sqrt{(1-r_{xy}^2)(1-r_{yz}^2)} = [0,0.96]$ as the bounds.

This geometric view is just another (and a specific and simpler in 3D case) look on what @rightskewed expressed in algebraic terms (minors etc.).

$\endgroup$
  • $\begingroup$ If X,Y,Z are random variables, how do you map them to vectors in 3d space (They can only be vectors in 1d space). Also if the RV's are Nx1, then they will be vectors in N dimensional space? $\endgroup$ – novice Jan 4 '17 at 1:04
  • $\begingroup$ @novice Yes, they are initially 3 vectors in Nd space, but only 3 dimensions are nonredundant. Please follow the 2nd link in the answer and read further reference there to subject space where it is explained. $\endgroup$ – ttnphns Jan 4 '17 at 1:11
4
$\begingroup$

Playing around with principal minors may be fine on 3 by 3 or maybe 4 by 4 problems, but runs out of gas and numerical stability in higher dimensions.

For a single "free" parameter problem such as this, it's easy to see that that the set of all values making the matrix psd will be a single interval. Therefore, it is sufficient to find the minimum and maximum such values. This can easily be accomplished by numerically solving a pair of linear SemiDefinite Programming (SDP) problems:

  1. minimize γ subject to matrix is psd.
  2. maximize γ subject to matrix is psd.

For example, these problems can be formulated and numerically solved using YALMIP under MATLAB.

  1. gamma = sdpvar; A = [1 .6 .8;.6 1 gamma;.8 gamma 1]; optimize(A >= 0, gamma)
  2. optimize(A >= 0,-gamma)

Fast, easy, and reliable.

BTW, if the smarty pants interviewer asking the question doesn't know that SemiDefinite Programming, which is well-developed and has sophisticated and easy to use numerical optimizers for reliably solving practical problems, can be used to solve this problem, and many much more difficult variants, tell him/her that this is no longer 1870, and it's time to take advantage of modern computational developments.

$\endgroup$
4
$\begingroup$

Let us consider the following convex set

$$\Bigg\{ (x,y,z) \in \mathbb R^3 : \begin{bmatrix} 1 & x & y\\ x & 1 & z\\ y & z & 1\end{bmatrix} \succeq \mathrm O_3 \Bigg\}$$

which is a spectrahedron named $3$-dimensional elliptope. Here's a depiction of this elliptope

enter image description here

Intersecting this elliptope with the planes defined by $x=0.6$ and by $y=0.8$, we obtain a line segment whose endpoints are colored in yellow

enter image description here

The boundary of the elliptope is a cubic surface defined by

$$\det \begin{bmatrix} 1 & x & y\\ x & 1 & z\\ y & z & 1\end{bmatrix} = 1 + 2 x y z - x^2 - y^2 - z^2 = 0$$

If $x=0.6$ and $y=0.8$, then the cubic equation above boils down to the quadratic equation

$$0.96 z - z^2 = z (0.96 - z) = 0$$

Thus, the intersection of the elliptope with the two planes is the line segment parametrized by

$$\{ (0.6, 0.8, t) \mid 0 \leq t \leq 0.96 \}$$

$\endgroup$
1
$\begingroup$

Every positive semi-definite matrix is a correlation/covariance matrix (and vice versa).

To see this, start with a positive semi-definite matrix $A$ and take its eigen-decomposition (which exists by the spectral theorm, since $A$ is symmetric) $A=UDU^T$ where $U$ is a matrix of orthonormal eigenvectors and $D$ is a diagonal matrix with eigen values on the diagonal. Then, let $B= U D^{1/2} U^T$ where $D^{1/2}$ is a diagonal matrix with the square root of eignevalues on the diagonal.

Then, take a vector with i.i.d. mean zero and variance 1 entries, $\mathbf{x}$ and note that $B \mathbf{x}$ also has mean zero, and covariance (and correlation) matrix $A$.

Now, to see every correlation/covariance matrix is positive semi-definite is simple: Let $R=E[\mathbf{x}\mathbf{x}^T]$ be a correlation matrix. Then, $R = R^T$ is easy to see, and $\mathbf{a}^T R \mathbf{a} = E[(\mathbf{a}^T \mathbf{x})^2] \geq 0$ so the Rayleigh quotient is non-negative for any non-zero $\mathbf{a}$ so $R$ is positive semi-definite.

Now, noting that a symmetric matrix is positive semi-definite if and only if its eigenvalues are non-negative, we see that your original approach would work: calculate the characteristic polynomial, look at its roots to see if they are non-negative. Note that testing for positive definiteness is easy with Sylvester's Criterion (as mentioned in another answer's comment; a matrix is positive definite if and only if the principal minors all have positive determinant); there are extensions for semidefinite (all minors have non-negative determinant), but you have to check $2^n$ minors in this case, versus just $n$ for positive definite.

$\endgroup$

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.