Произведение Хатри — Рао

Произведение Хатри — Рао — операция умножения матриц, определяемая выражением^[1][2]:

${\displaystyle \mathbf {A} \ast \mathbf {B} =\left(\mathbf {A} _{ij}\otimes \mathbf {B} _{ij}\right)_{ij}}$

в котором ${\displaystyle ij}$-й блок является произведением Кронекера ${\displaystyle m_{i}p_{i}\otimes n_{j}q_{j}}$ соответствующих блоков ${\displaystyle \mathbf {A} }$ и ${\displaystyle \mathbf {B} }$ при условии, что количество строк и столбцов обеих матриц равно. Размерность произведения — ${\displaystyle \sum _{i}{m_{i}p_{i}}\times \sum _{j}{n_{j}q_{j}}}$.

К примеру, если матрицы ${\displaystyle \mathbf {A} }$ и ${\displaystyle \mathbf {B} }$ имеют блочную размерность 2 × 2:

${\displaystyle \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]}$ и ${\displaystyle \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]}$,

то:

${\displaystyle \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]}$.

Столбцовое произведение Хатри — Рао

Столбцовое произведение Кронекера двух матриц также принято называть произведением Хатри — Рао. Это произведение предполагает, что блоки матриц являются их столбцами. В этом случае ${\displaystyle m_{1}=m}$, ${\displaystyle p_{1}=p}$, ${\displaystyle n=q}$ и для каждого ${\displaystyle j}$: ${\displaystyle n_{j}=p_{j}=1}$. Результатом произведения является ${\displaystyle mp\times n}$-матрица, каждый столбец которой получается как произведение Кронекера соответствующих столбцов матриц ${\displaystyle \mathbf {A} }$ и ${\displaystyle \mathbf {B} }$. Например, для:

${\displaystyle \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]}$ и ${\displaystyle \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]}$

столбцовое произведение:

${\displaystyle \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]}$.

Столбцовая версия произведения Хатри — Рао используется в линейной алгебре для аналитической обработки данных^[3] и оптимизации решений проблемы обращения диагональных матриц^[4][5]; в 1996 году его было предложено использовать в описании задачи совместного оценивания угла прихода и времени задержки сигналов в цифровой антенной решётке^[6], а также для описания отклика 4-координатного радара^[7].

Торцевое произведение

Торцевое произведение матриц

Существует альтернативная концепция произведения матриц, которая в отличие от столбцовой версии использует разбиение матриц на строки^[8] — торцевое произведение (англ. face-splitting product)^[7][9][10] или транспонированное произведение Хатри — Рао (англ. transposed Khatri — Rao product)^[11]. Этот тип матричного умножения базируется на построчном произведении Кронекера двух и более матриц с одинаковым количеством строк. Например, для:

${\displaystyle \mathbf {C} =\left[{\begin{array}{c c}\mathbf {C} _{1}\\\hline \mathbf {C} _{2}\\\hline \mathbf {C} _{3}\\\end{array}}\right]=\left[{\begin{array}{c c c}1&2&3\\\hline 4&5&6\\\hline 7&8&9\end{array}}\right]}$ и ${\displaystyle \mathbf {D} =\left[{\begin{array}{c }\mathbf {D} _{1}\\\hline \mathbf {D} _{2}\\\hline \mathbf {D} _{3}\\\end{array}}\right]=\left[{\begin{array}{c c c }1&4&7\\\hline 2&5&8\\\hline 3&6&9\end{array}}\right]}$

можно записать^[7]:

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

Основные свойства

Транспонирование (1996^[7][9][12]):

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

Коммутативность и ассоциативная операция^[7][9][12]:

${\displaystyle {\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}}}$

где ${\displaystyle \mathbf {A} }$, ${\displaystyle \mathbf {A} }$ и ${\displaystyle \mathbf {C} }$ — матрицы, а ${\displaystyle k}$ — скаляр,

${\displaystyle a\bullet \mathbf {B} =\mathbf {B} \bullet a}$,^[12] где ${\displaystyle a}$ - вектор с количеством элементов, равным количеству строк матрицы ${\displaystyle \mathbf {B} }$,

Свойство смешанного произведения (1997^[12]):

${\displaystyle (\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)}$,

${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \ast \mathbf {D} )=(\mathbf {A} \mathbf {C} )\circ (\mathbf {B} \mathbf {D} )}$^[10],

${\displaystyle (\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} )}$^[11][13],

${\displaystyle (\mathbf {A} \ast \mathbf {B} )^{\textsf {T}}(\mathbf {A} \ast \mathbf {B} )=(\mathbf {A} ^{\textsf {T}}\mathbf {A} )\circ (\mathbf {B} ^{\textsf {T}}\mathbf {B} )}$^[14],

где ${\displaystyle \circ }$ обозначает произведение Адамара.

Также выполняются следующие свойства:

