Vi fokuserar användningen av radprovtagning för approximering av matrisalgoritmer. Vi ger applikationer till matris multipication; sparse matris rekonstruktion; och, l 2 regression. För en matris A, R m×d som representerar m punkter i d m dimensioner, kan alla dessa uppgifter uppnås i O (md 2 ) via singular value decomposition (SVD). För lämpliga rad-sampling sannolikheter (som normalt beror på normerna i raderna i m × d vänster singular matris av A ( hävstångspoäng), ger vi rad-sampling algoritmer med linjära (upp till polylog faktorer) beroende på den stabila rangen av A. Detta resultat uppnås genom tillämpning av icke-kommutativa Bernsteingränser. Vi ger sedan, till vår kunskap, de första algoritmerna för beräkning approximationer till lämpliga rad-sampling sannolikheter utan att gå igenom SVD av A. Dessa är alltså de första o(md 2 ) algoritmerna för radprovtagningsbaserade approximationer till de matrisalgoritmer som använder hävstångspoäng som sannolikheten för provtagning. De tekniker vi använder för att approximera provtagning enligt hävstången poäng använder några kraftfulla senaste resultat i teorin om slumpmässiga prognoser för inbäddning, och kan vara av något oberoende intresse. Vi erkänner att man kan utföra alla dessa matris uppgifter mer effektivt med hjälp av dessa samma slumpmässiga projektionsmetoder, men de resulterande algoritmer är i termer av ett litet antal linjära kombinationer av alla rader. I många tillämpningar har de faktiska raderna av A en viss fysisk betydelse och därför är metoder baserade på ett litet antal av de faktiska raderna av intresse.
Vårt urval distribution D F kan ses som en kontinuerlig gräns för hävstång score provtagning distribution, så det tillståndsnummer som vi visar i Theorem 4.1 är mycket lik resultatet i REF.
Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}