Det har varit betydande intresse och framsteg nyligen i algoritmer som löser regressionsproblem som involverar höga och tunna matriser i inmatning sparty tid. Med tanke på en n × d matris där n d, dessa algoritmer hitta en approximation med färre rader, så att man kan lösa ett poly(d) storlek problem istället. I praktiken uppnås de bästa föreställningarna ofta genom att åberopa dessa rutiner på ett iterativt sätt. Vi visar dessa iterativa metoder kan anpassas för att ge teoretiska garantier jämförbara med och bättre än den nuvarande tekniken. Våra metoder bygger på att beräkna betydelsen av raderna, så kallade hävstångspoäng, på ett iterativt sätt. Vi visar att alternerande mellan att beräkna en kort matris uppskattning och att hitta mer exakt ungefärlig hävstångseffekt poäng leder till en serie geometriskt mindre fall. Detta ger en algoritm vars drifttid är input sparity plus en overhead jämförbar med kostnaden för att lösa ett regressionsproblem på mindre approximation. Våra resultat bygger på det nära sambandet mellan randomiserade matrisalgoritmer, iterativa metoder och graf sparifiering.
I REF föreslogs en algoritm baserad på radernas betydelse.
Iterative Row Sampling
{'venue': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'journal': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}