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

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

Произведение Хатри — Рао — операция умножения матриц, определяемая выражением[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], ,
  • [15], где и являются векторами согласованной размерности (следует из свойств 3 и 8),
  • ,
  • ,

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

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

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

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

[12]
,
,

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

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


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

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

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

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

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

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

и

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

.

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

.

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

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

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

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

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

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

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

  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 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.
  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 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.
  15. 1 2 3 4 5 6 7 Ahle, Thomas Almost Optimal Tensor Sketch. [[2]] (3 сентября 2019). Дата обращения 11 июля 2020.
  16. (2013) "Fast and scalable polynomial kernels via explicit feature maps" in SIGKDD international conference on Knowledge discovery and data mining., Association for Computing Machinery. DOI:10.1145/2487575.2487591. 
  17. 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&ndash, 174. DOI:10.1016/S0169-7439(03)00029-7.
  18. 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&ndash, 280. DOI:10.1111/j.1467-9868.2006.00543.x.
  19. (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. 
  20. Bryan Bischof. Higher order co-occurrence tensors for hypergraphs via face-splitting. Published 15 February, 2020, Mathematics, Computer Science, ArXiv
  21. Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.

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