BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Yuji Nakatsukasa (University of Oxford) DTSTART:20201028T150000Z DTEND:20201028T160000Z DTSTAMP:20260423T041507Z UID:E-NLA/19 DESCRIPTION:Title: F ast and stable randomized low-rank matrix approximation\nby Yuji Nakat sukasa (University of Oxford) as part of E-NLA - Online seminar series on numerical linear algebra\n\n\nAbstract\nRandomized SVD has become an extre mely successful approach for efficiently computing a low-rank approximatio n of matrices. In particular the paper by Halko\, Martinsson\, and Tropp ( SIREV 2011) contains extensive analysis\, and has made it a very popular m ethod. The typical complexity for a rank-r approximation of mxn matrices i s O(mnlog n+(m+n)r^2) for dense matrices. The classical Nystrom method is much faster\, but only applicable to positive semidefinite matrices. This work studies a generalization of Nystrom's method applicable to general ma trices\, and shows that (i) it has near-optimal approximation quality comp arable to competing methods\, (ii) the computational cost is the near-opti mal O(mnlog n+r^3) for dense matrices\, with small hidden constants\, and (iii) crucially\, it can be implemented in a numerically stable fashion de spite the presence of an ill-conditioned pseudoinverse. Numerical experime nts illustrate that generalized Nystrom can significantly outperform state -of-the-art methods\, especially when r>>1\, achieving up to a 10-fold spe edup. The method is also well suited to updating and downdating the matrix .\n LOCATION:https://researchseminars.org/talk/E-NLA/19/ END:VEVENT END:VCALENDAR