Khatri–Rao product

Short description: Type of product of matrices

In mathematics, the Khatri–Rao product of matrices is defined as

$\mathbf{𝐀}\ast \mathbf{𝐁}={({\mathbf{𝐀}}_{ij}\otimes {\mathbf{𝐁}}_{ij})}_{ij}$

in which the ij-th block is the m_ip_i × n_jq_j sized Kronecker product of the corresponding blocks of A and B, assuming the number of row and column partitions of both matrices is equal. The size of the product is then (Σ_i m_ip_i) × (Σ_j n_jq_j).

For example, if A and B both are 2 × 2 partitioned matrices e.g.:

$\mathbf{𝐀}=\left[\begin{array}{cc}{\mathbf{𝐀}}_{11}& {\mathbf{𝐀}}_{12}\\ {\mathbf{𝐀}}_{21}& {\mathbf{𝐀}}_{22}\end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right],\mathbf{𝐁}=\left[\begin{array}{cc}{\mathbf{𝐁}}_{11}& {\mathbf{𝐁}}_{12}\\ {\mathbf{𝐁}}_{21}& {\mathbf{𝐁}}_{22}\end{array}\right]=\left[\begin{array}{ccc}1& 4& 7\\ 2& 5& 8\\ 3& 6& 9\end{array}\right],$

we obtain:

$\mathbf{𝐀}\ast \mathbf{𝐁}=\left[\begin{array}{cc}{\mathbf{𝐀}}_{11}\otimes {\mathbf{𝐁}}_{11}& {\mathbf{𝐀}}_{12}\otimes {\mathbf{𝐁}}_{12}\\ {\mathbf{𝐀}}_{21}\otimes {\mathbf{𝐁}}_{21}& {\mathbf{𝐀}}_{22}\otimes {\mathbf{𝐁}}_{22}\end{array}\right]=\left[\begin{array}{cccc}1& 2& 12& 21\\ 4& 5& 24& 42\\ 14& 16& 45& 72\\ 21& 24& 54& 81\end{array}\right].$

This is a submatrix of the Tracy–Singh product of the two matrices (each partition in this example is a partition in a corner of the Tracy–Singh product) and also may be called the block Kronecker product.

Column-wise Kronecker product

A column-wise Kronecker product of two matrices may also be called the Khatri–Rao product. This product assumes the partitions of the matrices are their columns. In this case m₁ = m, p₁ = p, n = q and for each j: n_j = p_j = 1. The resulting product is a mp × n matrix of which each column is the Kronecker product of the corresponding columns of A and B. Using the matrices from the previous examples with the columns partitioned:

$\mathbf{𝐂}=\left[\begin{array}{ccc}{\mathbf{𝐂}}_1& {\mathbf{𝐂}}_2& {\mathbf{𝐂}}_3\end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right],\mathbf{𝐃}=\left[\begin{array}{ccc}{\mathbf{𝐃}}_1& {\mathbf{𝐃}}_2& {\mathbf{𝐃}}_3\end{array}\right]=\left[\begin{array}{ccc}1& 4& 7\\ 2& 5& 8\\ 3& 6& 9\end{array}\right],$

so that:

$\mathbf{𝐂}\ast \mathbf{𝐃}=\left[\begin{array}{ccc}{\mathbf{𝐂}}_1\otimes {\mathbf{𝐃}}_1& {\mathbf{𝐂}}_2\otimes {\mathbf{𝐃}}_2& {\mathbf{𝐂}}_3\otimes {\mathbf{𝐃}}_3\end{array}\right]=\left[\begin{array}{ccc}1& 8& 21\\ 2& 10& 24\\ 3& 12& 27\\ 4& 20& 42\\ 8& 25& 48\\ 12& 30& 54\\ 7& 32& 63\\ 14& 40& 72\\ 21& 48& 81\end{array}\right].$

