Dílo Khatri - Rao

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. dubna 2022; kontroly vyžadují 4 úpravy .

Součin Khatri-Rao  je operace násobení matic definovaná výrazem [1] [2] :

ve kterém -tý blok je Kroneckerův součin odpovídajících bloků a za předpokladu, že počet řádků a sloupců obou matic je stejný. Rozměr díla je .

Pokud například matice a mají blokový rozměr 2 × 2 :

a ,

pak:

.

Khatri-Rao sloupcový produkt

Kroneckerův součin dvou matic se také nazývá součin Khatri-Rao. Tento součin předpokládá, že bloky matic jsou jejich sloupce. V tomto případě , a pro každou : . Výsledkem součinu je -matice, jejíž každý sloupec se získá jako Kroneckerův součin odpovídajících sloupců matic a . Například pro:

a

sloupcový produkt:

.

Sloupcová verze produktu Khatri-Rao se používá v lineární algebře pro analytické zpracování dat [3] a optimalizaci řešení problému inverze diagonální matice [4] [5] ; v roce 1996 bylo navrženo jeho použití při popisu problému společného odhadu úhlu příchodu a doby zpoždění signálů v poli digitální antény [6] , stejně jako při popisu odezvy 4-souřadnicového radaru [ 7] .

Konečný produkt

Existuje alternativní pojetí součinu matic, které na rozdíl od sloupcové verze využívá rozdělení matic do řádků [8]  — součin face-splitting [7] [ 9] [ 10] nebo transponovaný součin Khatri- Rao ( Anglicky  transponovaný produkt Khatri-Rao ) [11] . Tento typ násobení matic je založen na Kroneckerově řádkovém součinu dvou nebo více matic se stejným počtem řádků. Například pro:  

a

lze napsat [7] :

.

Základní vlastnosti

Transponovat (1996 [7] [9] [12] ):

,

Komutativnost a asociativní operace [7] [9] [12] :

kde , a jsou matice a je skalár,

, [12] kde je vektor s počtem prvků rovným počtu řádků matice ,

Vlastnost smíšeného produktu (1997 [12] ):

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

kde označuje produkt Hadamard .

Dále jsou splněny následující vlastnosti:

kde je matice diskrétní Fourierovy transformace , je symbol vektorové konvoluce (identita vyplývá z vlastností referenční skici [17] ),

kde je vektor vytvořený z diagonálních prvků matice , je operace vytvoření vektoru z matice umístěním jejích sloupců pod sebe.

Absorpční vlastnost produktu Kronecker:

[10] [13] , ,

kde a jsou vektory konzistentní dimenze.

Například [16] :


Věta [16]

If , where jsou nezávislé inkluze matice obsahující řádky takové, že a , pak s pravděpodobností pro libovolný vektor , pokud počet řádků .

Konkrétně, pokud jsou prvky matice čísla , lze získat , což je pro malé hodnoty v souladu s limitní hodnotou lemmatu Johnson-Lindenstraussova rozdělení.

Blokovat koncový produkt

Pro blokové matice se stejným počtem sloupců v příslušných blocích:

a

podle definice [7] lze koncový produkt bloku zapsat jako:

.

Podobně pro blokově transponovaný konečný produkt (nebo blokový sloupcový produkt Khatri - Rao ) dvou matic se stejným počtem sloupců v odpovídajících blocích platí následující vztah [7] :

.

Provede se vlastnost transpozice [13] :

Aplikace

Rodina konečných produktů matic se používá v teorii tenzorové matice digitálních anténních polí pro radiotechnické systémy [11] .

Konečný produkt se rozšířil v systémech strojového učení, statistickém zpracování velkých dat [16] . Umožňuje snížit množství výpočtů při implementaci metody redukce rozměrů dat, nazývané tenzorová skica [16] , a také rychlé Johnson-Lindenstraussovy transformace [16] . V tomto případě se provede přechod z původní promítací matice na Hadamardův součin , který pracuje s maticemi menšího rozměru. Aproximační chyba vysokorozměrných dat na základě konečného součinu matic odpovídá lemmatu malého zkreslení [16] [20] . V této souvislosti lze myšlenku konečného produktu použít k vyřešení problému rozdílného soukromí [ 15 ] .  Kromě toho byly podobné výpočty použity k vytvoření tenzorů společného výskytu ve zpracování přirozeného jazyka a hypergrafech podobnosti obrázků [21] .

Konečný produkt se používá pro P-spline aproximaci [18] , vytváření zobecněných lineárních modelů datových polí (GLAM) během jejich statistického zpracování [19] a lze jej použít k efektivní implementaci jaderné metody strojového učení , stejně jako ke studiu interakce genotypů s prostředím. [22]

Viz také

