Många dataanalysapplikationer hanterar stora matriser och innebär att tillnärma matrisen med hjälp av ett litet antal "komponenter". Vanligtvis är dessa komponenter linjära kombinationer av raderna och kolumnerna i matrisen, och är därför svåra att tolka i termer av de ursprungliga egenskaperna hos indata. I detta dokument föreslår vi och studerar matris approximationer som uttryckligen uttrycks i termer av ett litet antal kolumner och / eller rader av datamatrisen, och därmed mer mottaglig för tolkning i termer av de ursprungliga uppgifterna. Våra viktigaste algoritmiska resultat är två randomiserade algoritmer som tar som ingång en m × n matris A och en rank parameter k. I vår första algoritm, C väljs, och vi låter A ′ = CC + A, där C + är Moore-Penrose generaliserade invers av C. I vår andra algoritm C, U, R väljs, och vi låter A ′ = CU R. (C och R är matriser som består av faktiska kolumner och rader, respektive A, och U är en generaliserad invers av deras skärningspunkt.) För varje algoritm, visar vi att med sannolikhet minst 1 − δ där A k är den "bästa" rank-k approximationen som tillhandahålls genom att trunkera singular value decomposition (SVD) av A, och där X F är Frobenius norm av matrisen X. Antalet kolumner i C och raderna R är ett låggradigt polynom i k, 1/ och log(1/δ). Både Numerical Linear Algebra community och Theoretic Computer Science community har studerat varianter av dessa matris sönderdelningar under de senaste tio åren. Men, våra två algoritmer är de första polynom tid algoritmer för sådana låg-rankade matris approximationer som kommer med relativa-terror garantier; tidigare, i vissa fall, var det inte ens känt om sådana matris sönderdelningar finns. Båda våra algoritmer är enkla och de tar tid på den ordning som behövs för att ungefär beräkna de översta k singular vektorer av A. Den tekniska grunden för vår analys är en ny, intuitiv provtagningsmetod som vi introducerar i detta papper som kallas "subrymdsprovtagning". Vid subrymdsprovtagning beror sannolikheten för provtagning på de euklideiska normerna i raderna på de översta enskilda vektorerna. Detta gör att vi kan få bevisbara relativa-terror garantier genom att dekonvolvera "subrymd" information och "storlek på-A" information i inmatningsmatrisen. Denna teknik är sannolikt att vara användbar för andra matris approximation och data analys problem. * En preliminär version av detta papper framträdde i manuskript och teknisk rapportformat som "Polynomisk Tid Algoritm för Column-Row-Based Relativ-Error Low-Rank Matrix Caimation" [27, 28]. Preliminära versioner av delar av detta dokument har också framträtt som konferensförfaranden [29, 30, 31].  Stora m × n matriser är vanliga i tillämpningar eftersom data ofta består av m objekt, som var och en beskrivs av n funktioner. Exempel på objekt-feature par inkluderar: dokument och ord som ingår i dessa dokument; genom och miljöförhållanden under vilka gensvar mäts; lager och deras tillhörande tidsupplösning; hyperspektral bilder och frekvensupplösning; och webbgrupper och enskilda användare. Inom vart och ett av dessa tillämpningsområden tillbringar utövare mycket tid med att analysera data för att förstå, tolka och i slutändan använda dessa data för någon applikationsspecifik uppgift. Säg att A är m × n datamatrisen. I många fall är ett viktigt steg i dataanalys att konstruera en komprimerad representation av A som kan vara lättare att analysera och tolka. Den vanligaste sådan representation erhålls genom att trunkera Singular Value Decomposition (SVD) med ett visst antal k  på min {m, n} termer, i stor del eftersom detta ger den "bästa" rank-k approximation till A när det mäts med avseende på någon unitally invariant matris norm. Tyvärr är de basvektorer (de så kallade eigencolumns och eigenrows) som tillhandahålls genom denna approximation (och med avseende på vilka varje kolumn och rad i den ursprungliga datamatrisen uttrycks) notoriskt svåra att tolka i termer av de underliggande data och processer som genererar dessa data. Till exempel vektorn [(1/2) ålder -(1/ ε 2) höjd + (1/2) inkomst], som är en av de betydande okorrelerade "faktorer" från en datauppsättning av människors egenskaper är inte särskilt informativ. Det skulle vara mycket bättre att ha en låg rank approximation som är nästan lika bra som den som tillhandahålls av SVD men som uttrycks i form av ett litet antal faktiska kolumner och / eller faktiska rader av en matris, snarare än linjära kombinationer av dessa kolumner och rader. Det viktigaste bidraget i detta dokument är att tillhandahålla sådana nedbrytningar. I synnerhet tillhandahåller vi vad vi kallar en relativ-terror CUR matris nedbrytning: med tanke på en m × n matris A, vi sönderdela den som en produkt av tre matriser, C, U och R, där C består av ett litet antal faktiska kolumner av A, R består av ett litet antal faktiska rader av A, och U är en liten noggrant konstruerade matris som garanterar att produkten CU R är "nära" till A. I själva verket kommer CU R att vara nästan lika bra som den bästa låg-ranking approximation till A som traditionellt används och som erhålls genom trunkering SVD. Därför kan kolumnerna A som ingår i C, liksom raderna A som ingår i R, användas i stället för eigencolumns och eigenrows, med den ytterligare fördelen av förbättrad tolkningsbarhet när det gäller de ursprungliga uppgifterna. Innan vi beskriver våra huvudsakliga resultat i nästa underavsnitt vill vi betona att två forskningsgemenskaper, Numerical Linear Algebra (NLA) community och Theoretic Computer Science (TCS) community, har gett betydande praktisk och teoretisk motivation för att studera varianter av dessa matris sönderdelningar under de senaste tio åren. I avsnitt 3 ger vi en detaljerad behandling av relevant tidigare arbete i både NLA och TCS litteratur. De två algoritmer som presenteras i detta dokument är de första polynom tid algoritmer för sådana låg-rankade matris approximationer som kommer med relativa-terror garantier; tidigare, i vissa fall var det inte ens känt om sådana matris sönderdelningar finns. Som ett exempel på denna preferens för att ha datamatrisen uttryckt i ett litet antal faktiska kolumner och rader av den ursprungliga matrisen, i motsats till ett litet antal eigencolumns och eigenrows, anser nyligen dataanalys arbete i DNA mikroarray och DNA Single Nucleotide Polymorphism (SNP) analys [44, 47, 52]. DNA-SNP-data modelleras ofta som en m × n-matris A, där m är antalet individer i studien, n är antalet SNP-värden som analyseras, och A ij är en kodning av j-th SNP-värdet för i-th-individen. På liknande sätt för DNA-mikroarray
CUR-algoritmen innebär slumpmässig provtagning av r-raderna med hjälp av sannolikheter som genereras av den beräknade hävstångspoängen för att erhålla matrisen R, och därefter provtagning av c-kolumnerna i A-kolumnen baserat på hävstångspoängen i R-matrisen för att erhålla C. Den viktigaste tekniska insikten i REF är att hävstångspoängen för en kolumn mäter "hur mycket" av kolonnen ligger i subrymden som spänns av A:s toppk-vänsters singular vektorer. Därför kallas denna metod för sampning också för subrymdsprovtagning.
Relative-Error CUR Matrix Decompositions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}