How to determine the rank of a Khatri-Rao product of two matrices based on their each rank

Question

As is known to all, the Khatri-Rao product is defined as $\mathbf{C}=\mathbf{A}\odot \mathbf{B}=\left[\begin{matrix}\mathbf{a}_1\otimes\mathbf{b}_1&\mathbf{a}_2\otimes\mathbf{b}_2&\cdots \mathbf{a}_K\otimes\mathbf{b}_K\end{matrix}\right]$,where both $\mathbf{a}_i\in \mathbb{C}^{I\times1}$ $\mathbf{b}_i\in \mathbb{C}^{J\times1}$ and $\mathbf{C} \in \mathbb{C}^{IJ\times K}$. I don't know how to determine the rank of the matrix $\mathbf{C}$,based on the ranks of $\mathbf{A}$ and $\mathbf{B}$.

Answer 1

I stumbled upon this question in own search on an related question. For the Kronecker product $\otimes$, the identity holds that $rank(A \otimes B) = rank(A)rank(B)$ which is "well known" (c.f. [1]).

To the best of my knowledge, there exist no such relation for the Khatri-Rao product $\odot$. However, for $A\in \mathbb{R}^{I\times K}$ and $B\in \mathbb{R}^{J\times K}$ if $rank(A)\geq 1$ and $rank(B)\geq 1$ then

$$rank(A\odot B) \geq min(rank(A)+rank(B)-1, K)$$

The first proof of this appear in [2], but shorter proofs are given in [3, 4, 5].

I do not think a tight bound exists (as in the Kronecker case), but I haven't seen a proof that it does not.

References

[1] Sidiropoulos ND, De Lathauwer L, Fu X, Huang K, Papalexakis EE, Faloutsos C. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing. 2017 Jul 1;65(13):3551-82.

[2] Sidiropoulos ND, Bro R. On the uniqueness of multilinear decomposition of N‐way arrays. Journal of Chemometrics: A Journal of the Chemometrics Society. 2000 May;14(3):229-39.

[3] Ten Berge JM. The k-rank of a Khatri–Rao product. Unpublished Note, Heijmans Institute of Psychological Research, University of Groningen, The Netherlands. 2000.

[4] Stegeman A, Sidiropoulos ND. On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition. Linear Algebra and its applications. 2007 Jan 15;420(2-3):540-52.

[5] De Lathauwer L. Decompositions of a higher-order tensor in block terms—Part I: Lemmas for partitioned matrices. SIAM Journal on Matrix Analysis and Applications. 2008;30(3):1022-32.