Hari Sundar


Distributed Algorithms for Linear Algebra

CS 7935 - Seminar - class number 18537

The purpose of this seminar is to study and explore fundamental linear algebra methods, especially for large scale problems, and the distributed algorithms for computing them in parallel. Each semester, a particular theme shall be chosen and explored. We will meet and discuss (typically) one paper a week. If you are registering for credit, you will be expected to present (at least) one paper from the list below. Email me your choice of paper(s) at the earliest.

Fall 2015 - Generalizations of the SVD

Wed 9:00-10:30am

MEB 3147 (LCR)

Singular Value Decomposition is often referred to as the 'Swiss Army Knife' of Linear Algebra. Indeed, it has found widespread use across engineering and the sciences. There has been significant recent research in developing new algorithms for computing accurate and approximate SVDs for large matrices, including distributed or easily parallelizable algorithms. There has also been significant interest in extending the SVD to Tensors. This seminar will focus on these advances. Here is a tentative list of papers for discussion. We will likely add additional ones as our discussions progress. It is also unlikely that we will be able to cover all of these and will try and prioritize the ordering.

SVD & Parallel SVD

  1. Intro, SVD, CSD, GSVD, HoSVD, Tensor Factorization etc ...
  2. Berry, Michael W., et al. Parallel algorithms for the singular value decomposition. Statistics Textbooks and Monographs 184 (2006) *Ashok Jallepalli
  3. Zlatko Drmač and Krešimir Veselić, New Fast and Accurate Jacobi SVD Algorithm. I, SIAM. J. Matrix Anal. & Appl., 29(4), 1322–1342 (and part II) Christopher Mertin - 16 Sep 2015
  4. N. Halko, P. G. Martinsson, and J. A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Rev., 53(2), 217–288. Mina Ghashami - 23 Nov 2015

GSVD, HoSVD, Tensor Factorization

  1. C. C. Paige, and M. A. Saunders: Towards a Generalized Singular Value Decomposition, SIAM J. Numer. Anal., Volume 18, Number 3, June 1981. Ally Warner - 30 Sep 2015
  2. Kruskal, J. B. (1989). Rank, decomposition, and uniqueness for 3-way and N-way arrays. In R. Coppi & S. Bolasco (Eds.), Multiway data analysis (pp. 7–18). Elsevier. Wai Ming Tai - 7 Oct 2015
  3. Ledyard R Tucker, Some mathematical notes on three-mode factor analysis, Psychometrika 31 (3): 279–311. Majid Rasouli - 21 Oct 2015
  4. Jie Chen and Yousef Saad, On the Tensor SVD and the Optimal Low Rank Orthogonal Approximation of Tensors, SIAM. J. Matrix Anal. & Appl., 30(4), 1709–1734 Sourabh Palande - 28 Oct 2015
  5. I. V. Oseledets and E. E. Tyrtyshnikov, Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions, SIAM J. Sci. Comput., 31(5), 3744–3759. Milinda Fernando 4 Nov 2015
  6. Lars Grasedyck, Hierarchical Singular Value Decomposition of Tensors, SIAM. J. Matrix Anal. & Appl., 31(4), 2029–2054
  7. Nick Vannieuwenhoven, Raf Vandebril, and Karl Meerbergen, A New Truncation Strategy for the Higher-Order Singular Value Decomposition, SIAM J. Sci. Comput., 34(2), A1027–A1052. 11 Nov 2015
  8. I. V. Oseledets, Tensor-Train Decomposition, SIAM J. Sci. Comput., 33(5), 2295–2317. 18 Nov 2015
  9. Roland Badeau and Rémy Boyer, Fast Multilinear Singular Value Decomposition for Structured Tensors, SIAM. J. Matrix Anal. & Appl., 30(3), 1008–1021. 25 Nov 2015
  10. Liqi Wang, Moody T. Chu, and Bo Yu, Orthogonal Low Rank Tensor Approximation: Alternating Least Squares Method and Its Global Convergence, SIAM. J. Matrix Anal. & Appl., 36(1), 1–19 02 Dec 2015

Applications

  1. Kolda, Tamara G., and Brett W. Bader. Tensor decompositions and applications SIAM review 51.3 (2009): 455-500. 09 Dec 2015
  2. O. Alter, P. O. Brown and D. Botstein, Generalized Singular Value Decomposition for Comparative Analysis of Genome-Scale Expression Datasets of Two Different Organisms. PNAS 100 (6): 3351–3356. 16 Dec 2015.
  3. Rendle, Steffen, and Lars Schmidt-Thieme. Pairwise interaction tensor factorization for personalized tag recommendation Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010.
  4. Anandkumar, Animashree, et al. Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research 15.1 (2014): 2773-2832.