Khatri–Rao product

Short description: Type of product of matrices

In mathematics, the Khatri–Rao product or block Kronecker product of two partitioned matrices 𝐀 and 𝐁 is defined as[1][2][3]

𝐀∗𝐁=(𝐀ij⊗𝐁ij)ij

in which the ij-th block is the mipi × njqj 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 mipi) × (Σj njqj).

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

𝐀=[𝐀11𝐀12𝐀21𝐀22]=[123456789],𝐁=[𝐁11𝐁12𝐁21𝐁22]=[147258369],

we obtain:

𝐀∗𝐁=[𝐀11⊗𝐁11𝐀12⊗𝐁12𝐀21⊗𝐁21𝐀22⊗𝐁22]=[1212214524421416457221245481].

This is a submatrix of the Tracy–Singh product[4] of the two matrices (each partition in this example is a partition in a corner of the Tracy–Singh product).

## Contents

* 1 Column-wise Kronecker product
* 2 Face-splitting product
* 3 Main properties
* 3.1 Examples
* 3.2 Theorem
* 4 Block face-splitting product
* 4.1 Main properties
* 5 Applications
* 6 See also
* 7 Notes
* 8 References

## 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 m1 = m, p1 = p, n = q and for each j: nj = qj = 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:

𝐂=[𝐂1𝐂2𝐂3]=[123456789],𝐃=[𝐃1𝐃2𝐃3]=[147258369],

so that:

𝐂∗𝐃=[𝐂1⊗𝐃1𝐂2⊗𝐃2𝐂3⊗𝐃3]=[18212102431227420428254812305473263144072214881].

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

In 1996 the column-wise Khatri–Rao product was proposed to estimate the angles of arrival (AOAs) and delays of multipath signals[8] and four coordinates of signals sources[9] 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[10] in 1996.[9][11][12][13][14]

This matrix operation was named the "face-splitting product" of matrices[11][13] 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:

𝐂=[𝐂1𝐂2𝐂3]=[123456789],𝐃=[𝐃1𝐃2𝐃3]=[147258369],

the result can be obtained:[9][11][13]

𝐂∙𝐃=[𝐂1⊗𝐃1𝐂2⊗𝐃2𝐂3⊗𝐃3]=[14728143122182032102540123048214263244872275481].

## Main properties

In the following properties, the operator

denotes the row-wise Kronecker product (face-splitting product) and the operator

denotes the column-wise Kronecker product

1. Transpose (V. Slyusar, 1996[9][11][12]):

(𝐀∙𝐁)T=AT∗𝐁T,
2. Bilinearity and associativity:[9][11][12]

𝐀∙(𝐁+𝐂)=𝐀∙𝐁+𝐀∙𝐂,(𝐁+𝐂)∙𝐀=𝐁∙𝐀+𝐂∙𝐀,(k𝐀)∙𝐁=𝐀∙(k𝐁)=k(𝐀∙𝐁),(𝐀∙𝐁)∙𝐂=𝐀∙(𝐁∙𝐂),

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

a∙𝐁=𝐁∙a,[12]
where a is a vector,
3. The mixed-product property (V. Slyusar, 1997[12]):

(𝐀∙𝐁)(𝐀T∗𝐁T)=(𝐀𝐀T)∘(𝐁𝐁T),
(𝐀∙𝐁)(𝐂∗𝐃)=(𝐀𝐂)∘(𝐁𝐃),[13]
(𝐀∙𝐁∙𝐂∙𝐃)(𝐋∗𝐌∗𝐍∗𝐏)=(𝐀𝐋)∘(𝐁𝐌)∘(𝐂𝐍)∘(𝐃𝐏)[15]
(𝐀∗𝐁)T(𝐀∗𝐁)=(𝐀T𝐀)∘(𝐁T𝐁),[16]
where ∘ denotes the Hadamard product,
4. (𝐀∘𝐁)∙(𝐂∘𝐃)=(𝐀∙𝐂)∘(𝐁∙𝐃),[12]
5. a⊗(𝐁∙𝐂)=(a⊗𝐁)∙𝐂,[9] where a is a row vector,
6. (𝐀⊗𝐁)(𝐂∗𝐃)=(𝐀𝐂)∗(𝐁𝐃),[16]
7. (𝐀⊗𝐁)∗(𝐂⊗𝐃)=𝐏[(𝐀∗𝐂)⊗(𝐁∗𝐃)], where 𝐏 is a permutation matrix.[7]
8.     (𝐀∙𝐁)(𝐂⊗𝐃)=(𝐀𝐂)∙(𝐁𝐃),[13][15]
Similarly:

