Randomized algorithms for singular value decomposition

• Grant number: 15/18552-5
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: October 01, 2015
• End date: September 30, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Renato da Rocha Lopes
• Grantee: Antonio Pedro de Sousa Vieira
• Host Institution: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Singular value decomposition (SVD) is a factorization of a real or complex matrix in the form A = USV*, where U and V are unitary and S is diagonal. SVD exists for every matrix A. This factorization is useful in many cases, such as minimum squares calculation and approximation of A with low rank matrixes. This last technique is largely employed in large-scale matrix processing. Classic methods for SVD calculation face challenges related to the size of the data matrixes encountered: the memory access overhead and the computational cost associated to the many operations necessary for the decomposition. Processing time can be reduced by the use of randomized algorithms, which reduce memory access through a prior rank reduction, and through processing parallelization. In this work, a study of SVD implementations, from the classic methods to randomized implementation and GPU utilizing approaches, later associating these two modifications. Comparative analysis of the results will be conducted with standard Python and MATLAB implementations as reference levels. This study aims to improve the appliant's skills in the field of data processing and to create open source options, to be used in large matrix decomposition applications.