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

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

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

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

и ,

то:

.

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

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

и

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

.

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

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

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

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

и

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

.

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

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

,

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

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

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

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

,
[10],
[11][13],
[14],

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

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

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

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

  • [18], где - матрица, - матрица, , - векторы из и единиц соответственно,
  • [19], где является матрицей, - произведение Адамара и - вектор из единиц.
  • , где - символ проникающего торцевого произведения матриц.
  • По аналогии, , где - матрица, - матрица,
  • [12],
  • [10],
  • [11],
  • [19],
  • ,

где - вектор, сформированный из диагональных элементов матрицы , - операция формирования вектора из матрицы путём расположения одного под другим её столбцов.

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

[10][13]
,
,

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

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

Теорема[16]

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

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

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

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

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

и

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

.

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

.

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

Приложения

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

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

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

См. также

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

Примечания

  1. Khatri C. G., C. R. Rao. Solutions to some functional equations and their applications to characterization of probability distributions (англ.) // Sankhya[англ.] : 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. Архивировано 12 июля 2020 года.
  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. Архивировано 12 июля 2020 года.
  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). Izvestiya VUZ: Radioelektronika.– 1998, Vol. 41; Number 3: 50—53. Архивировано (PDF) 27 июля 2020. Дата обращения: 27 июля 2020.
  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] Архивная копия от 26 апреля 2021 на Wayback Machine
  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. Архивировано 25 января 2020 года.
  10. 1 2 3 4 Slyusar, V. I. (1999). "A Family of Face Products of Matrices and its Properties" (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz. 35 (3): 379—384. doi:10.1007/BF02733426. Архивировано (PDF) 25 января 2020. Дата обращения: 12 июля 2020.
  11. 1 2 3 4 Миночкин А. И., Рудаков В. И., Слюсар В. И. Основы военно-технических исследований. Теория и приложения. Том. 2. Синтез средств информационного обеспечения вооружения и военной техники // Под ред. А. П. Ковтуненко. — Киев: «Гранмна». — 2012. C. 7 - 98; 354 - 521 (2012). Дата обращения: 12 июля 2020. Архивировано 25 января 2020 года.
  12. 1 2 3 4 5 6 7 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. Архивировано (PDF) 25 января 2020. Дата обращения: 12 июля 2020.
  13. 1 2 3 4 5 Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. - DOI: 10.13140/RG.2.2.31620.76164/1
  14. 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
  15. 1 2 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.
  16. 1 2 3 4 5 6 7 Ahle, Thomas; Knudsen, Jakob Almost Optimal Tensor Sketch. [2] (3 сентября 2019). Дата обращения: 11 июля 2020. Архивировано 14 июля 2020 года.
  17. Ninh, Pham; Rasmus, Pagh (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.
  18. 1 2 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.
  19. 1 2 3 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.
  20. Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Oblivious Sketching of High-Degree Polynomial Kernels. ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery. doi:10.1137/1.9781611975994.9.
  21. Bryan Bischof. Higher order co-occurrence tensors for hypergraphs via face-splitting. Published 15 February, 2020, Mathematics, Computer Science, ArXiv Архивная копия от 25 ноября 2020 на Wayback Machine
  22. 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. [3]

Литература