(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)=(𝐀𝐁⋯𝐂)∙(𝐋𝐌⋯𝐒),
9.     cT∙dT=cT⊗dT,[12]
c∗d=c⊗d,
where c and d are vectors,
10. (𝐀∗cT)d=(𝐀∗dT)c,[17] dT(c∙𝐀T)=cT(d∙𝐀T),
11.     (𝐀∙𝐁)(c⊗d)=(𝐀c)∘(𝐁d),[18]
where c and d are vectors (it is a combine of properties 3 an 8), Similarly:

(𝐀∙𝐁)(𝐌𝐍c⊗𝐐𝐏d)=(𝐀𝐌𝐍c)∘(𝐁𝐐𝐏d),
12.     ℱ((C(1)x)⋆(C(2)y))=((ℱC(1))∙(ℱC(2)))(x⊗y)=(ℱC(1)x)∘(ℱC(2)y),
where ⋆ is vector convolution; C(1),C(2) are "count sketch" matrices; and ℱ is the Fourier transform matrix (this result is an evolving of count sketch properties[19]).

This can be generalized for appropriate matrices 𝐀,𝐁:

ℱ((𝐀x)⋆(𝐁y))=((ℱ𝐀)∙(ℱ𝐁))(x⊗y)=(ℱ𝐀x)∘(ℱ𝐁y)
because property 11 above gives us

((ℱ𝐀)∙(ℱ𝐁))(x⊗y)=(ℱ𝐀x)∘(ℱ𝐁y)
And the convolution theorem gives us

ℱ((𝐀x)⋆(𝐁y))=(ℱ𝐀x)∘(ℱ𝐁y)
13.     𝐀∙𝐁=(𝐀⊗1𝐤T)∘(1𝐜T⊗𝐁),[20]
where 𝐀 is r×c matrix, 𝐁 is r×k matrix, 1𝐜 is a vector of 1's of length c, and 1𝐤 is a vector of 1's of length k or

𝐌∙𝐌=(𝐌⊗𝟏T)∘(𝟏T⊗𝐌),[21]
where 𝐌 is r×c matrix, ∘ means element by element multiplication and 𝟏 is a vector of 1's of length c.

𝐌∙𝐌=𝐌[∘](𝐌⊗𝟏T),
where [∘] denotes the penetrating face product of matrices.[13] Similarly:

𝐏∗𝐍=(𝐏⊗1𝐤)∘(1𝐜⊗𝐍), where 𝐏 is c×r matrix, 𝐍 is k×r matrix,.
14.     W𝐝𝐀=𝐰∙𝐀,[12]
vec⁡((𝐰T∗𝐀)𝐁)=(𝐁T∗𝐀)𝐰[13]= vec⁡(𝐀(𝐰∙𝐁))= vec⁡(𝐀W𝐝𝐁),

