Frieze m.fl. [17] bevisade att ett litet prov av rader av en given matris A innehåller en låg rank approximation D som minimerar A − D på små additiva fel, och provtagningen kan göras effektivt med bara två passerar över matrisen [12]. I detta dokument generaliserar vi detta resultat på två sätt. För det första bevisar vi att additivt fel sjunker exponentiellt genom att iterera provtagningen på ett adaptivt sätt. Med hjälp av detta resultat, ger vi en pass-effektiv algoritm för beräkning låg-rank approximation med minskat additivt fel. Vårt andra resultat är att det med hjälp av en naturlig fördelning på undergrupper av rader (kallas volymprovtagning), finns en undergrupp av k- rader vars spännvidd innehåller en faktor (k + 1) relativ approximation och en undergrupp av k + k (k + 1) / rader vars spännvidd innehåller en 1+ relativ approximation. Förekomsten av en sådan liten certifikat för multiplicativ låg-rank approximation leder till en PTAS för följande projektiva kluster problem: Med tanke på en uppsättning punkter P i R d, och heltal k, j, hitta en uppsättning j subspaces F1,. .., Fj, var och en av dimensionerna på de flesta k, som minimerar
Detta resultat bevisas med den så kallade volymprovtagningsmetoden REF.
Matrix approximation and projective clustering via volume sampling
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}