Random Projections for Matrix Decomposition and Manifold Learning

Abstract

The thesis focuses on solving problems that are related to the behavior of random variables in high-dimensional spaces. The main motivation comes from the understanding that many of the scientific challenges involve large amounts of highdimensional data. It is known that there are always a small number of “hidden” parameters that encode the “interesting” part of the data. The question is, how do we identify and extract these parameters? This thesis is focused on two different aspects of data analysis: Numerical linear algebra and manifold learning. Numerical linear algebra is a major component for data analysis. It includes matrix factorization algorithms such as SVD and LU. SVD is considered to be the single most important algorithm in numerical linear algebra. However, due to the computational complexity of classical SVD algorithms, they cannot be applied in practice to huge datasets. One possible solution to this problem is to use low-rank methods. The idea of low-rank methods is the fact that in many cases there are dependencies and redundancies within the data. Therefore, the data can be well approximated and processed by utilizing its low-rank property which results in a faster processing of smaller data. In this thesis, Low-rank SVD and LU approximation algorithms are presented. They create a trade-off between accuracy and computational time. We improve on the state-of-the-art algorithms for Low-rank SVD and LU approximation. Since matrix factorization algorithms play a central central role in almost any modern computation, this part of the thesis provides general tools for many of the modern big data, and data analysis challenges. Understanding high-dimensional data via manifold learning. Many data analysis problems are formulated in the language of manifold learning. A typical assumption is that the data is on (or near) some unknown manifold embedded in high dimensions, and the goal is to “understand” the structure of this manifold. The thesis presents two result on this subject. First, a connection between two of the most classical methods in manifold learning, PCA and least squares, is presented. Secondly, a method for regression over manifold is presented. It allows to interpolate functions defined on manifolds given only the values of the function in several sampled points, without knowing the manifold on which the function is defined. The ability to solve regression problems over manifolds, can enable us to gain new insights from complex sampled data. Keywords: Matrix decompositions, Random projections, SVD, LU, manifold learning, Regression over manifolds

Väitöskirja keskittyy ratkaisemaan ongelmia, jotka liittyvät satunnaisten muuttujien käytökseen korkeaulottuvuuksissa avaruuksissa. Päämotivaatio tulee siitä ymmärryksestä, että monet tieteelliset haasteet sisältävät suuria määriä korkeaulottuvuuksellista dataa. Samalla tiedetään, että pieni määrä ”piilossa pysyviä” parametreja määrittää datan ”mielenkiintoisia” osia. Kysymys kuuluukin, kuinka pystymme tunnistamaan ja uuttamaan nämä parametrit. Tämä väitöskirja keskittyy data-analyysin kahteen alueeseen: Numeeriseen lineaariseen algebraan ja ”manifold learning” eli ”monisto-oppimisen” termillä tunnettuun lähestymistapaan. Tässä väitöskirjassa esitellään Low-rank SVD ja LU approksimaatioalgoritmit. Ne muodostavat kompromissin tarkkuuden ja laskenta-ajan välillä. Nämä metodit parantavat nykyaikaisia algoritmeja Low-rank SVD ja LU approksimaatioille. Uudet tulokset poistavat rajoitteita, jotka liittyvät ratkaistavissa olevien haasteiden kokoon ja tarkkuuteen. Koska matriisin tekijöihin jakaminen on keskiössä melkein kaikessa nykyaikaisessa laskennassa, tämä väitöskirjan osio tarjoaa yleisesti hyödynnettäviä työkaluja moneen nykyaikaiseen suuren datan ja data-analyysin ongelmanratkaisuun. Väitöskirjan tulokset todistavat satunnaisprojektioiden tehokkuuden erilaisissa matriisin tekijöihin jakamisen metodeissa, sekä antavat uuden näkökulman korkeiden ulottuvuuksien data-analyysille. Nämä kaksi aluetta ovat useiden tutkimusongelmien ytimessä. Tällä tutkimuksen alueella on yhä useita vastaamattomia kysymyksiä, joiden tutkimuksessa satunnaisprojektiot voivat olla avuksi. Avainsanat: Matriisien tekijöihin jakaminen, Satunnaisprojektiot,SVD, LU, monistooppiminen, regressio monistoja hyödyntäen