Poznámky

  1. Khatri CG, ČR Rao . Řešení některých funkcionálních rovnic a jejich aplikace k charakterizaci rozdělení pravděpodobnosti  (anglicky)  // Sankhya  : journal. - 1968. - Sv. 30 . - S. 167-180 . Archivováno z originálu 23. října 2010.
  2. Zhang X; Yang Z & Cao C. (2002), Nerovnosti zahrnující Khatri-Rao produkty pozitivních semi-definitních matic, Applied Mathematics E-notes sv. 2: 117–124 
  3. Viz např. HD Macedo a JN Oliveira. Přístup lineární algebry k OLAP . Formal Aspects of Computing, 27(2):283-307, 2015.
  4. Lev-Ari, Hanoch. Efektivní řešení lineárních maticových rovnic s aplikací na zpracování multistatických anténních polí // Komunikace v informačních systémech. - 2005. - 1. ledna ( roč. 05 , č. 1 ). - S. 123-130 . — ISSN 1526-7555 . - doi : 10.4310/CIS.2005.v5.n1.a5 .
  5. Masiero, B.; Nascimento, VH Revisiting the Kronecker Array Transform  // IEEE Signal Processing Letters. - 2017. - 1. května ( roč. 24 , č. 5 ). - S. 525-529 . — ISSN 1070-9908 . - doi : 10.1109/LSP.2017.2674969 . - .
  6. Vanderveen, MC, Ng, BC, Papadias, CB, & Paulraj, A. (n.d.). Společný odhad úhlu a zpoždění (JADE) pro signály v prostředí s více cestami . Záznam z konference Třicáté Asilomarské konference o signálech, systémech a počítačích. — DOI:10.1109/acssc.1996.599145
  7. 1 2 3 4 5 6 7 8 Slyusar, VI (27. prosince 1996). “Koncové produkty v matricích v radarových aplikacích” (PDF) . Radioelektronika a komunikační systémy. – 1998, sv. 41; Číslo 3 : 50-53. Archivováno (PDF) z originálu dne 27.07.2020 . Staženo 27.07.2020 . Použitý zastaralý parametr |deadlink=( nápověda )
  8. Anna Esteve, Eva Boj & Josep Fortiana (2009): Interakční termíny v regresi založené na vzdálenosti, komunikace ve statistice – teorie a metody, 38:19, P. 3501 [1] Archivováno 26. dubna 2021 na Wayback Machine
  9. 1 2 3 Slyusar, VI Analytický model pole digitálních antén na bázi produktů face-splitting matrix   // Proc . ICATT-97, Kyjev: deník. - 1997. - 20. května. - str. 108-109 .
  10. 1 2 3 4 Slyusar, VI (1999). „Rodina maticových produktů pro tváře a její vlastnosti“ (PDF) . Kybernetika a systémová analýza C/C of Cybernetika I Sistemnyi Analiz . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Archivováno z originálu (PDF) dne 25. ledna 2020 . Staženo 12. července 2020 .
  11. 1 2 3 4 Minochkin A. I., Rudakov V. I., Slyusar V. I. Základy vojensko-technického výzkumu. Teorie a aplikace. Hlasitost. 2. Syntéza prostředků informační podpory zbraní a vojenské techniky // Ed. A. P. Kovtuněnko. - Kyjev: "Granmna". - 2012. C. 7 - 98; 354 - 521 (2012). Staženo 12. července 2020. Archivováno z originálu dne 25. ledna 2020.
  12. 1 2 3 4 5 6 7 Slyusar, VI (15. 9. 1997). „Nové operace maticového produktu pro aplikace radarů“ (PDF) . Proč. Přímé a inverzní problémy teorie elektromagnetických a akustických vln (DIPED-97), Lvov. : 73-74. Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-07-12 . Použitý zastaralý parametr |deadlink=( nápověda )
  13. 1 2 3 4 5 Vadym Slyusar. Nové maticové operace pro DSP (přednáška). Duben 1999. – DOI: 10.13140/RG.2.2.31620.76164/1
  14. 1 2 C. Radhakrishna Rao . Odhad heteroscedastických odchylek v lineárních modelech.//Journal of the American Statistical Association, Vol. 65, č.p. 329 (březen 1970), str. 161-172
  15. 1 2 Kasiviswanathan, Shiva Prasad, et al. "Cena za soukromé zveřejnění kontingenčních tabulek a spekter náhodných matic s korelovanými řádky." Sborník příspěvků z 42. sympozia ACM na téma Teorie výpočetní techniky. 2010.
  16. 1 2 3 4 5 6 7 Ahle, Thomas; Knudsen, Jakob Téměř optimální náčrt tenzoru . [ [2] ] (3. září 2019). Staženo 11. července 2020. Archivováno z originálu dne 14. července 2020.
  17. Ninh, Pham; Rasmus, Pagh (2013). Rychlá a škálovatelná polynomiální jádra prostřednictvím explicitních map funkcí . Mezinárodní konference SIGKDD o objevování znalostí a dolování dat. Asociace pro výpočetní techniku. DOI : 10.1145/2487575.2487591 .
  18. 12 Eilers , Paul H.C.; Marx, Brian D. (2003). „Vícerozměrná kalibrace s teplotní interakcí pomocí dvourozměrné regrese penalizovaného signálu“. Chemometrie a inteligentní laboratorní systémy . 66 (2): 159&ndash, 174. DOI : 10.1016/S0169-7439(03)00029-7 .
  19. 1 2 3 Currie, ID; Durban, M.; Eilers, PHC (2006). „Zobecněné modely lineárních polí s aplikacemi pro vícerozměrné vyhlazování“. Journal of the Royal Statistical Society . 68 (2): 259&ndash, 280. DOI : 10.1111/j.1467-9868.2006.00543.x .
  20. Ahle, Thomas; Kapralov, Michael; Knudsen, Jacob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Oblivious Sketching of High-Degree Polynomial Kernels . Symposium ACM-SIAM o diskrétních algoritmech. Asociace pro výpočetní techniku. DOI : 10.1137/1.9781611975994.9 .
  21. Bryan Bischoff. Tenzory společného výskytu vyššího řádu pro hypergrafy prostřednictvím rozdělení tváře. Publikováno 15. února 2020, Matematika, Počítačová věda, ArXiv Archivováno 25. listopadu 2020 na Wayback Machine
  22. Johannes WR Martini, Jose Crossa, Fernando H. Toledo, Jaime Cuevas. O produktech Hadamard a Kronecker v kovariančních strukturách pro interakci genotyp x prostředí.//Genom rostlin. 2020;13:e20033. Strana 5. [3]

Literatura