RANDOMIZED NUMERICAL LINEAR ALGEBRA APPROACHES FOR APPROXIMATING MATRIX FUNCTIONS

This work explores how randomization can be exploited to deliver sophisticated

algorithms with provable bounds for: (i) The approximation of matrix functions, such

as the log-determinant and the Von-Neumann entropy; and (ii) The low-rank approximation

of matrices. Our algorithms are inspired by recent advances in Randomized

Numerical Linear Algebra (RandNLA), an interdisciplinary research area that exploits

randomization as a computational resource to develop improved algorithms for

large-scale linear algebra problems. The main goal of this work is to encourage the

practical use of RandNLA approaches to solve Big Data bottlenecks at industrial

level. Our extensive evaluation tests are complemented by a thorough theoretical

analysis that proves the accuracy of the proposed algorithms and highlights their

scalability as the volume of data increases. Finally, the low computational time and

memory consumption, combined with simple implementation schemes that can easily

be extended in parallel and distributed environments, render our algorithms suitable

for use in the development of highly efficient real-world software.