Till innehåll på sidan

Samuel Relton: Estimating the Largest Elements of a Matrix

Tid: To 2016-10-06 kl 14.15 - 15.00

Plats: KTH Mathematics, Lindstedtsvägen 25, floor 7, room 3721

Medverkande: Samuel Relton, University of Manchester

Exportera till kalender

Abstract:

In many applications we need to find or estimate the \(p \ge 1\) largest elements of a matrix, along with their locations. This is required for recommender systems used by Amazon and Netflix, link prediction in graphs, and in finding the most important links in a complex network, for example. 

Our algorithm uses only matrix vector products and is based upon a power method for mixed subordinate norms. We have obtained theoretical results on the convergence of this algorithm via a comparison with rook pivoting for the LU decomposition. We have also improved the practicality of the algorithm by producing a blocked version iterating on \(n \times t\) matrices, as opposed to vectors, where \(t\) is a tunable parameter. For \(p > 1\) we show how deflation can be used to improve the convergence of the algorithm. 

Finally, numerical experiments on both randomly generated matrices and real-life datasets (the latter for \(A^TA\) and \(e^A\)) show how our algorithms can reliably estimate the largest elements of a matrix whilst obtaining considerable speedups when compared to forming the matrix explicitly: over 1000x in some cases.