Vi visar hur man kan approximera en datamatris A med en mycket mindre skissÃ som kan användas för att lösa en generell klass av begränsade k-rank approximationsproblem inom (1 + ) fel. Viktigt är att denna klass omfattar k-means klustring och okonstruerad låggradig approximation (dvs. Huvudkomponentanalys). Genom att reducera datapunkter till bara O(k) dimensioner påskyndar vi generellt varje exakt, ungefärlig eller heuristisk algoritm för dessa allmänt förekommande problem. För k-medel dimensionalitet minskning, ger vi (1 + ) relativa felresultat för många vanliga skissning tekniker, inklusive slumpmässig rad projektion, kolumnval, och ungefärlig SVD. För ungefärlig huvudkomponentanalys ger vi ett enkelt alternativ till kända algoritmer som har applikationer i strömningsinställningen. Dessutom utökar vi det senaste arbetet med kolonnbaserad matrisrekonstruktion, vilket ger kolumnundergrupper som inte bara "täcker" ett bra subutrymme för A, utan kan användas direkt för att beräkna detta subrymd. Slutligen, för k- medel kluster, visar vi hur man uppnår en (9 + ) approximation av Johnson- Lindenstrauss projicering data till bara O (log k/ 2 ) dimensioner. Detta är det första resultatet som utnyttjar den specifika strukturen av k-medel för att uppnå dimension oberoende av indatastorlek och sublinjär i k.
Cohen m.fl. Ref-studiens dimensionsreduktionstekniker för indatamatriser som kan användas för distribuerade k-medelvärden.
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}