Khatri–Rao product

From HandWiki
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).

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:

See also

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