I detta arbete föreslår vi en ny randomiserad algoritm för beräkning av en låggradig approximation till en given matris. Med ett tillvägagångssätt som skiljer sig från befintlig litteratur, innebär vår metod först en specifik partisk provtagning, med ett element som väljs baserat på hävstångspoängen i sin rad och kolumn, och sedan innebär viktad alternerande minimering över den faktoriserade formen av den avsedda låg-rankade matrisen, för att minimera fel endast på dessa prover. Vår metod kan utnyttja input sparity, men ändå producera approximationer i spektral (i motsats till den svagare Frobenius) norm; detta kombinerar de bästa aspekterna av annars olika aktuella resultat, men med ett beroende av tillståndsnummer σ = σ 1 /σ r. I synnerhet kräver vi O(nnz(M ) + nσ 2 r 5  och 2 ) beräkningar för att generera en rank-r approximation till M i spektral norm. Den bästa befintliga metoden kräver däremot tid för att beräkna en approximation i Frobenius norm. Förutom tätheten i spektral norm, har vi ett bättre beroende av felet. Vår metod är naturligt och mycket parallelliserbar. Vår nya strategi möjliggör två förlängningar som är intressanta på egen hand. Den första är en ny metod för att direkt beräkna en låg-ranking approximation (i effektiv faktoriserad form) till produkten av två givna matriser; den beräknar en liten slumpmässig uppsättning poster av produkten, och utför sedan viktad alternerande minimization (som tidigare) på dessa. Provtagningsstrategin är annorlunda eftersom vi nu inte kan komma åt hävstångspoäng av produktmatrisen (men istället måste arbeta med ingångsmatriser). Den andra utbyggnaden är en förbättrad algoritm med mindre kommunikations komplexitet för den distribuerade PCA-inställningen (där varje server har en liten uppsättning rader av matrisen, och vill beräkna låg rang approximation med liten mängd kommunikation med andra servrar).
På senare tid har Ref ansetts vara partisk entrywise-provtagning med hjälp av hävstångspoäng, följt av matriskomplettering för att beräkna låggradig approximation.
Tighter Low-rank Approximation via Sampling the Leveraged Element
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}