Aplicaciones algorítmicas del lema de Johnson-Lindenstrauss

Abstract

Este trabajo está estructurado en seis capítulos. En primer lugar, en el Capítulo 1 desarrollaremos los conceptos previos que nos permitirán entender la teoría que se expondrá posteriormente. En el Capítulo 2 enunciaremos y demostraremos el lema de Johnson-Lindestrauss ilustrando dicho lema con varios ejemplos teóricos. Las aplicaciones prácticas las desarrollaremos en el Capítulo 3 : mostraremos la e ciencia computacional que proporciona el lema en algunos problemas clásicos como el vecino más próximo o el cálculo de la distancia entre puntos en espacios euclídeos de dimensión alta. En el Capítulo 4 describiremos el trabajo realizado durante la estancia en prácticas en la empresa The Netwizzy Company S.L.. Detallaremos, de forma más precisa, las herramientas empleadas y la metodología. Por ultimo, en el Capítulo 5 y Capítulo 6 expondremos los resultados obtenidos durante la estancia en The Netwizzy Company S.L. y las conclusiones de este Trabajo Final de Grado, respectivamente.

This thesis is structured in six chapters. Firstly, in Chapter 1 we will develop the preliminary concepts that will allow us to understand the theory which will be exposed afterwards. In Chapter 2 we will enunciate and demonstrate the Johnson-Lindenstrauss's lemma, illustrating it with a few theoretical examples. Practical applications will be developed during Chapter 3 : we will show the computational e ciency that the lemma provides in some classical problems such as the nearest neighbor or calculating the distance between points in high-dimensional Euclidean spaces. During Chapter 4 we will describe our work during our internship at the company The Netwizzy Company S.L.. We will detail the tools used and the methodology in a precise way. Finally, in Chapter 5 and Chapter 6 we will discuss respectively the results during the stay in The Netwizzy Company S.L. and the conclusions of this Final Project.