This column-wise version of the Khatri–Rao product is useful in linear algebra approaches to data analytical processing and in optimizing the solution of inverse problems dealing with a diagonal matrix.

In 1996 the Column-wise Khatri–Rao product was proposed to estimate the angles of arrival (AOAs) and delays of multipath signals and four coordinates of signals sources at a digital antenna array.

Face-splitting product

Face splitting product of matrices

The alternative concept of the matrix product, which uses row-wise splitting of matrices with a given quantity of rows, was proposed by V. Slyusar in 1996.

This matrix operation was named the "face-splitting product" of matrices or the "transposed Khatri–Rao product". This type of operation is based on row-by-row Kronecker products of two matrices. Using the matrices from the previous examples with the rows partitioned:

$\mathbf{𝐂}=\left[\begin{array}{c}{\mathbf{𝐂}}_1\\ {\mathbf{𝐂}}_2\\ {\mathbf{𝐂}}_3\\ \end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right],\mathbf{𝐃}=\left[\begin{array}{c}{\mathbf{𝐃}}_1\\ {\mathbf{𝐃}}_2\\ {\mathbf{𝐃}}_3\\ \end{array}\right]=\left[\begin{array}{ccc}1& 4& 7\\ 2& 5& 8\\ 3& 6& 9\end{array}\right],$

the result can be obtained:

$\mathbf{𝐂}\bullet \mathbf{𝐃}=\left[\begin{array}{c}{\mathbf{𝐂}}_1\otimes {\mathbf{𝐃}}_1\\ {\mathbf{𝐂}}_2\otimes {\mathbf{𝐃}}_2\\ {\mathbf{𝐂}}_3\otimes {\mathbf{𝐃}}_3\\ \end{array}\right]=\left[\begin{array}{ccccccccc}1& 4& 7& 2& 8& 14& 3& 12& 21\\ 8& 20& 32& 10& 25& 40& 12& 30& 48\\ 21& 42& 63& 24& 48& 72& 27& 54& 81\end{array}\right].$

Main properties

1. Transpose (V. Slyusar, 1996):

   ${(\mathbf{𝐀}\bullet \mathbf{𝐁})}^{\text{T}}={\text{A}}^{\text{T}}\ast {\mathbf{𝐁}}^{\text{T}}$,

2. Bilinearity and associativity:

   $\begin{array}{rl}\mathbf{𝐀}\bullet (\mathbf{𝐁}+\mathbf{𝐂})& =\mathbf{𝐀}\bullet \mathbf{𝐁}+\mathbf{𝐀}\bullet \mathbf{𝐂},\\ (\mathbf{𝐁}+\mathbf{𝐂})\bullet \mathbf{𝐀}& =\mathbf{𝐁}\bullet \mathbf{𝐀}+\mathbf{𝐂}\bullet \mathbf{𝐀},\\ (k\mathbf{𝐀})\bullet \mathbf{𝐁}& =\mathbf{𝐀}\bullet (k\mathbf{𝐁})=k(\mathbf{𝐀}\bullet \mathbf{𝐁}),\\ (\mathbf{𝐀}\bullet \mathbf{𝐁})\bullet \mathbf{𝐂}& =\mathbf{𝐀}\bullet (\mathbf{𝐁}\bullet \mathbf{𝐂}),\\ \end{array}$

   where A, B and C are matrices, and k is a scalar,

   $a\bullet \mathbf{𝐁}=\mathbf{𝐁}\bullet a$,

   where $a$ is a vector,
