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

Question

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?

Answer 1

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.