Title: On low-rank updates to the singular value and Tucker decompositions
Abstract: Previous chapter Next chapter Full AccessProceedings Proceedings of the 2010 SIAM International Conference on Data Mining (SDM)On low-rank updates to the singular value and Tucker decompositionsMichael J. O'HaraMichael J. O'Harapp.713 - 719Chapter DOI:https://doi.org/10.1137/1.9781611972801.62PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract The singular value decomposition is widely used in signal processing and data mining. Since the data often arrives in a stream, the problem of updating matrix decompositions under low-rank modification has been widely studied. Brand developed a technique in 2006 that has many advantages. However, the technique does not directly approximate the updated matrix, but rather its previous low-rank approximation added to the new update, which needs justification. Further, the technique is still too slow for large information processing problems. We show that the technique minimizes the change in error per update, so if the error is small initially it remains small. We show that an updating algorithm for large sparse matrices should be sub-linear in the matrix dimension in order to be practical for large problems, and demonstrate a simple modification to the original technique that meets the requirements. We extend Brand's method to tensors, the multi-way generalization of matrices. The few published comparable techniques either focus on small-magnitude changes, are iterative, or have no published error properties. We show that the technique of Brand for updating the truncated singular value decomposition can be redesigned as a low-rank update scheme for the Tucker decomposition, with analogous run-time and error properties. Previous chapter Next chapter RelatedDetails Published:2010ISBN:978-0-89871-703-7eISBN:978-1-61197-280-1 https://doi.org/10.1137/1.9781611972801Book Series Name:ProceedingsBook Code:PR136Book Pages:1-953Key words:Updating, truncated singular value decomposition, Tucker decomposition, low-rank approximation, tensor