3. The mixed-product property (V. Slyusar, 1997):

   $(\mathbf{𝐀}\bullet \mathbf{𝐁})({\mathbf{𝐀}}^{\text{T}}\ast {\mathbf{𝐁}}^{\text{T}})=\left(\mathbf{𝐀}{\mathbf{𝐀}}^{\text{T}}\right)\circ \left(\mathbf{𝐁}{\mathbf{𝐁}}^{\text{T}}\right)$,

   $(\mathbf{𝐀}\bullet \mathbf{𝐁})(\mathbf{𝐂}\ast \mathbf{𝐃})=(\mathbf{𝐀}\mathbf{𝐂})\circ (\mathbf{𝐁}\mathbf{𝐃})$,

   $(\mathbf{𝐀}\bullet \mathbf{𝐁}\bullet \mathbf{𝐂}\bullet \mathbf{𝐃})(\mathbf{𝐋}\ast \mathbf{𝐌}\ast \mathbf{𝐍}\ast \mathbf{𝐏})=(\mathbf{𝐀}\mathbf{𝐋})\circ (\mathbf{𝐁}\mathbf{𝐌})\circ (\mathbf{𝐂}\mathbf{𝐍})\circ (\mathbf{𝐃}\mathbf{𝐏})$

   $(\mathbf{𝐀}\ast \mathbf{𝐁}{)}^{\text{T}}(\mathbf{𝐀}\ast \mathbf{𝐁})=\left({\mathbf{𝐀}}^{\text{T}}\mathbf{𝐀}\right)\circ \left({\mathbf{𝐁}}^{\text{T}}\mathbf{𝐁}\right)$,

   where $\circ$ denotes the Hadamard product,
4. $(\mathbf{𝐀}\circ \mathbf{𝐁})\bullet (\mathbf{𝐂}\circ \mathbf{𝐃})=(\mathbf{𝐀}\bullet \mathbf{𝐂})\circ (\mathbf{𝐁}\bullet \mathbf{𝐃})$,
5. $\mathbf{𝐀}\otimes (\mathbf{𝐁}\bullet \mathbf{𝐂})=(\mathbf{𝐀}\otimes \mathbf{𝐁})\bullet \mathbf{𝐂}$,
6. $(\mathbf{𝐀}\otimes \mathbf{𝐁})(\mathbf{𝐂}\ast \mathbf{𝐃})=(\mathbf{𝐀}\mathbf{𝐂})\ast (\mathbf{𝐁}\mathbf{𝐃})$,
7. $(\mathbf{𝐀}\otimes \mathbf{𝐁})\ast (\mathbf{𝐂}\otimes \mathbf{𝐃})=\mathbf{𝐏}[(\mathbf{𝐀}\ast \mathbf{𝐂})\otimes (\mathbf{𝐁}\ast \mathbf{𝐃})]$, where $\mathbf{𝐏}$ is a permutation matrix.
8.  

   $(\mathbf{𝐀}\bullet \mathbf{𝐁})(\mathbf{𝐂}\otimes \mathbf{𝐃})=(\mathbf{𝐀}\mathbf{𝐂})\bullet (\mathbf{𝐁}\mathbf{𝐃})$,

   Similarly:

   $(\mathbf{𝐀}\bullet \mathbf{𝐋})(\mathbf{𝐁}\otimes \mathbf{𝐌})\cdots (\mathbf{𝐂}\otimes \mathbf{𝐒})=(\mathbf{𝐀}\mathbf{𝐁}\cdots \mathbf{𝐂})\bullet (\mathbf{𝐋}\mathbf{𝐌}\cdots \mathbf{𝐒})$,

9.  
   $c^{\text{T}}\bullet d^{\text{T}}=c^{\text{T}}\otimes d^{\text{T}}$,
   $c\ast d=c\otimes d$,
   where $c$ and $d$ are vectors,
10. $(\mathbf{𝐀}\ast c^{\text{T}})d=(\mathbf{𝐀}\ast d^{\text{T}})c$, $d^{\text{T}}(c\bullet {\mathbf{𝐀}}^{\text{T}})=c^{\text{T}}(d\bullet {\mathbf{𝐀}}^{\text{T}})$,
11.  

    $(\mathbf{𝐀}\bullet \mathbf{𝐁})(c\otimes d)=(\mathbf{𝐀}c)\circ (\mathbf{𝐁}d)$,

    where $c$ and $d$ are vectors (it is a combine of properties 3 an 8), Similarly:

    $(\mathbf{𝐀}\bullet \mathbf{𝐁})(\mathbf{𝐌}\mathbf{𝐍}c\otimes \mathbf{𝐐}\mathbf{𝐏}d)=(\mathbf{𝐀}\mathbf{𝐌}\mathbf{𝐍}c)\circ (\mathbf{𝐁}\mathbf{𝐐}\mathbf{𝐏}d),$

