Abstrakt. I många tillämpningar består uppgifterna av (eller kan vara naturligt formulerade som) en m × n matris A. Det är ofta av intresse att hitta en låg rank approximation till A, dvs. en approximation D till matrisen A av rank inte större än en specificerad rank k, där k är mycket mindre än m och n. Metoder såsom singular value decomposition (SVD) kan användas för att hitta en approximation till A som är bäst i en väldefinierad betydelse. Dessa metoder kräver minne och tid som är superlinjära i m och n; för många tillämpningar där datamängderna är mycket stora är detta oöverkomligt. Två enkla och intuitiva algoritmer presenteras som, när de ges en m × n-matris A, beräknar en beskrivning av en låggradig approximation D * till A, och som är kvalitativt snabbare än SVD. Båda algoritmerna har bevisbara gränser för felmatrisen A − D *. För varje matris X, låt X F och X 2 betecknar dess Frobenius norm och dess spektral norm, respektive. I den första algoritmen väljs C-kolumner av A slumpmässigt. Om m × c-matrisen C består av dessa c-kolumner av A (efter lämplig skalning) visas det att från C T C approximationer till de högsta singularvärdena och motsvarande singularvektorer kan beräknas. Från den beräknade singular vektorer en beskrivning D * av matrisen A kan beräknas så att rank(D * ) ≤ k och sådana som håller med hög sannolikhet för både  till = 2, F. Denna algoritm kan genomföras utan att lagra matrisen A i slumpmässigt åtkomstminne (RAM), förutsatt att det kan göra två passerar över matrisen lagras i externt minne och använda O(cm + c 2 ) ytterligare RAM. Den andra algoritmen är liknande förutom att det ytterligare approximerar matrisen C genom slumpmässigt urval r rader av C för att bilda en r × c matris W. Således har det ytterligare fel, men det kan genomföras i tre passerar över matrisen med endast konstant ytterligare RAM. För att uppnå ett ytterligare fel (bortom den bästa rangen k approximation) som är som mest A 2 F, båda algoritmer tar tid som är polynom i k, 1/, och log( 1/π), där δ > 0 är en felsannolikhet; den första tar tid linjär i max (m, n) och den andra tar tid oberoende av m och n. Våra gränser förbättra tidigare publicerade resultat med avseende på rang parameter k för både Frobenius och spektral normer. Dessutom använder sig bevisen för felgränserna av en ny metod som gör det viktigt att använda sig av matrisperturberingsteorin. Sannolikheten fördelning över kolumnerna i A och omskalning är avgörande egenskaper hos algoritmerna som måste väljas omdömesgillt.
Låggradig approximation: I REF infördes problemet med beräkning av låggradig approximation av en given matris med endast några få passager över data.
Fast monte-carlo algorithms for finding low-rank approximations
{'venue': 'J. ACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}