Abstrakt. Vi presenterar en snabb algoritm för kärnsammanfattningsproblem i högdimensioner. Dessa problem förekommer i beräkningsfysik, numerisk approximation, icke-parametrisk statistik och maskininlärning. I vårt sammanhang beror summorna på en kärnfunktion som är en parpotential definierad på en datauppsättning punkter i ett högdimensionellt Euclidean utrymme. En direkt utvärdering av den totala skalan fyrsidigt med antalet poäng. Snabba kärnsammanfattningsmetoder kan minska denna kostnad till linjär komplexitet, men de konstanter som är inblandade skalas inte väl med dimensionaliteten i datauppsättningen. De viktigaste algoritmiska komponenterna i snabba kärnsammanräkningsalgoritmer är separationen av kärnsumman mellan nära och långt fält (som är grunden för beskärning) och en effektiv och korrekt approximation av det avlägsna fältet. Vi introducerar nya metoder för beskärning och för approximering av det avlägsna fältet. Vår avlägsna approximation kräver endast kärnutvärderingar och använder inte analytiska expansioner. Beskärning sker inte med hjälp av avgränsande rutor utan snarare kombinatoriskt med hjälp av en sparifierad närmaste granne graf av indatadistributionen. Tidskomplexiteten hos vår algoritm beror linjärt på den omgivande dimensionen. Felet i algoritmen beror på den låga ungefärligheten i det avlägsna fältet, vilket i sin tur beror på kärnans funktion och den inneboende dimensionaliteten i fördelningen av punkterna. Felet i den avlägsna område approximationen beror inte på den omgivande dimensionen. Vi presenterar den nya algoritmen tillsammans med experimentella resultat som visar dess prestanda. Som en höjdpunkt rapporterar vi resultat för Gaussian kärnan summor för 100 miljoner poäng i 64 dimensioner, för en miljon poäng i 1000 dimensioner, och för problem där Gaussian kärnan har en variabel bandbredd. Så vitt vi vet är alla dessa experiment omöjliga eller oöverkomligt dyra med befintliga snabba kärnsammanfattningsmetoder.
ASKIT REF använde n-kroppsidéer för att minska tid och lagring av kärnmatrisutvärdering, vilket är en riktning för vårt framtida arbete.
ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}