12.  
    ${ℱ}(C^{(1)}x\star C^{(2)}y)=({ℱ}{C}^{(1)}\bullet {ℱ}{C}^{(2)})(x\otimes y)={ℱ}{C}^{(1)}x\circ {ℱ}{C}^{(2)}y$,
    where $\star$ is vector convolution and ${ℱ}$ is the Fourier transform matrix (this result is an evolving of count sketch properties),
13.  

    $\mathbf{𝐀}\bullet \mathbf{𝐁}=(\mathbf{𝐀}\otimes {{\mathbf{1}}_{\mathbf{𝐜}}}^{\text{T}})\circ ({{\mathbf{1}}_{\mathbf{𝐤}}}^{\text{T}}\otimes \mathbf{𝐁})$,

    where $\mathbf{𝐀}$ is $r\times c$ matrix, $\mathbf{𝐁}$ is $r\times k$ matrix, ${\mathbf{1}}_{\mathbf{𝐜}}$ is a vector of 1's of length $c$, and ${\mathbf{1}}_{\mathbf{𝐤}}$ is a vector of 1's of length $k$ or

    $\mathbf{𝐌}\bullet \mathbf{𝐌}=(\mathbf{𝐌}\otimes {\mathbf{𝟏}}^{\text{T}})\circ ({\mathbf{𝟏}}^{\text{T}}\otimes \mathbf{𝐌})$,

    where $\mathbf{𝐌}$ is $r\times c$ matrix, $\circ$ means element by element multiplication and $\mathbf{𝟏}$ is a vector of 1's of length $c$.

    $\mathbf{𝐌}\bullet \mathbf{𝐌}=\mathbf{𝐌}[\circ ](\mathbf{𝐌}\otimes {\mathbf{𝟏}}^{\text{T}})$,

    where $[\circ ]$ denotes the penetrating face product of matrices. Similarly:

    $\mathbf{𝐏}\ast \mathbf{𝐍}=(\mathbf{𝐏}\otimes {\mathbf{1}}_{\mathbf{𝐜}})\circ ({\mathbf{1}}_{\mathbf{𝐤}}\otimes \mathbf{𝐍})$, where $\mathbf{𝐏}$ is $c\times r$ matrix, $\mathbf{𝐍}$ is $k\times r$ matrix,.

14.  
    ${\mathbf{W}}_{\mathbf{𝐝}}\mathbf{𝐀}=\mathbf{𝐰}\bullet \mathbf{𝐀}$,
    $vec(({\mathbf{𝐰}}^{\text{T}}\ast \mathbf{𝐀})\mathbf{𝐁})=({\mathbf{𝐁}}^{\text{T}}\ast \mathbf{𝐀})\mathbf{𝐰}$= $vec(\mathbf{𝐀}(\mathbf{𝐰}\bullet \mathbf{𝐁}))$,
    
    $\mathrm{vec}\left({\mathbf{𝐀}}^{\text{T}}{\mathbf{W}}_{\mathbf{𝐝}}\mathbf{𝐀}\right)={(\mathbf{𝐀}\bullet \mathbf{𝐀})}^{\text{T}}\mathbf{𝐰}$,
    where $\mathbf{𝐰}$ is the vector consisting of the diagonal elements of ${\mathbf{W}}_{\mathbf{𝐝}}$, $\mathrm{vec}(\mathbf{𝐀})$ means stack the columns of a matrix $\mathbf{𝐀}$ on top of each other to give a vector.