• ${\displaystyle (\mathbf {A} \circ \mathbf {B} )\bullet (\mathbf {C} \circ \mathbf {D} )=(\mathbf {A} \bullet \mathbf {C} )\circ (\mathbf {B} \bullet \mathbf {D} )}$^[12],
• ${\displaystyle \ a\otimes (\mathbf {B} \bullet \mathbf {C} )=(a\otimes \mathbf {B} )\bullet \mathbf {C} }$,^[7] где ${\displaystyle a}$ - вектор-строка,
• ${\displaystyle (\mathbf {A} \otimes \mathbf {B} )(\mathbf {C} \ast \mathbf {D} )=(\mathbf {A} \mathbf {C} )\ast (\mathbf {B} \mathbf {D} )}$^[14],
• ${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \mathbf {C} )\bullet (\mathbf {B} \mathbf {D} )}$^[13],
• ${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )\dots (\mathbf {C} \otimes \mathbf {S} )=(\mathbf {A} \mathbf {B} \dots \mathbf {C} )\bullet (\mathbf {L} \mathbf {M} ...\mathbf {S} )}$,
• ${\displaystyle c^{\textsf {T}}\bullet d^{\textsf {T}}=c^{\textsf {T}}\otimes d^{\textsf {T}}}$^[12],
• ${\displaystyle c\ast d=c\otimes d}$, где ${\displaystyle c}$ и ${\displaystyle d}$ являются векторами согласованной размерности,
• ${\displaystyle (\mathbf {A} \ast c^{\textsf {T}})d=(\mathbf {A} \ast d^{\textsf {T}})c}$^[15], ${\displaystyle d^{\textsf {T}}(c\bullet \mathbf {A} ^{\textsf {T}})=c^{\textsf {T}}(d\bullet \mathbf {A} ^{\textsf {T}})}$,
• ${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(c\otimes d)=(\mathbf {A} c)\circ (\mathbf {B} d)}$^[16], где ${\displaystyle c}$ и ${\displaystyle d}$ являются векторами согласованной размерности (следует из свойств 3 и 8),
• ${\displaystyle (\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)}$,
• ${\displaystyle {\mathcal {W}}(C^{(1)}x\star C^{(2)}y)=({\mathcal {W}}C^{(1)}\bullet {\mathcal {W}}C^{(2)})(x\otimes y)={\mathcal {W}}C^{(1)}x\circ {\mathcal {W}}C^{(2)}y}$,

где ${\displaystyle {\mathcal {W}}}$ является матрицей дискретного преобразования Фурье, ${\displaystyle \star }$ - символ векторной свёртки (тождество следует из свойств отсчётного скетча^[17]),

• ${\displaystyle \mathbf {A} \bullet \mathbf {B} =(\mathbf {A} \otimes \mathbf {1_{c}} ^{\textsf {T}})\circ (\mathbf {1_{k}} ^{\textsf {T}}\otimes \mathbf {B} )}$^[18], где ${\displaystyle \mathbf {A} }$ - ${\displaystyle r\times c}$ матрица, ${\displaystyle \mathbf {B} }$ - ${\displaystyle r\times k}$ матрица, ${\displaystyle \mathbf {1_{c}} }$, ${\displaystyle \mathbf {1_{k}} }$ - векторы из ${\displaystyle c}$ и ${\displaystyle k}$ единиц соответственно,
• ${\displaystyle \mathbf {M} \bullet \mathbf {M} =(\mathbf {M} \otimes \mathbf {1} ^{\textsf {T}})\circ (\mathbf {1} ^{\textsf {T}}\otimes \mathbf {M} )}$^[19], где ${\displaystyle \mathbf {M} }$ является ${\displaystyle r\times c}$ матрицей, ${\displaystyle \circ }$ - произведение Адамара и ${\displaystyle \mathbf {1} }$ - вектор из ${\displaystyle c}$ единиц.
• ${\displaystyle \mathbf {M} \bullet \mathbf {M} =\mathbf {M} [\circ ](\mathbf {M} \otimes \mathbf {1} ^{\textsf {T}})}$, где ${\displaystyle [\circ ]}$ - символ проникающего торцевого произведения матриц.
• По аналогии, ${\displaystyle \mathbf {P} \ast \mathbf {N} =(\mathbf {P} \otimes \mathbf {1_{c}} )\circ (\mathbf {1_{k}} \otimes \mathbf {N} )}$, где ${\displaystyle \mathbf {P} }$ - ${\displaystyle c\times r}$ матрица, ${\displaystyle \mathbf {N} }$ - ${\displaystyle k\times r}$ матрица,
• ${\displaystyle \mathbf {W_{d}} \mathbf {A} =\mathbf {w} \bullet \mathbf {A} }$^[12],
• ${\displaystyle vec((\mathbf {w} ^{\textsf {T}}\ast \mathbf {A} )\mathbf {B} )=(\mathbf {B} ^{\textsf {T}}\ast \mathbf {A} )\mathbf {w} }$^[10],
• ${\displaystyle vec(\mathbf {A} (\mathbf {w} \bullet \mathbf {B} ))=(\mathbf {B} ^{\textsf {T}}\ast \mathbf {A} )\mathbf {w} }$^[11],
• ${\displaystyle vec(\mathbf {A} ^{\textsf {T}}\mathbf {W_{d}} \mathbf {A} )=(\mathbf {A} \bullet \mathbf {A} )^{\textsf {T}}\mathbf {w} }$^[19],
• ${\displaystyle vec(\mathbf {A} \mathbf {W_{d}} \mathbf {A} ^{\textsf {T}})=(\mathbf {A} ^{\textsf {T}}\bullet \mathbf {A} ^{\textsf {T}})^{\textsf {T}}\mathbf {w} =(\mathbf {A} \ast \mathbf {A} )\mathbf {w} }$,

