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

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

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

в котором $ij$-й блок является произведением Кронекера $m_i{p}_i\otimes n_j{q}_j$ соответствующих блоков $𝐀$ и $𝐁$ при условии, что количество строк и столбцов обеих матриц равно. Размерность произведения — $\sum _i{m}_i{p}_i\times \sum _j{n}_j{q}_j$.

К примеру, если матрицы $𝐀$ и $𝐁$ имеют блочную размерность Шаблон:Nowrap:

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

то:

$𝐀\ast 𝐁=\left[\begin{array}{cc}{𝐀}_{11}\otimes {𝐁}_{11}& {𝐀}_{12}\otimes {𝐁}_{12}\\ {𝐀}_{21}\otimes {𝐁}_{21}& {𝐀}_{22}\otimes {𝐁}_{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]$.

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

Столбцовое произведение Кронекера двух матриц также принято называть произведением Хатри — Рао. Это произведение предполагает, что блоки матриц являются их столбцами. В этом случае $m_1=m$, $p_1=p$, $n=q$ и для каждого $j$: $n_j=p_j=1$. Результатом произведения является $mp\times n$-матрица, каждый столбец которой получается как произведение Кронекера соответствующих столбцов матриц $𝐀$ и $𝐁$. Например, для:

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

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

$𝐂\ast 𝐃=\left[\begin{array}{ccc}{𝐂}_1\otimes {𝐃}_1& {𝐂}_2\otimes {𝐃}_2& {𝐂}_3\otimes {𝐃}_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]$.

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

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

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

Существует альтернативная концепция произведения матриц, которая в отличие от столбцовой версии использует разбиение матриц на строки — торцевое произведение (Шаблон:Lang-en) или транспонированное произведение Хатри — Рао (Шаблон:Lang-en). Этот тип матричного умножения базируется на построчном произведении Кронекера двух и более матриц с одинаковым количеством строк. Например, для:

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

можно записать:

$𝐂\bullet 𝐃=\left[\begin{array}{c}{𝐂}_1\otimes {𝐃}_1\\ {𝐂}_2\otimes {𝐃}_2\\ {𝐂}_3\otimes {𝐃}_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]$.

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

Транспонирование (1996):

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

Коммутативность и ассоциативная операция:

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

где $𝐀$, $𝐀$ и $𝐂$ — матрицы, а $k$ — скаляр,

$a\bullet 𝐁=𝐁\bullet a$, где $a$ - вектор с количеством элементов, равным количеству строк матрицы $𝐁$,

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

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

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

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

$(𝐀\ast 𝐁{)}^{\mathsf{\text{T}}}(𝐀\ast 𝐁)=({𝐀}^{\mathsf{\text{T}}}𝐀)\circ ({𝐁}^{\mathsf{\text{T}}}𝐁)$,

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

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

• $(𝐀\circ 𝐁)\bullet (𝐂\circ 𝐃)=(𝐀\bullet 𝐂)\circ (𝐁\bullet 𝐃)$,
• $a\otimes (𝐁\bullet 𝐂)=(a\otimes 𝐁)\bullet 𝐂$, где $a$ - вектор-строка,
• $(𝐀\otimes 𝐁)(𝐂\ast 𝐃)=(𝐀𝐂)\ast (𝐁𝐃)$,
• $(𝐀\bullet 𝐁)(𝐂\otimes 𝐃)=(𝐀𝐂)\bullet (𝐁𝐃)$,
• $(𝐀\bullet 𝐋)(𝐁\otimes 𝐌)\dots (𝐂\otimes 𝐒)=(𝐀𝐁\dots 𝐂)\bullet (𝐋𝐌...𝐒)$,
• $c^{\mathsf{\text{T}}}\bullet d^{\mathsf{\text{T}}}=c^{\mathsf{\text{T}}}\otimes d^{\mathsf{\text{T}}}$,
• $c\ast d=c\otimes d$, где $c$ и $d$ являются векторами согласованной размерности,
• $(𝐀\ast c^{\mathsf{\text{T}}})d=(𝐀\ast d^{\mathsf{\text{T}}})c$, $d^{\mathsf{\text{T}}}(c\bullet {𝐀}^{\mathsf{\text{T}}})=c^{\mathsf{\text{T}}}(d\bullet {𝐀}^{\mathsf{\text{T}}})$,
• $(𝐀\bullet 𝐁)(c\otimes d)=(𝐀c)\circ (𝐁d)$, где $c$ и $d$ являются векторами согласованной размерности (следует из свойств 3 и 8),
• $(𝐀\bullet 𝐁)(𝐌𝐍c\otimes 𝐐𝐏d)=(𝐀𝐌𝐍c)\circ (𝐁𝐐𝐏d)$,
• $𝒲(C^{(1)}x\star C^{(2)}y)=(𝒲C^{(1)}\bullet 𝒲C^{(2)})(x\otimes y)=𝒲C^{(1)}x\circ 𝒲C^{(2)}y$,

где $𝒲$ является матрицей дискретного преобразования Фурье, $\star$ - символ векторной свёртки (тождество следует из свойств отсчётного скетча),

• $𝐀\bullet 𝐁=(𝐀\otimes {{\mathrm{𝟏}}_{𝐜}}^{\mathsf{\text{T}}})\circ ({{\mathrm{𝟏}}_{𝐤}}^{\mathsf{\text{T}}}\otimes 𝐁)$, где $𝐀$ - $r\times c$ матрица, $𝐁$ - $r\times k$ матрица, ${\mathrm{𝟏}}_{𝐜}$, ${\mathrm{𝟏}}_{𝐤}$ - векторы из $c$ и $k$ единиц соответственно,
• $𝐌\bullet 𝐌=(𝐌\otimes {\mathrm{𝟏}}^{\mathsf{\text{T}}})\circ ({\mathrm{𝟏}}^{\mathsf{\text{T}}}\otimes 𝐌)$, где $𝐌$ является $r\times c$ матрицей, $\circ$ - произведение Адамара и $\mathrm{𝟏}$ - вектор из $c$ единиц.
• $𝐌\bullet 𝐌=𝐌[\circ ](𝐌\otimes {\mathrm{𝟏}}^{\mathsf{\text{T}}})$, где $[\circ ]$ - символ проникающего торцевого произведения матриц.
• По аналогии, $𝐏\ast 𝐍=(𝐏\otimes {\mathrm{𝟏}}_{𝐜})\circ ({\mathrm{𝟏}}_{𝐤}\otimes 𝐍)$, где $𝐏$ - $c\times r$ матрица, $𝐍$ - $k\times r$ матрица,
• ${𝐖}_{𝐝}𝐀=𝐰\bullet 𝐀$,
• $vec(({𝐰}^{\mathsf{\text{T}}}\ast 𝐀)𝐁)=({𝐁}^{\mathsf{\text{T}}}\ast 𝐀)𝐰$,
• $vec(𝐀(𝐰\bullet 𝐁))=({𝐁}^{\mathsf{\text{T}}}\ast 𝐀)𝐰$,
• $vec({𝐀}^{\mathsf{\text{T}}}{𝐖}_{𝐝}𝐀)=(𝐀\bullet 𝐀{)}^{\mathsf{\text{T}}}𝐰$,
• $vec(𝐀{𝐖}_{𝐝}{𝐀}^{\mathsf{\text{T}}})=({𝐀}^{\mathsf{\text{T}}}\bullet {𝐀}^{\mathsf{\text{T}}}{)}^{\mathsf{\text{T}}}𝐰=(𝐀\ast 𝐀)𝐰$,

где $𝐰$ - вектор, сформированный из диагональных элементов матрицы ${𝐖}_{𝐝}$, $vec(𝐀)$ - операция формирования вектора из матрицы $𝐀$ путём расположения одного под другим её столбцов.

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

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

$(𝐀\bullet 𝐋)(𝐁\otimes 𝐌)...(𝐂\otimes 𝐒)(c\otimes d)=(𝐀𝐁...𝐂c)\circ (𝐋𝐌...𝐒d)$,

$(𝐀\bullet 𝐋)(𝐁\otimes 𝐌)...(𝐂\otimes 𝐒)(𝐏c\otimes 𝐐d)=(𝐀𝐁...𝐂𝐏c)\circ (𝐋𝐌...𝐒𝐐d)$,

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

Например:

$\begin{array}{c}\\ & (\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}$

Теорема

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

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

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

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

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

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

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

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

согласно определению, блочное торцевое произведение $𝐀[\bullet ]𝐁$ запишется в виде:

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

Аналогично, для блочного транспонированного торцевого произведения (или блочного столбцового произведения Хатри — Рао) двух матриц $𝐀[\ast ]𝐁$ с одинаковым количеством столбцов в соответствующих блоках имеет место соотношение:

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

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

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

Приложения

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

Торцевое произведение получило широкое распространение в системах машинного обучения, статистической обработке больших данных. Оно позволяет сократить объёмы вычислений при реализации метода уменьшения размерности данных, получившего наименование тензорный скетч, а также быстрого преобразования Джонсона — Линденштрауса. При этом осуществляется переход от исходной проецирующей матрицы к произведению Адамара, оперирующему матрицами меньшей размерности. Погрешность аппроксимации данных большой размерности на основе торцевого произведения матриц соответствует лемме о малом искажении. В указанном контексте идея торцевого произведенияШаблон:Переход может быть использована для решения задачи дифференциальной приватности (Шаблон:Lang-en). Кроме того, аналогичные вычисления были применены для формирования тензоров совместной встречаемости в задачах обработки естественного языка и построения гиперграфов подобия изображений.

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

См. также

• Тензорный скетчШаблон:Уточнить
• Лемма о малом искаженииШаблон:Уточнить

Литература

• Шаблон:Статья
• Шаблон:Citation
• Matrix Algebra & Its Applications to Statistics & Econometrics./C. R. Rao with M. Bhaskara Rao. — World Scientific. — 1998. — P. 216.