15.  

    $(\mathbf{𝐀}\bullet \mathbf{𝐋})(\mathbf{𝐁}\otimes \mathbf{𝐌})\cdots (\mathbf{𝐂}\otimes \mathbf{𝐒})(\mathbf{𝐊}\ast \mathbf{𝐓})=(\mathbf{𝐀}\mathbf{𝐁}...\mathbf{𝐂}\mathbf{𝐊})\circ (\mathbf{𝐋}\mathbf{𝐌}...\mathbf{𝐒}\mathbf{𝐓})$.

    Similarly:

    $\begin{array}{rl}(\mathbf{𝐀}\bullet \mathbf{𝐋})(\mathbf{𝐁}\otimes \mathbf{𝐌})\cdots (\mathbf{𝐂}\otimes \mathbf{𝐒})(c\otimes d)& =(\mathbf{𝐀}\mathbf{𝐁}\cdots \mathbf{𝐂}c)\circ (\mathbf{𝐋}\mathbf{𝐌}\cdots \mathbf{𝐒}d),\\ (\mathbf{𝐀}\bullet \mathbf{𝐋})(\mathbf{𝐁}\otimes \mathbf{𝐌})\cdots (\mathbf{𝐂}\otimes \mathbf{𝐒})(\mathbf{𝐏}c\otimes \mathbf{𝐐}d)& =(\mathbf{𝐀}\mathbf{𝐁}\cdots \mathbf{𝐂}\mathbf{𝐏}c)\circ (\mathbf{𝐋}\mathbf{𝐌}\cdots \mathbf{𝐒}\mathbf{𝐐}d)\end{array}$,

    where $c$ and $d$ are vectors

Examples

