# Finding high-dimensional correlation matrices that are both sparse and low-rank

Let $\boldsymbol{R}$ be the correlation matrix of $X_i,i=1,\dots,p$ with a large $p\gg q=\text{rank}(\boldsymbol{R})$. Is that reasonable to assume that $\boldsymbol{R}$ is both (approximately) sparse and low rank?

The approximate sparsity may refer to (7) in this paper.

The vector space spanned by $X_i$, $i=1,\dots,p$ is $q$-dimensional, i.e., has $q$ uncorrelated basis random variables. It seems $X_i$, $i=1,\dots,p$ are highly correlated. So, it seems $\boldsymbol{R}$ should not be (approximately) sparse. But I find that in this paper the authors assume $\boldsymbol{R}$ (without the noise part) satisfies these two conditions.

Any intuition behind this assumption?

• $1_p 1_p^{\top}$ is rank-1 and not at all sparse. Feb 16, 2017 at 16:52
• @RodrigodeAzevedo, Thanks. But I prefer to see some examples satisfy the both conditions.
– John
Feb 16, 2017 at 17:15
• So, you want to find correlation matrices that are both low-rank and sparse? Feb 16, 2017 at 17:18
• @RodrigodeAzevedo, correct. And I also hope to see if that is reasonable in practical applications.
– John
Feb 16, 2017 at 17:32
• Is there a desired sparsity pattern? Are there entries in the correlation matrix that must be zero? Feb 16, 2017 at 17:41

Suppose we are given $$n, r \in \mathbb N^+$$, where $$n$$ is a multiple of $$r$$. Let $$m := \dfrac nr$$ and let $$\mathrm z \in \{\pm 1\}^m$$.

We define the fat $$r \times n$$ matrix

$$\mathrm X := \mathrm z^{\top} \otimes \mathrm I_r$$

which has full row rank. Consider the following $$n \times n$$ Gram matrix

$$\mathrm X^{\top} \mathrm X = (\mathrm z \otimes \mathrm I_r) (\mathrm z^{\top} \otimes \mathrm I_r) = \mathrm z \mathrm z^{\top} \otimes \mathrm I_r$$

By construction, this Gram matrix is symmetric, positive semidefinite and it has only ones on its main diagonal. Thus, it is a correlation matrix. Its rank is $$r$$, also by construction. There are no guarantees that $$\mathrm z \mathrm z^{\top} \otimes \mathrm I_r$$ is the sparsest $$n \times n$$ rank-$$r$$ correlation matrix, of course.

### Example

Suppose we want to build a $$12 \times 12$$ rank-$$3$$ correlation matrix. Hence, $$n= 12$$, $$r = 3$$, $$m = 4$$. Let us choose the binary vector $$\mathrm z = 1_4$$. Hence,

$$\mathrm X = 1_4^{\top} \otimes \mathrm I_3 = \begin{bmatrix} \mathrm I_3 & \mathrm I_3 & \mathrm I_3 & \mathrm I_3\end{bmatrix}$$

and

$$\mathrm X^{\top} \mathrm X = 1_4 1_4^{\top} \otimes \mathrm I_3 = \begin{bmatrix} \mathrm I_3 & \mathrm I_3 & \mathrm I_3 & \mathrm I_3\\ \mathrm I_3 & \mathrm I_3 & \mathrm I_3 & \mathrm I_3\\ \mathrm I_3 & \mathrm I_3 & \mathrm I_3 & \mathrm I_3\\ \mathrm I_3 & \mathrm I_3 & \mathrm I_3 & \mathrm I_3\end{bmatrix}$$

is a correlation matrix. Of the $$12^2 = 144$$ entries, only $$4^2 \cdot 3 = 48$$ are nonzero.