где ${\displaystyle \mathbf {w} }$ - вектор, сформированный из диагональных элементов матрицы ${\displaystyle \mathbf {W_{d}} }$, ${\displaystyle vec(\mathbf {A} )}$ - операция формирования вектора из матрицы ${\displaystyle \mathbf {A} }$ путём расположения одного под другим её столбцов.

Свойство поглощения произведения Кронекера:

${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\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} )}$^[10][13]

${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )(c\otimes d)=(\mathbf {A} \mathbf {B} ...\mathbf {C} c)\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} d)}$,

${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )(\mathbf {P} c\otimes \mathbf {Q} d)=(\mathbf {A} \mathbf {B} ...\mathbf {C} \mathbf {P} c)\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} \mathbf {Q} d)}$,

где ${\displaystyle c}$ и ${\displaystyle d}$ являются векторами согласованной размерности.

Например^[16]:

${\displaystyle {\begin{aligned}\\&\quad \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]&\quad =\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]&\quad ={\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}}}$

Теорема^[16]

Если ${\displaystyle M=T^{(1)}\bullet \dots \bullet T^{(c)}}$, где ${\displaystyle T^{(1)},\dots ,T^{(c)}}$ представляют собой независимые включения матрицы ${\displaystyle T}$, содержащей строки ${\displaystyle T_{1},\dots ,T_{m}\in \mathbb {R} ^{d}}$, такие, что ${\displaystyle E[(T_{1}x)^{2}]=\|x\|_{2}^{2}}$ и ${\displaystyle E[(T_{1}x)^{p}]^{1/p}\leq {\sqrt {ap}}\|x\|_{2}}$,

то ${\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}$ с вероятностью ${\displaystyle 1-\delta }$ для любого вектора ${\displaystyle x}$, если количество строк

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

В частности, если элементами матрицы ${\displaystyle T}$ являются числа ${\displaystyle \pm 1}$, можно получить ${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta +\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$, что при малых значениях ${\displaystyle \varepsilon }$ согласуется с предельным значением ${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta )}$ леммы Джонсона-Линденштрауса о распределении.

Блочное торцевое произведение

Примение блочного транспонированного торцевого произведения для описания отклика многогранной цифровой антенной решётки^[13]

Для блочных матриц с одинаковым количеством столбцов в соответствующих блоках:

${\displaystyle \mathbf {A} =\left[{\begin{array}{c | c}\mathbf {A} _{11}&\mathbf {A} _{12}\\\hline \mathbf {A} _{21}&\mathbf {A} _{22}\end{array}}\right]}$ и ${\displaystyle \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {B} _{11}&\mathbf {B} _{12}\\\hline \mathbf {B} _{21}&\mathbf {B} _{22}\end{array}}\right]}$

согласно определению^[7], блочное торцевое произведение ${\displaystyle \mathbf {A} [\bullet ]\mathbf {B} }$ запишется в виде:

${\displaystyle \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]}$.

Аналогично, для блочного транспонированного торцевого произведения (или блочного столбцового произведения Хатри — Рао) двух матриц ${\displaystyle \mathbf {A} [\ast ]\mathbf {B} }$ с одинаковым количеством столбцов в соответствующих блоках имеет место соотношение^[7]:

${\displaystyle \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]}$.

Выполняется свойство транспонирования^[13]:

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

Приложения

Семейство торцевых произведений матриц используется в тензорно-матричной теории цифровых антенных решёток для радиотехнических систем^[11].

Торцевое произведение получило широкое распространение в системах машинного обучения, статистической обработке больших данных^[16]. Оно позволяет сократить объёмы вычислений при реализации метода уменьшения размерности данных, получившего наименование тензорный скетч^[16], а также быстрого преобразования Джонсона — Линденштрауса^[16]. При этом осуществляется переход от исходной проецирующей матрицы к произведению Адамара, оперирующему матрицами меньшей размерности. Погрешность аппроксимации данных большой размерности на основе торцевого произведения матриц соответствует лемме о малом искажении^[16][20]. В указанном контексте идея торцевого произведения➤ может быть использована для решения задачи дифференциальной приватности (англ. differential privacy)^[15]. Кроме того, аналогичные вычисления были применены для формирования тензоров совместной встречаемости в задачах обработки естественного языка и построения гиперграфов подобия изображений^[21].

Торцевое произведение применяется для P-сплайн аппроксимации^[18], построения обобщённых линейных моделей массивов данных (GLAM) при их статистической обработке^[19] и может быть использовано для эффективной реализации ядерного метода машинного обучения, а также изучения взаимодействия генотипов с окружающей средой.^[22]

См. также

• Тензорный скетч^{[уточнить]}
• Лемма о малом искажении^{[уточнить]}