I den här artikeln utvecklar vi algoritmer för att approximera matrisförökning med avseende på spektralnormen. Låt A  på R n×m och B på R n×p vara två matriser och ε > 0. Vi approximerar produkten A B med hjälp av två skisser e A  på R t×m och e med hög sannolikhet. Vi analyserar två olika provtagningsförfaranden för att bygga e A och e B; en av dem görs av i.i.d. Icke-uniforma provtagningsrader från A och B och den andra genom slumpmässiga linjära kombinationer av deras rader. Vi bevisar gränser på t som endast beror på den inneboende dimensionaliteten av A och B, det vill säga deras rang och deras stabila rang. För att uppnå gränser som beror på rang när vi tar slumpmässiga linjära kombinationer använder vi standardverktyg från högdimensionell geometri såsom koncentration av mätargument i kombination med genomtänkta ε-nätkonstruktioner. För gränser som beror på den mindre parametern av stabil rang denna teknik själv verkar svag. Vi visar emellertid att det i kombination med ett enkelt trunkeringsargument är möjligt att ge sådana gränser. För att hantera liknande gränser för radprovtagning, utvecklar vi en ny matris-värderad Chernoff bundet ojämlikhet som vi kallar låg rank matris värderad Chernoff bundet. Tack vare denna ojämlikhet kan vi ge gränser som bara beror på den stabila rangen av ingångsmatriser. Vi belyser nyttan av våra ungefärliga matris multiplikation gränser genom att leverera två applikationer. Först ger vi en approximationsalgoritm för 2-regressionsproblem som returnerar en ungefärlig lösning genom att slumpmässigt projicera det initiala problemet till dimensioner linjära på rangen av begränsningsmatrisen. För det andra ger vi förbättrade approximationsalgoritmer för låggradig matris approximation problem med avseende på den spektral norm.
Detta beroende av rang förbättras senare till stabil rang i REF, men till priset av ett svagare beroende av.
Low rank matrix-valued chernoff bounds and approximate matrix multiplication
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}