Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Convex Kernel Embedding.
KTH, School of Computer Science and Communication (CSC).
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Marin Šarić

Convex Kernel Embedding

This work examines problems in linear and non-linear dimensionality reduction through linear algebra and geometry, connecting insights from geometric multivariate analysis with convex analysis and machine learning.

A linear algebra toolbox for the geometric interpretation of common data statistics is introduced and derived. Rather than solely interpreting observed data as points in a space, complete datasets are also viewed as points in a matrix space. The Euclidean distance matrix (EDM) and the Gram matrix describing relationships between the datapoints are presented and related to kernels as used in the machine learning community.

Using the introduced toolbox, a novel derivation of Classical multidimensional scaling (MDS) is presented, giving a more geometrically intuitive proof using solely basic linear algebra. Classical MDS is formulated as maintaining an embedding by preserving the global distance isometry through the EDM.

Non-linear dimensionality reduction (NDR) techniques are viewed as relaxations of the global distance isometry, in other words as partial preservations of the EDM. This work maintains focus on EDM relaxations expressed as convex optimization programs. Recent concepts from convex analysis are consolidated and derived from the undergraduate linear algebra to offer a geometric insight into convex optimization programs related to NDR.

Maximum variance unfolding is used as an example NDR technique to derive the metric, EDM and Gram matrix optimization programs, further analyzing their geometry and equivalence using the presented linear algebra tools.

Abstract [sv]

Marin Šarić

Konvex kernel inbäddning

Detta arbete betraktar problem inom linjär och icke-linjär dimensionalitetsreduktion med hjälp av linjär algebra och geometri, genom att binda samman insikter ur geometrisk flervariabelanalys med konvex analys och maskininlärning.

En uppsättning algebraiska verktyg introduceras och härleds, avsedda för geometrisk tolkning av vanligt förekommande typer av datastatistik. I stället för att bara tolka data som punkter i rummet, betraktas även hela datamängder som punkter i ett matrisrum. Den euklidiska avståndsmatrisen (Euclidean distance matrix, EDM) liksom Gram-matrisen, vilka beskriver förhållandet mellan datapunkterna, presenteras och anknyts till de kernels som används inom maskininlärning.

Tekniker för ickelinjär dimensionalitetsreduktion (Non-linear dimensionality reduction, NDR) betraktas som relaxeringar av den globala avståndsisometrin; med andra ord, som delvis bibehållna EDM. Detta arbete fokuserar på relaxeringar som uttrycks som program för konvex optimering. Nyligen introducerade koncept ur den konvexa analysen konsolideras och härleds från grundläggande linjär algebra, för att ge geometrisk insikt i konvexa optimeringsprogram med anknytning till NDR.

"Maximum variance unfolding" används som ett exempel på en NDR-teknik, för vilken optimeringsprogram härleds metriskt, med EDM respektive Gram-matris, med hjälp av de verktyg som presenterats.

Place, publisher, year, edition, pages
2011.
Series
Trita-CSC-E, ISSN 1653-5715 ; 2011:075
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-130763OAI: oai:DiVA.org:kth-130763DiVA: diva2:654210
Educational program
Master of Science - Systems, Control and Robotics
Uppsok
Technology
Supervisors
Examiners
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links

http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2011/rapporter11/saric_marin_11075.pdf
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 91 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf