8
$\begingroup$

I have a question about CP tensor ranks. In the following, $\mathcal X \in \mathbb R^{n_1 \times n_2 \times n_3}$ is a third-order tensor of CP rank $R$, i.e., there exist vectors $a_i$, $b_i$ and $c_i$ for $i = 1, \ldots, R$ of appropriate dimensions such that $$\mathrm{vec}(\mathcal X) = c_1 \otimes b_1 \otimes a_1 + \ldots + c_R \otimes b_R \otimes a_R.$$

The following theorem holds.

Theorem. Let $R_\mu$ be the rank of the matricization $X^{(\mu)}$ of $\mathcal X$ for $\mu = 1, 2, 3$. Then $$ \max\{R_1,R_2, R_3\} \leq R \leq \min\{R_1R_2, R_1R_3, R_2R_3\}.$$

While I have no issues with the lower bound (i.e., left), I can neither prove nor find a reference for the proof of the upper bound. I can prove that $R \leq \min\{n_1n_2, n_1n_3, n_2n_3\}$, but that is not enough, as $R_\mu \leq n_\mu$ for $\mu = 1, 2, 3$.

EDIT: Proof of $R \leq \min\{n_1n_2, n_1n_3, n_2n_3\}$

(w.l.o.g. prove $R \leq n_1 n_2$.) Consider $X^{(1)} \in \mathbb R^{n_1\times n_2n_3}$ the first matricization of $\mathcal X$, and write $$ X^{(1)} = [x_1, \ldots, x_{n_2n_3}] $$ Then we have for the canonical basis vectors $e_i \in \mathbb{R}^{n_2n_3}$ $$ X^{(1)} = \sum_{i = 1}^{n_2 n_3} x_i e_i^\top $$ And by vectorization $$ \mathrm{vec}(\mathcal X) = \mathrm{vec}(X^{(1)}) = \sum_{i = 1}^{n_2 n_3} e_i \otimes x_i, $$ which implies that $R \leq n_2 n_3$ by constructing vectors $g_i$ and $h_i$ such that $g_i \otimes h_i = e_i$.

$\endgroup$

1 Answer 1

4
$\begingroup$

We first note that vectors $c_1\otimes a_1,\ldots,c_R\otimes a_R$ are linearly independent. Otherwise, after reordering if necessary, there would exist scalars $\beta_1,\ldots,\beta_{R-1}$ such that $$c_R\otimes a_R = \sum_{k=1}^{R-1}\beta_k(c_k\otimes a_k)\,.$$ Using definition and linearity of Kronecker product, this would lead to \begin{align} \operatorname{vec}(\mathcal{X}) &= \sum_{k=1}^{R-1}c_k\otimes b_k\otimes a_k + c_R\otimes b_R\otimes a_R\\ &= \sum_{k=1}^{R-1}c_k\otimes (b_k+\beta_kb_R)\otimes a_k\,, \end{align} which is in contradiction with $\mathcal{X}$ having CP rank $R$.

Said differently, matrix $$C\odot A=\begin{bmatrix}c_1\otimes a_1 & \cdots & c_R\otimes a_R\end{bmatrix},$$ where $\odot$ denotes Kathri-Rao product, has rank $R$. The second matricization of $\mathcal{X}$ can be written as $$X^{(2)}=B(C\odot A)^T\,.$$ Since $C\odot A$ is of full column rank, it follows that $$R_2=\operatorname{rank}(X^{(2)}) = \operatorname{rank}(B)\,.$$

We can repeat all of the observations above for the first and the third matricization of $\mathcal{X}$ to conclude $$R = \operatorname{rank}(C\odot B) = \operatorname{rank}(C\odot A) = \operatorname{rank}(B\odot A)$$ and $$R_1=\operatorname{rank}(A),\quad R_2=\operatorname{rank}(B),\quad R_3=\operatorname{rank}(C)\,.$$

Now, we have $$R = \operatorname{rank}(C\odot B) \leq \operatorname{rank}(C\otimes B) = \operatorname{rank}(B)\operatorname{rank}(C)=R_2R_3\,,$$ where inequality holds because each column of $C\odot B$ appears as a column of $C\otimes B$. Repeating this for matrices $C\odot A$ and $B\odot A$ proves the theorem.

$\endgroup$
1
  • $\begingroup$ Really cool! Thanks $\endgroup$
    – G. Gare
    Jun 5, 2019 at 9:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .