Khatri–Rao product

In mathematics, the Khatri–Rao product or block Kronecker product of two partitioned matrices $\mathbf {A}$ and $\mathbf {B}$ is defined as

$\mathbf {A} \ast \mathbf {B} =\left(\mathbf {A} _{ij}\otimes \mathbf {B} _{ij}\right)_{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 {A} =\left[{\begin{array}{c | c}\mathbf {A} _{11}&\mathbf {A} _{12}\\\hline \mathbf {A} _{21}&\mathbf {A} _{22}\end{array}}\right]=\left[{\begin{array}{c c | c}1&2&3\\4&5&6\\\hline 7&8&9\end{array}}\right],\quad \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {B} _{11}&\mathbf {B} _{12}\\\hline \mathbf {B} _{21}&\mathbf {B} _{22}\end{array}}\right]=\left[{\begin{array}{c | c c}1&4&7\\\hline 2&5&8\\3&6&9\end{array}}\right],$

we obtain:

$\mathbf {A} \ast \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {A} _{11}\otimes \mathbf {B} _{11}&\mathbf {A} _{12}\otimes \mathbf {B} _{12}\\\hline \mathbf {A} _{21}\otimes \mathbf {B} _{21}&\mathbf {A} _{22}\otimes \mathbf {B} _{22}\end{array}}\right]=\left[{\begin{array}{c c | c c}1&2&12&21\\4&5&24&42\\\hline 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).

Column-wise Kronecker product

The column-wise Kronecker product of two matrices is a special case of the Khatri-Rao product as defined above, and 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 = q_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 {C} =\left[{\begin{array}{c | c | c}\mathbf {C} _{1}&\mathbf {C} _{2}&\mathbf {C} _{3}\end{array}}\right]=\left[{\begin{array}{c | c | c}1&2&3\\4&5&6\\7&8&9\end{array}}\right],\quad \mathbf {D} =\left[{\begin{array}{c | c | c }\mathbf {D} _{1}&\mathbf {D} _{2}&\mathbf {D} _{3}\end{array}}\right]=\left[{\begin{array}{c | c | c }1&4&7\\2&5&8\\3&6&9\end{array}}\right],$

so that:

$\mathbf {C} \ast \mathbf {D} =\left[{\begin{array}{c | c | c }\mathbf {C} _{1}\otimes \mathbf {D} _{1}&\mathbf {C} _{2}\otimes \mathbf {D} _{2}&\mathbf {C} _{3}\otimes \mathbf {D} _{3}\end{array}}\right]=\left[{\begin{array}{c | c | c }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

An 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 {C} ={\begin{bmatrix}\mathbf {C} _{1}\\\hline \mathbf {C} _{2}\\\hline \mathbf {C} _{3}\\\end{bmatrix}}={\begin{bmatrix}1&2&3\\\hline 4&5&6\\\hline 7&8&9\end{bmatrix}},\quad \mathbf {D} ={\begin{bmatrix}\mathbf {D} _{1}\\\hline \mathbf {D} _{2}\\\hline \mathbf {D} _{3}\\\end{bmatrix}}={\begin{bmatrix}1&4&7\\\hline 2&5&8\\\hline 3&6&9\end{bmatrix}},$

the result can be obtained:

$\mathbf {C} \bullet \mathbf {D} ={\begin{bmatrix}\mathbf {C} _{1}\otimes \mathbf {D} _{1}\\\hline \mathbf {C} _{2}\otimes \mathbf {D} _{2}\\\hline \mathbf {C} _{3}\otimes \mathbf {D} _{3}\\\end{bmatrix}}={\begin{bmatrix}1&4&7&2&8&14&3&12&21\\\hline 8&20&32&10&25&40&12&30&48\\\hline 21&42&63&24&48&72&27&54&81\end{bmatrix}}.$

Main properties

1. Transpose (V. Slyusar, 1996):

   $\left(\mathbf {A} \bullet \mathbf {B} \right)^{\textsf {T}}={\textbf {A}}^{\textsf {T}}\ast \mathbf {B} ^{\textsf {T}}$,

2. Bilinearity and associativity:

   ${\begin{aligned}\mathbf {A} \bullet (\mathbf {B} +\mathbf {C} )&=\mathbf {A} \bullet \mathbf {B} +\mathbf {A} \bullet \mathbf {C} ,\\(\mathbf {B} +\mathbf {C} )\bullet \mathbf {A} &=\mathbf {B} \bullet \mathbf {A} +\mathbf {C} \bullet \mathbf {A} ,\\(k\mathbf {A} )\bullet \mathbf {B} &=\mathbf {A} \bullet (k\mathbf {B} )=k(\mathbf {A} \bullet \mathbf {B} ),\\(\mathbf {A} \bullet \mathbf {B} )\bullet \mathbf {C} &=\mathbf {A} \bullet (\mathbf {B} \bullet \mathbf {C} ),\\\end{aligned}}$

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

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

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

   $(\mathbf {A} \bullet \mathbf {B} )\left(\mathbf {A} ^{\textsf {T}}\ast \mathbf {B} ^{\textsf {T}}\right)=\left(\mathbf {A} \mathbf {A} ^{\textsf {T}}\right)\circ \left(\mathbf {B} \mathbf {B} ^{\textsf {T}}\right)$,

   $(\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \ast \mathbf {D} )=(\mathbf {A} \mathbf {C} )\circ (\mathbf {B} \mathbf {D} )$,

   $(\mathbf {A} \bullet \mathbf {B} \bullet \mathbf {C} \bullet \mathbf {D} )(\mathbf {L} \ast \mathbf {M} \ast \mathbf {N} \ast \mathbf {P} )=(\mathbf {A} \mathbf {L} )\circ (\mathbf {B} \mathbf {M} )\circ (\mathbf {C} \mathbf {N} )\circ (\mathbf {D} \mathbf {P} )$

   $(\mathbf {A} \ast \mathbf {B} )^{\textsf {T}}(\mathbf {A} \ast \mathbf {B} )=\left(\mathbf {A} ^{\textsf {T}}\mathbf {A} \right)\circ \left(\mathbf {B} ^{\textsf {T}}\mathbf {B} \right)$,

   where $\circ$ denotes the Hadamard product,
4. $(\mathbf {A} \circ \mathbf {B} )\bullet (\mathbf {C} \circ \mathbf {D} )=(\mathbf {A} \bullet \mathbf {C} )\circ (\mathbf {B} \bullet \mathbf {D} )$,
5. $\ a\otimes (\mathbf {B} \bullet \mathbf {C} )=(a\otimes \mathbf {B} )\bullet \mathbf {C}$, where $a$ is a row vector,
6. $(\mathbf {A} \otimes \mathbf {B} )(\mathbf {C} \ast \mathbf {D} )=(\mathbf {A} \mathbf {C} )\ast (\mathbf {B} \mathbf {D} )$,
7. $(\mathbf {A} \otimes \mathbf {B} )\ast (\mathbf {C} \otimes \mathbf {D} )=\mathbf {P} [(\mathbf {A} \ast \mathbf {C} )\otimes (\mathbf {B} \ast \mathbf {D} )]$, where $\mathbf {P}$ is a permutation matrix.
8.  

   $(\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \mathbf {C} )\bullet (\mathbf {B} \mathbf {D} )$,

   Similarly:

   $(\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )\cdots (\mathbf {C} \otimes \mathbf {S} )=(\mathbf {A} \mathbf {B} \cdots \mathbf {C} )\bullet (\mathbf {L} \mathbf {M} \cdots \mathbf {S} )$,

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

    $(\mathbf {A} \bullet \mathbf {B} )(c\otimes d)=(\mathbf {A} c)\circ (\mathbf {B} d)$,

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

    $(\mathbf {A} \bullet \mathbf {B} )(\mathbf {M} \mathbf {N} c\otimes \mathbf {Q} \mathbf {P} d)=(\mathbf {A} \mathbf {M} \mathbf {N} c)\circ (\mathbf {B} \mathbf {Q} \mathbf {P} d),$

12.  
    ${\mathcal {F}}\left((C^{(1)}x)\star (C^{(2)}y)\right)=\left(({\mathcal {F}}C^{(1)})\bullet ({\mathcal {F}}C^{(2)})\right)(x\otimes y)=({\mathcal {F}}C^{(1)}x)\circ ({\mathcal {F}}C^{(2)}y)$,
    where $\star$ is vector convolution; $C^{(1)},C^{(2)}$ are "count sketch" matrices; and ${\mathcal {F}}$ is the Fourier transform matrix (this result is an evolving of count sketch properties).
    
    This can be generalized for appropriate matrices $\mathbf {A} ,\mathbf {B}$:

    ${\mathcal {F}}\left((\mathbf {A} x)\star (\mathbf {B} y)\right)=\left(({\mathcal {F}}\mathbf {A} )\bullet ({\mathcal {F}}\mathbf {B} )\right)(x\otimes y)=({\mathcal {F}}\mathbf {A} x)\circ ({\mathcal {F}}\mathbf {B} y)$

    because property 11 above gives us

    $\left(({\mathcal {F}}\mathbf {A} )\bullet ({\mathcal {F}}\mathbf {B} )\right)(x\otimes y)=({\mathcal {F}}\mathbf {A} x)\circ ({\mathcal {F}}\mathbf {B} y)$

    And the convolution theorem gives us

    ${\mathcal {F}}\left((\mathbf {A} x)\star (\mathbf {B} y)\right)=({\mathcal {F}}\mathbf {A} x)\circ ({\mathcal {F}}\mathbf {B} y)$

13.  
    $\mathbf {A} \bullet \mathbf {B} =\left(\mathbf {A} \otimes \mathbf {1_{k}} ^{\textsf {T}}\right)\circ \left(\mathbf {1_{c}} ^{\textsf {T}}\otimes \mathbf {B} \right)$,
    where $\mathbf {A}$ is $r\times c$ matrix, $\mathbf {B}$ is $r\times k$ matrix, $\mathbf {1_{c}}$ is a vector of 1's of length $c$, and $\mathbf {1_{k}}$ is a vector of 1's of length $k$ or

    $\mathbf {M} \bullet \mathbf {M} =\left(\mathbf {M} \otimes \mathbf {1} ^{\textsf {T}}\right)\circ \left(\mathbf {1} ^{\textsf {T}}\otimes \mathbf {M} \right)$,

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

    $\mathbf {M} \bullet \mathbf {M} =\mathbf {M} [\circ ]\left(\mathbf {M} \otimes \mathbf {1} ^{\textsf {T}}\right)$,

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

    $\mathbf {P} \ast \mathbf {N} =(\mathbf {P} \otimes \mathbf {1_{k}} )\circ (\mathbf {1_{c}} \otimes \mathbf {N} )$, where $\mathbf {P}$ is $c\times r$ matrix, $\mathbf {N}$ is $k\times r$ matrix,.

14.  
    $\mathbf {W_{d}} \mathbf {A} =\mathbf {w} \bullet \mathbf {A}$,
    $\operatorname {vec} ((\mathbf {w} ^{\textsf {T}}\ast \mathbf {A} )\mathbf {B} )=(\mathbf {B} ^{\textsf {T}}\ast \mathbf {A} )\mathbf {w}$= $\operatorname {vec} (\mathbf {A} (\mathbf {w} \bullet \mathbf {B} ))$= $\operatorname {vec} (\mathbf {A} \mathbf {W_{d}} \mathbf {B} )$,
    
    $\operatorname {vec} \left(\mathbf {A} ^{\textsf {T}}\mathbf {W_{d}} \mathbf {A} \right)=\left(\mathbf {A} \bullet \mathbf {A} \right)^{\textsf {T}}\mathbf {w}$,
    where $\mathbf {w}$ is the vector consisting of the diagonal elements of $\mathbf {W_{d}}$, $\operatorname {vec} (\mathbf {A} )$ means stack the columns of a matrix $\mathbf {A}$ on top of each other to give a vector.
15.  

    $(\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )\cdots (\mathbf {C} \otimes \mathbf {S} )(\mathbf {K} \ast \mathbf {T} )=(\mathbf {A} \mathbf {B} ...\mathbf {C} \mathbf {K} )\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} \mathbf {T} )$.

    Similarly:

    ${\begin{aligned}(\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )\cdots (\mathbf {C} \otimes \mathbf {S} )(c\otimes d)&=(\mathbf {A} \mathbf {B} \cdots \mathbf {C} c)\circ (\mathbf {L} \mathbf {M} \cdots \mathbf {S} d),\\(\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )\cdots (\mathbf {C} \otimes \mathbf {S} )(\mathbf {P} c\otimes \mathbf {Q} d)&=(\mathbf {A} \mathbf {B} \cdots \mathbf {C} \mathbf {P} c)\circ (\mathbf {L} \mathbf {M} \cdots \mathbf {S} \mathbf {Q} d)\end{aligned}}$,

    where $c$ and $d$ are vectors

Examples

Source:

${\begin{aligned}&\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\left({\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}\otimes {\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}\right)\left({\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\ast {\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]{}={}&\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\otimes \,{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]{}={}&{\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\circ \,{\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}.\end{aligned}}$

Theorem

Source:

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 {R} ^{d}$, such that

$E\left[(T_{1}x)^{2}\right]=\left\|x\right\|_{2}^{2}$ and $E\left[(T_{1}x)^{p}\right]^{\frac {1}{p}}\leq {\sqrt {ap}}\|x\|_{2}$,

then for any vector $x$

$\left|\left\|Mx\right\|_{2}-\left\|x\right\|_{2}\right|<\varepsilon \left\|x\right\|_{2}$

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

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

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

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

which matches the Johnson–Lindenstrauss lemma of $m=O\left(\varepsilon ^{-2}\log 1/\delta \right)$ when $\varepsilon$ 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 {A} =\left[{\begin{array}{c | c}\mathbf {A} _{11}&\mathbf {A} _{12}\\\hline \mathbf {A} _{21}&\mathbf {A} _{22}\end{array}}\right],\quad \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {B} _{11}&\mathbf {B} _{12}\\\hline \mathbf {B} _{21}&\mathbf {B} _{22}\end{array}}\right],$

can be written as :

$\mathbf {A} [\bullet ]\mathbf {B} =\left[{\begin{array}{c | c}\mathbf {A} _{11}\bullet \mathbf {B} _{11}&\mathbf {A} _{12}\bullet \mathbf {B} _{12}\\\hline \mathbf {A} _{21}\bullet \mathbf {B} _{21}&\mathbf {A} _{22}\bullet \mathbf {B} _{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 {A} [\ast ]\mathbf {B} =\left[{\begin{array}{c | c}\mathbf {A} _{11}\ast \mathbf {B} _{11}&\mathbf {A} _{12}\ast \mathbf {B} _{12}\\\hline \mathbf {A} _{21}\ast \mathbf {B} _{21}&\mathbf {A} _{22}\ast \mathbf {B} _{22}\end{array}}\right].$

Main properties

1. Transpose:

   $\left(\mathbf {A} [\ast ]\mathbf {B} \right)^{\textsf {T}}={\textbf {A}}^{\textsf {T}}[\bullet ]\mathbf {B} ^{\textsf {T}}$

Applications

The Face-splitting product and the Block Face-splitting product used in the tensor-matrix theory of digital antenna arrays. These operations are also used 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. Archived from the original on 2010-10-23. Retrieved 2008-08-21.
• Rao C.R.; Rao M. Bhaskara (1998), Matrix Algebra and Its Applications to Statistics and Econometrics, World Scientific, p. 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