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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Произведение Хатри-Рао»)
Перейти к навигации Перейти к поиску

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

в котором -й блок является произведением Кронекера соответствующих блоков и при условии, что количество строк и столбцов обеих матриц равно. Размерность произведения — .

К примеру, если матрицы и имеют блочную размерность 2 × 2:

и ,

то:

.

Столбцовое произведение Хатри — Рао[править | править код]

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

и

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

.

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

Торцевое произведение[править | править код]

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

и

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

.

Основные свойства[править | править код]

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

,

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

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

,[11] где - вектор с количеством элементов, равным количеству строк матрицы ,

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

,
,
[12][10],
[13],

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

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

  • [11],
  • [7],
  • [13],
  • [12],
  • ,
  • [11],
  • , где и являются векторами согласованной размерности,
  • [14], где и являются векторами согласованной размерности (следует из свойств 3 и 8),
  • ,

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

[12]
,
,

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

Например[14]:


Теорема[14][править | править код]

Если , где представляют собой независимые включения матрицы , содержащей строки , такие, что и ,
то с вероятностью для любого вектора , если количество строк
.

В частности, если элементами матрицы являются числа , можно получить , что при малых значениях согласуется с предельным значением леммы Джонсона-Линденштрауса о распределении.

Блочное торцевое произведение[править | править код]

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

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

и

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

.

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

.

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

Приложения[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  1. Khatri C. G., C. R. Rao. Solutions to some functional equations and their applications to characterization of probability distributions (англ.) // Sankhya[en] : journal. — 1968. — Vol. 30. — P. 167—180. Архивировано 23 октября 2010 года.
  2. Zhang X; Yang Z & Cao C. (2002), Inequalities involving Khatri–Rao products of positive semi-definite matrices, Applied Mathematics E-notes Т. 2: 117–124 
  3. 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.
  4. Lev-Ari, Hanoch. Efficient Solution of Linear Matrix Equations with Application to Multistatic Antenna Array Processing (EN) // Communications in Information & Systems. — 2005. — 1 января (т. 05, № 1). — С. 123—130. — ISSN 1526-7555. — doi:10.4310/CIS.2005.v5.n1.a5.
  5. Masiero, B.; Nascimento, V. H. Revisiting the Kronecker Array Transform // IEEE Signal Processing Letters. — 2017. — 1 мая (т. 24, № 5). — С. 525—529. — ISSN 1070-9908. — doi:10.1109/LSP.2017.2674969. — Bibcode2017ISPL...24..525M.
  6. 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
  7. 1 2 3 4 5 6 7 8 Slyusar, V. I. (December 27, 1996). “End products in matrices in radar applications” (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53.
  8. Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 [1]
  9. 1 2 3 Slyusar, V. I. Analytical model of the digital antenna array on a basis of face-splitting matrix products (англ.) // Proc. ICATT- 97, Kyiv : journal. — 1997. — 20 May. — P. 108—109.
  10. 1 2 3 Миночкин А. И., Рудаков В. И., Слюсар В. И. Основы военно-технических исследований. Теория и приложения. Том. 2. Синтез средств информационного обеспечения вооружения и военной техники // Под ред. А. П. Ковтуненко. — Киев: «Гранмна». — 2012. C. 7 - 98; 354 - 521 (2012).
  11. 1 2 3 4 5 6 Slyusar, V. I. (1997-09-15). “New operations of matrices product for applications of radars” (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74.
  12. 1 2 3 4 5 Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. - DOI: 10.13140/RG.2.2.31620.76164/1
  13. 1 2 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
  14. 1 2 3 4 5 6 7 Ahle, Thomas Almost Optimal Tensor Sketch. [[2]] (3 сентября 2019). Дата обращения 11 июля 2020.
  15. (2020) "Oblivious Sketching of High-Degree Polynomial Kernels" in ACM-SIAM Symposium on Discrete Algorithms., Association for Computing Machinery. DOI:10.1137/1.9781611975994.9. 
  16. 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.
  17. Bryan Bischof. Higher order co-occurrence tensors for hypergraphs via face-splitting. Published 15 February, 2020, Mathematics, Computer Science, ArXiv
  18. Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.

Литература[править | править код]