Abstrakt. Vi betraktar snabba kärnsummor i höga dimensioner: givet en stor uppsättning punkter i d dimensioner (med d 3) och en parpotentiell funktion (kärnfunktionen), beräknar vi en viktad summa av alla parvisa kärninteraktioner för varje punkt i uppsättningen. Direkt summering motsvarar (dense) matris-vektor multiplikation och skalor fyrsidigt med antalet punkter. Snabba kärnsammanfattningsalgoritmer minskar denna kostnad till log-lineär eller linjär komplexitet. Treecodes och Fast Multipole Methods (FMMs) levererar enorma uppfarter genom att konstruera ungefärliga representationer av interaktioner mellan punkter som är långt ifrån varandra. I algebraiska termer motsvarar dessa representationer låggradiga approximationer av block av den totala interaktionsmatrisen. Befintliga metoder kräver ett alltför stort antal kärnutvärderingar med ökande d och antal punkter i datasetet. För att ta itu med detta problem använder vi en randomiserad algebraisk metod där vi först provar raderna i ett block och sedan konstruerar dess ungefärliga, låg-rankade interpolativa nedbrytning. Vi undersöker genomförbarheten av detta tillvägagångssätt teoretiskt och experimentellt. Vi tillhandahåller ett nytt teoretiskt resultat som visar en fastare gräns på rekonstruktionsfelet från enhetliga provtagningsrader än den befintliga toppmoderna. Vi visar att vår provtagningsmetod är konkurrenskraftig med befintliga (men oöverkomligt dyra) metoder från litteraturen. Vi konstruerar också kärnmatriser för Laplacian, Gaussian, och polynomiska kärnor - allt som används i fysik och dataanalys. Vi utforskar de numeriska egenskaperna hos block av dessa matriser, och visar att de är amenable till vår strategi. Beroende på datamängden kan vår randomiserade algoritm framgångsrikt beräkna låggradiga approximationer i höga dimensioner. Vi rapporterar resultat för datamängder från fyra dimensioner upp till 1000 dimensioner.
I REF föreslås till exempel en interpolativ nedbrytning av kärnmatrisen.
Far-Field Compression for Fast Kernel Summation Methods in High Dimensions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}