vec⁡(𝐀TW𝐝𝐀)=(𝐀∙𝐀)T𝐰,[21]
where 𝐰 is the vector consisting of the diagonal elements of W𝐝, vec⁡(𝐀) means stack the columns of a matrix 𝐀 on top of each other to give a vector.
15.     (𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(𝐊∗𝐓)=(𝐀𝐁...𝐂𝐊)∘(𝐋𝐌...𝐒𝐓).[13][15]
Similarly:

(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(c⊗d)=(𝐀𝐁⋯𝐂c)∘(𝐋𝐌⋯𝐒d),(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(𝐏c⊗𝐐d)=(𝐀𝐁⋯𝐂𝐏c)∘(𝐋𝐌⋯𝐒𝐐d),
where c and d are vectors
16.
If 𝐁 is a diagonal matrix and 𝐛 is its main diagonal:

vec⁡(𝐀𝐁𝐂)=(𝐂T∗𝐀)𝐛
Here, vec⁡(⋅) is the column-wise vectorization operator.

### Examples

Source:[18]

([100110]∙[101001])([111−1]⊗[111−1])([σ100σ2]⊗[ρ100ρ2])([x1x2]∗[y1y2])=([100110]∙[101001])([111−1][σ100σ2][x1x2]⊗[111−1][ρ100ρ2][y1y2])=[100110][111−1][σ100σ2][x1x2]∘[101001][111−1][ρ100ρ2][y1y2].

### Theorem

Source:[18]

If M=T(1)∙…∙T(c), where T(1),…,T(c) are independent components a random matrix T with independent identically distributed rows T1,…,Tm∈ℝd, such that

E[(T1x)2]=‖x‖22 and E[(T1x)p]1p≤ap‖x‖2,

then for any vector x

|‖Mx‖2−‖x‖2|<ε‖x‖2

with probability 1−δ if the quantity of rows

m=(4a)2cε−2log⁡1/δ+(2ae)ε−1(log⁡1/δ)c.

In particular, if the entries of T are ±1 can get

m=O(ε−2log⁡1/δ+ε−1(1clog⁡1/δ)c)

which matches the Johnson–Lindenstrauss lemma of m=O(ε−2log⁡1/δ) when ε is small.

## Block face-splitting product

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

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

𝐀=[𝐀11𝐀12𝐀21𝐀22],𝐁=[𝐁11𝐁12𝐁21𝐁22],

can be written as :

𝐀[∙]𝐁=[𝐀11∙𝐁11𝐀12∙𝐁12𝐀21∙𝐁21𝐀22∙𝐁22].

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:[9][13]

𝐀[∗]𝐁=[𝐀11∗𝐁11𝐀12∗𝐁12𝐀21∗𝐁21𝐀22∗𝐁22].

### Main properties

1. Transpose:

(𝐀[∗]𝐁)T=AT[∙]𝐁T[15]

## 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,[18]
* A popular Natural Language Processing models, and hypergraph models of similarity,[22]
* Generalized linear array model in statistics[21]
* Two- and multidimensional P-spline approximation of data,[20]
* Studies of genotype x environment interactions.[23]

## See also

* Kronecker product
* Hadamard product

## Notes

1. ↑ 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://library.isical.ac.in:8080/xmlui/bitstream/handle/10263/614/68.E02.pdf. Retrieved 2008-08-21.
2. ↑ Liu, Shuangzhe (1999). "Matrix Results on the Khatri–Rao and Tracy–Singh Products". Linear Algebra and Its Applications 289 (1–3): 267–277. doi:10.1016/S0024-3795(98)10209-4.
3. ↑ Zhang X; Yang Z; Cao C. (2002), "Inequalities involving Khatri–Rao products of positive semi-definite matrices", Applied Mathematics E-notes 2: 117–124
4. ↑ Liu, Shuangzhe; Trenkler, Götz (2008). "Hadamard, Khatri-Rao, Kronecker and other matrix products". International Journal of Information and Systems Sciences 4 (1): 160–177.
5. ↑ See e.g. H. D. Macedo and J.N. Oliveira. A linear algebra approach to OLAP. Formal Aspects of Computing, 27(2):283–307, 2015.
6. ↑ Lev-Ari, Hanoch (2005-01-01). "Efficient Solution of Linear Matrix Equations with Application to Multistatic Antenna Array Processing" (in EN). Communications in Information & Systems 05 (1): 123–130. doi:10.4310/CIS.2005.v5.n1.a5. ISSN 1526-7555. http://www.ims.cuhk.edu.hk/~cis/2005.1/05.pdf.
7. ↑ 7.0 7.1 Masiero, B.; Nascimento, V. H. (2017-05-01). "Revisiting the Kronecker Array Transform". IEEE Signal Processing Letters 24 (5): 525–529. doi:10.1109/LSP.2017.2674969. ISSN 1070-9908. Bibcode: 2017ISPL...24..525M. https://zenodo.org/record/896497.
8. ↑ Vanderveen, M. C., Ng, B. C., Papadias, C. B., & Paulraj, A. (n.d.). Joint angle and delay estimation (JADE) for signals in multipath environments. Conference Record of The Thirtieth Asilomar Conference on Signals, Systems and Computers. – DOI:10.1109/acssc.1996.599145
9. ↑ 9.0 9.1 9.2 9.3 9.4 9.5 9.6 9.7 Slyusar, V. I. (December 27, 1996). "End matrix products in radar applications.". Izvestiya VUZ: Radioelektronika 41 (3): 71–75. http://slyusar.kiev.ua/en/IZV_1998_3.pdf.
10. ↑ Anna Esteve, Eva Boj & Josep Fortiana (2009): "Interaction Terms in Distance-Based Regression," Communications in Statistics – Theory and Methods, 38:19, p. 3501 [1]
11. ↑ 11.0 11.1 11.2 11.3 11.4 Slyusar, V. I. (1997-05-20). "Analytical model of the digital antenna array on a basis of face-splitting matrix products.". Proc. ICATT-97, Kyiv: 108–109. http://slyusar.kiev.ua/ICATT97.pdf.
12. ↑ 12.0 12.1 12.2 12.3 12.4 12.5 12.6 12.7 Slyusar, V. I. (1997-09-15). "New operations of matrices product for applications of radars". Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73–74. http://slyusar.kiev.ua/DIPED_1997.pdf.
13. ↑ 13.00 13.01 13.02 13.03 13.04 13.05 13.06 13.07 13.08 13.09 Slyusar, V. I. (March 13, 1998). "A Family of Face Products of Matrices and its Properties". Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz. 1999. 35 (3): 379–384. doi:10.1007/BF02733426. http://slyusar.kiev.ua/FACE.pdf.
14. ↑ Slyusar, V. I. (2003). "Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels". Radioelectronics and Communications Systems 46 (10): 9–17. http://slyusar.kiev.ua/en/IZV_2003_10.pdf.
15. ↑ 15.0 15.1 15.2 15.3 15.4 Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. – DOI: 10.13140/RG.2.2.31620.76164/1
16. ↑ 16.0 16.1 C. Radhakrishna Rao. Estimation of Heteroscedastic Variances in Linear Models.//Journal of the American Statistical Association, Vol. 65, No. 329 (Mar., 1970), pp. 161–172
17. ↑ Kasiviswanathan, Shiva Prasad, et al. «The price of privately releasing contingency tables and the spectra of random matrices with correlated rows.» Proceedings of the forty-second ACM symposium on Theory of computing. 2010.
18. ↑ 18.0 18.1 18.2 18.3 Thomas D. Ahle, Jakob Bæk Tejs Knudsen. Almost Optimal Tensor Sketch. Published 2019. Mathematics, Computer Science, ArXiv
19. ↑ Ninh, Pham (2013). "Fast and scalable polynomial kernels via explicit feature maps". SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.
20. ↑ 20.0 20.1 Eilers, Paul H.C.; Marx, Brian D. (2003). "Multivariate calibration with temperature interaction using two-dimensional penalized signal regression.". Chemometrics and Intelligent Laboratory Systems 66 (2): 159-174. doi:10.1016/S0169-7439(03)00029-7.
21. ↑ 21.0 21.1 21.2 Currie, I. D.; Durban, M.; Eilers, P. H. C. (2006). "Generalized linear array models with applications to multidimensional smoothing". Journal of the Royal Statistical Society 68 (2): 259-280. doi:10.1111/j.1467-9868.2006.00543.x.
22. ↑ Bryan Bischof. Higher order co-occurrence tensors for hypergraphs via face-splitting. Published 15 February 2020, Mathematics, Computer Science, ArXiv
23. ↑ Johannes W. R. Martini, Jose Crossa, Fernando H. Toledo, Jaime Cuevas. On Hadamard and Kronecker products in covariance structures for genotype x environment interaction.//Plant Genome. 2020;13:e20033. Page 5. [2]

## 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

* v
* t
* e

Linear algebra

Basic concepts|

* Scalar
* Vector
* Vector space
* Scalar multiplication
* Vector projection
* Linear span
* Linear map
* Linear projection
* Linear independence
* Linear combination
* Basis
* Change of basis
* Row and column vectors
* Row and column spaces
* Orthogonality
* Kernel
* Eigenvalues and eigenvectors
* Outer product
* Inner product space
* Dot product
* Transpose
* Gram–Schmidt process
* Linear equations
* Fundamental theorem

Vector algebra|

* Cross product
* Triple product
* Seven-dimensional cross product

Multilinear algebra|

* Geometric algebra
* Exterior algebra
* Bivector
* Multivector
* Tensor
* Outermorphism

Matrices|

* Block
* Decomposition
* Invertible
* Minor
* Multiplication
* Rank
* Transformation
* Cramer's rule
* Gaussian elimination
* Determinant

Algebraic constructions|

* Dual
* Direct sum
* Function space
* Quotient
* Subspace
* Tensor product

Numerical|

* Floating-point
* MATLAB
* Numerical stability
* Basic Linear Algebra Subprograms (BLAS)
* Sparse matrix
* Comparison of linear algebra libraries
* Comparison of numerical analysis software

* Category
* Outline
* Mathematics portal
* Wikibook
* Wikiversity

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Khatri–Rao product. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Khatri–Rao_product&oldid=3988396"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template