Korkeaulotteisten äärellisten joukkojen upotukset

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2023-08-23

Department

Major/Subject

Matematiikka ja systeemitieteet

Mcode

SCI3029

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

fi

Pages

33

Series

Abstract

Tässä työssä johdetaan Johnson-Lindenstrauss-teoreema sekä käydään läpi kyseisen teoreeman sovelluksia. Teoreema käsittelee korkeaulotteisten pisteiden upottamista pienempään ulottuvuuteen, niin että pisteiden väliset etäisyydet pysyvät likimääräisesti samana. Teoreeman käyttötarkoituksia löytyy monessa laskennallisessa menetelmässä. Teoreeman johtamiseksi tarvitaan taustatietoa $n$-ulotteisten joukkojen tilavuuksien käsitteistä, mittateoriasta, metrisistä avaruuksista, topologiasta ja todennäköisyyslaskennasta. Päätuloksen johtaminen aloitetaan käymällä aluksi läpi Brunn-Minkowski-epäyhtälö, joka on voimassa kaikille kompakteille joukoille. Kyseistä epäyhtälöä voidaan hyödyntää yleisen isoperimetrisen epäyhtälön osoittamisessa. Isoperimetrinen epäyhtälö on puolestaan hyödyllinen tarkasteltaessa mitan keskittymistä pallon pinnalla. Työssä sovelletaan mitan keskittymistä todistettaessa Lévyn apulausetta, joka pätee yleisesti $1$-Lipschitz-funktioille. Projisointifunktioiden ominaisuuksista johtuen Lévyn apulausetta hyödynnetään päälauseen todistuksessa. Lopuksi käsitellään teoreeman tarkoitusta ja sen hyödyllisiä sovelluksia laskennallisissa menetelmissä.

In this thesis, we derive the Johnson-Lindenstrauss theorem and explore its applications. The theorem addresses the embedding of high-dimensional points into lower-dimensional spaces while preserving distances, a process known as high-dimensional reduction. The theorem also has numerous applications in various computational methods. Deriving the theorem requires background knowledge in the concepts of volumes of $n$-dimensional sets, measure theory, metric spaces, topology, and probability theory. The derivation of the main result begins with the Brunn-Minkwoski inequality, which holds for all compact sets. This inequality can be used to prove the general isoperimetric inequality. The isoperimetric inequality is, in turn, useful for examining the measure concentration on the sphere. In this thesis, the measure concentration is used to prove Lévy's lemma which generally applies to every 1-Lipschitz function. As a result of the properties of projection functions, Lévy's lemma can be used in the proof of the main theorem. Finally, in the end we discuss the purpose and useful applications of the main theorem in numerical methods.

Description

Supervisor

Alestalo, Pekka

Thesis advisor

Alestalo, Pekka

Keywords

metriset avaruudet, upotukset, mitan keskittyminen, isoperimetrinen epäyhtälö, analyysi

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202409246466

Collections

[kand] Perustieteiden korkeakoulu / SCI