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

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

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

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

и ,

то:

.

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

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

и

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

.

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

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

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

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

и

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

.

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

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

,

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

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

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

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

,
,
,
,

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

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

  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • , где и являются векторами согласованной размерности,
  • , ,
  • , где и являются векторами согласованной размерности (следует из свойств 3 и 8),
  • ,
  • ,

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

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

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

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

,
,

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

Например :


Теорема

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

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

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

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

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

и

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

.

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

.

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

Приложения

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

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

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

См. также

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

Примечания

  1. Khatri C. G., C. R. Rao . (англ.) // : 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. . Formal Aspects of Computing, 27(2):283-307, 2015.
  4. Lev-Ari, Hanoch. (EN) // Communications in Information & Systems. — 2005. — 1 января ( т. 05 , № 1 ). — С. 123—130 . — ISSN . — doi : . 12 июля 2020 года.
  5. Masiero, B.; Nascimento, V. H. // IEEE Signal Processing Letters. — 2017. — 1 мая ( т. 24 , № 5 ). — С. 525—529 . — ISSN . — doi : . — Bibcode : . 12 июля 2020 года.
  6. Vanderveen, M. C., Ng, B. C., Papadias, C. B., & Paulraj, A. (n.d.). . Conference Record of The Thirtieth Asilomar Conference on Signals, Systems and Computers. — DOI:10.1109/acssc.1996.599145
  7. Slyusar, V. I. (December 27, 1996). (PDF) . Radioelectronics and Communications Systems.– 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 от 26 апреля 2021 на Wayback Machine
  9. Slyusar, V. I. (англ.) // Proc. ICATT- 97, Kyiv : journal. — 1997. — 20 May. — P. 108—109 . 25 января 2020 года.
  10. Slyusar, V. I. (1999). (PDF) . Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz . 35 (3): 379—384. doi : . (PDF) из оригинала 25 января 2020 . Дата обращения: 12 июля 2020 .
  11. Миночкин А. И., Рудаков В. И., Слюсар В. И. C. 7 - 98; 354 - 521 (2012). Дата обращения: 12 июля 2020. 25 января 2020 года.
  12. Slyusar, V. I. (1997-09-15). (PDF) . Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv. : 73—74. (PDF) из оригинала 25 января 2020 . Дата обращения: 12 июля 2020 .
  13. Vadym Slyusar. (Lecture). April 1999. - DOI: 10.13140/RG.2.2.31620.76164/1
  14. 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. 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. Ahle, Thomas; Knudsen, Jakob . [ ] (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 : .
  18. 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 : .
  19. Currie, I. D.; Durban, M.; Eilers, P. H. C. (2006). "Generalized linear array models with applications to multidimensional smoothing". . 68 (2): 259—280. doi : .
  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 : .
  21. Bryan Bischof. Higher order co-occurrence tensors for hypergraphs via face-splitting. Published 15 February, 2020, Mathematics, Computer Science, от 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.

Литература

  • Khatri C. G., C. R. Rao. (англ.) // : journal. — 1968. — Vol. 30 . — P. 167—180 . 23 октября 2010 года.
  • Zhang X; Yang Z; Cao C. (2002), "Inequalities involving Khatri–Rao products of positive semi-definite matrices", Applied Mathematics E-notes , 2 : 117—124
  • Matrix Algebra & Its Applications to Statistics & Econometrics./C. R. Rao with M. Bhaskara Rao. — World Scientific. — 1998. — P. 216.
Источник —

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