$\begin{array}{rl}& (\left[\begin{array}{cc}1& 0\\ 0& 1\\ 1& 0\end{array}\right]\bullet \left[\begin{array}{cc}1& 0\\ 1& 0\\ 0& 1\end{array}\right])(\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\otimes \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right])(\left[\begin{array}{cc}{\sigma }_1& 0\\ 0& {\sigma }_2\\ \end{array}\right]\otimes \left[\begin{array}{cc}{\rho }_1& 0\\ 0& {\rho }_2\\ \end{array}\right])(\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\ast \left[\begin{array}{c}{y}_1\\ y_2\end{array}\right])\\ =& (\left[\begin{array}{cc}1& 0\\ 0& 1\\ 1& 0\end{array}\right]\bullet \left[\begin{array}{cc}1& 0\\ 1& 0\\ 0& 1\end{array}\right])(\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{cc}{\sigma }_1& 0\\ 0& {\sigma }_2\\ \end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\otimes \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{cc}{\rho }_1& 0\\ 0& {\rho }_2\\ \end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right])\\ =& \left[\begin{array}{cc}1& 0\\ 0& 1\\ 1& 0\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{cc}{\sigma }_1& 0\\ 0& {\sigma }_2\\ \end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\circ \left[\begin{array}{cc}1& 0\\ 1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{cc}{\rho }_1& 0\\ 0& {\rho }_2\\ \end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right].\end{array}$

Theorem

If $M=T^{(1)}\bullet \dots \bullet T^{(c)}$, where $T^{(1)},\dots ,T^{(c)}$ are independent components a random matrix $T$ with independent identically distributed rows $T_1,\dots ,T_m\in {\mathbb{ℝ}}^d$, such that

$E[(T_{1}x{)}^2]={\Vert x\Vert }_2^2$ and $E{[(T_{1}x{)}^p]}^{\frac{1}{p}}\le \sqrt{ap}\Vert x{\Vert }_2$,

then for any vector $x$

$|{\Vert Mx\Vert }_2-{\Vert x\Vert }_2|<\epsilon {\Vert x\Vert }_2$

with probability $1-\delta$ if the quantity of rows

$m=(4a{)}^{2c}{\epsilon }^{-2}\log 1/\delta +(2ae){\epsilon }^{-1}(\log 1/\delta {)}^c.$

In particular, if the entries of $T$ are $\pm 1$ can get

$m=O({\epsilon }^{-2}\log 1/\delta +{\epsilon }^{-1}{(\frac{1}{c}\log 1/\delta )}^c)$

which matches the Johnson–Lindenstrauss lemma of $m=O({\epsilon }^{-2}\log 1/\delta )$ when $\epsilon$ is small.

Block face-splitting product

Transposed block face-splitting product in the context of a multi-face radar model

According to the definition of V. Slyusar the block face-splitting product of two partitioned matrices with a given quantity of rows in blocks

$\mathbf{𝐀}=\left[\begin{array}{cc}{\mathbf{𝐀}}_{11}& {\mathbf{𝐀}}_{12}\\ {\mathbf{𝐀}}_{21}& {\mathbf{𝐀}}_{22}\end{array}\right],\mathbf{𝐁}=\left[\begin{array}{cc}{\mathbf{𝐁}}_{11}& {\mathbf{𝐁}}_{12}\\ {\mathbf{𝐁}}_{21}& {\mathbf{𝐁}}_{22}\end{array}\right],$

can be written as :

$\mathbf{𝐀}[\bullet ]\mathbf{𝐁}=\left[\begin{array}{cc}{\mathbf{𝐀}}_{11}\bullet {\mathbf{𝐁}}_{11}& {\mathbf{𝐀}}_{12}\bullet {\mathbf{𝐁}}_{12}\\ {\mathbf{𝐀}}_{21}\bullet {\mathbf{𝐁}}_{21}& {\mathbf{𝐀}}_{22}\bullet {\mathbf{𝐁}}_{22}\end{array}\right].$

The transposed block face-splitting product (or Block column-wise version of the Khatri–Rao product) of two partitioned matrices with a given quantity of columns in blocks has a view:

$\mathbf{𝐀}[\ast ]\mathbf{𝐁}=\left[\begin{array}{cc}{\mathbf{𝐀}}_{11}\ast {\mathbf{𝐁}}_{11}& {\mathbf{𝐀}}_{12}\ast {\mathbf{𝐁}}_{12}\\ {\mathbf{𝐀}}_{21}\ast {\mathbf{𝐁}}_{21}& {\mathbf{𝐀}}_{22}\ast {\mathbf{𝐁}}_{22}\end{array}\right].$

Main properties

1. Transpose:

   ${(\mathbf{𝐀}[\ast ]\mathbf{𝐁})}^{\text{T}}={\text{A}}^{\text{T}}[\bullet ]{\mathbf{𝐁}}^{\text{T}}$

Applications

The Face-splitting product and the Block Face-splitting product used in the tensor-matrix theory of digital antenna arrays. These operations used also in:

• Artificial Intelligence and Machine learning systems to minimization of convolution and tensor sketch operations,
• A popular Natural Language Processing models, and hypergraph models of similarity,
• Generalized linear array model in statistics
• Two- and multidimensional P-spline approximation of data,
• Studies of genotype x environment interactions.

See also

• Kronecker product
• Hadamard product

References

• Khatri C. G., C. R. Rao (1968). "Solutions to some functional equations and their applications to characterization of probability distributions". Sankhya 30: 167–180. http://sankhya.isical.ac.in/search/30a2/30a2019.html. Retrieved 2008-08-21. 
• Rao C.R.; Rao M. Bhaskara (1998), Matrix Algebra and Its Applications to Statistics and Econometrics, World Scientific, pp. 216 
• Zhang X; Yang Z; Cao C. (2002), "Inequalities involving Khatri–Rao products of positive semi-definite matrices", Applied Mathematics E-notes 2: 117–124 
• Liu Shuangzhe; Trenkler Götz (2008), "Hadamard, Khatri-Rao, Kronecker and other matrix products", International Journal of Information and Systems Sciences 4: 160–177