BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:IterativeCUR: One Small Sketch for Big Matrix Approximations - Nat
 haniel Pritchard (University of Oxford)
DTSTART:20251106T150000Z
DTEND:20251106T160000Z
UID:TALK235018@talks.cam.ac.uk
CONTACT:Georg Maierhofer
DESCRIPTION:The computation of accurate low-rank matrix approximations is 
 central to improving the scalability of various techniques in machine lear
 ning\, uncertainty quantification\, and control. Traditionally\, low-rank 
 approximations are constructed using SVD-based approaches such as truncate
 d SVD or RandomizedSVD. Although these SVD approaches---especially Randomi
 zedSVD---have proven to be very computationally efficient\, other low-rank
  approximation methods can offer even greater performance. One such approa
 ch is the CUR decomposition\, which forms a low-rank approximation using d
 irect row and column subsets of a matrix. Because CUR uses direct matrix s
 ubsets\, it is also often better able to preserve native matrix structures
  like sparsity or non-negativity than SVD-based approaches and can facilit
 ate data interpretation in many contexts. This paper introduces IterativeC
 UR\, which draws on previous work in randomized numerical linear algebra t
 o build a new algorithm that is highly competitive compared to prior work:
  (1) It is adaptive in the sense that it takes as an input parameter the d
 esired tolerance\, rather than an a priori guess of the numerical rank. (2
 ) It typically runs significantly faster than both existing CUR algorithms
  and techniques such as RandomizedSVD\, in particular when these methods a
 re run in an adaptive rank mode. Its asymptotic complexity is  O(mn + (m+n
 )r²+ r³) for an m x n matrix of numerical rank r. (3) It relies on a sin
 gle small sketch from the matrix that is successively downdated as the alg
 orithm proceeds.\n\nWe demonstrate through extensive experiments that Iter
 ativeCUR achieves up to 4x speed-up over state-of-the-art pivoting-on-sket
 ch approaches with no loss of accuracy\, and up to 40x speed-up over rank-
 adaptive randomized SVD approaches.
LOCATION:Centre for Mathematical Sciences\, MR14
END:VEVENT
END:VCALENDAR