Singular value decomposition (SVD) is a popular matrix decomposition technique and is pervasively used in diverse areas such as document retrieval, background subtraction in videos, and compression. Real world applications see addition or removal of rows or columns, and recomputing of SVD from scratch is computationally prohibitive in most applications. In this talk, two flavors of the incremental version of computing SVD will be shown: downdating and updating the SVD. These problems arise when q rows of an existing matrix are removed from or added to an (m by n) matrix and the SVD of the resultant matrix is required. A general template to solve the incremental SVD problems will be presented first. We will then show our results on solving the incremental problems efficiently by suitably adopting the template. We will also show techniques that allow deferring subspace calculations if the applications do not require the SVD to be explicitly retrieved upon each downdate or updat e request. Our techniques are deterministic and allow streaming of matrix entries. We will also briefly review existing algorithms which use random projections or sampling and show how they fit the general template.. The talk will be accessible to anyone with basic knowledge of linear algebra. (Joint work with Saurav Jha and Arpita Singh, IIT Madras)
Shankar Balachandran is on the faculty of CSE department at IIT Madras and is currently a visiting professor in the EE department at IIT Bombay. He received his BE in Computer Science and Engineering from the University of Madras and PhD in Electrical Engineering from the University of Texas at Dallas. His primary areas of research are in computer architecture and VLSI design automation.