Algoritmi za brzo aproksimativno spektralno učenje

Abstract

This thesis presents learning algorithms which use the information stored in the spectrum (eigenvalues and eigenvectors) of a matrix derived from the input set. Matrices in question are graph matrices or kernel matrices. However, the algorithms which use these matrices have either a quadratic or cubic time complexity and quadratic memory complexity. Therefore, in this thesis the algorithms will be presented that approximate those matrices and reduce the time and memory complexity to the linear one. Also, these algorithms will be compared with the other algorithms that solve this problem, and their empirical and theoretical analysis will be presented.