Datalog fra Aarhus Universitet løser 30 år gammelt matematisk problem

Dataloger har i årtier benyttet en matematisk læresætning til at komprimere data – uden at vide, om det var den bedst mulige metode. Men det er den, fastslår ny forskning af Kasper Green Larsen, adjunkt på Institut for Datalogi, Aarhus Universitet og hans amerikanske forskningskollega Jelani Nelson fra Harvard John A. Paulson School of Engineering and Applied Sciences.

Hvor meget kan man komprimere data uden at gå for meget på kompromis med kvaliteten? Det spørgsmål har dataloger i de sidste 30 år anvendt den matematiske sætning ”Johnson-Lindenstrauss lemmaet” til at besvare. Læresætningen tillader én at komprimere højdimensionel data og derved forøge hastigheden af de algoritmer, der ligger til grund for blandt andet spamfiltre, online-streaming og søgning på internettet.

”Johnson-Lindenstrauss lemmaet” blev oprindeligt bevist af matematikerne William B. Johnson og Joram Lindenstrauss i 1984 og er et centralt resultat indenfor matematisk analyse. Sætningen har fundet bred anvendelse i datalogien til komprimering, samt til at fremskynde algoritmisk behandling af data. Både i matematiske og datalogiske forskningskredse har der dog altid været usikkerhed om, hvorvidt læresætningen nu også gav den bedst mulige komprimering af data. Eller om der kunne udvikles en bedre metode. Indtil nu.

Adjunkt på Institut for Datalogi, Aarhus Universitet Kasper Green Larsen (Foto: Lars Svankjær)

Aarhusiansk forsker bag forskningsresultat

Nu er det nemlig endegyldigt bevist, at ”Johnson-Lindenstrauss lemmaet” vitterligt er den bedste metode til komprimering af højdimensionel data. Bag det opsigtsvækkende forskningsresultat står Kasper Green Larsen, adjunkt på Institut for Datalogi, Aarhus Universitet og hans amerikanske forskningskollega Jelani Nelson fra Harvard John A. Paulson School of Engineering and Applied Sciences.

- Det vigtigste bidrag fra vores forskning er, at vi nu har en fuld matematisk forståelse af, hvor meget højdimensionel data kan komprimeres. Udover at dataloger ikke mere skal bruge tid på at forske i metoder til at komprimere data, betyder det også, at vi kan sætte alle kræfter ind på at gøre komprimeringsprocessen hurtigere. Datamængderne bliver kun større i fremtiden, så hurtigere algoritmer er essentielle for fremtidens arbejde med "Big Data", siger Kasper Green Larsen.

Resultatet bliver mødt med stor interesse i matematiske kredse. Blandt andet fra den anderkendte Professor i matematik på Tel Aviv Universitet Noga Alon:

– Johnson-Lindenstrauss lemmaet er et grundlæggende resultat i højdimensionel geometri, men der var et irriterende hul i vores forståelse af, hvor meget man kan reducere dimensionen af en datamængde uden at forvrænge geometrien for meget. Jelani Nelson og Kasper Green Larsen har løst problemet. Deres bevis er en forfriskende demonstration af kraften i en smart kombination af kombinatorisk argumentation med geometriske værktøjer i løsningen af ​​et klassisk problem, siger han til Harvard John A. Paulson School of Engineering and Applied Sciences.

--- Fakta om Kasper Green Larsen ---

Kasper Green Larsen har begået en række fundamentale og internationalt anerkendte bidrag publiceret i 36 artikler, heraf 25 ved de absolut højest rangerede konferencer indenfor teoretisk Datalogi. I 2017 blev han optaget i Det Unge Akademi ved Det Kongelige Danske Videnskabernes Selskab. Modtager af Hartmann Fondens Diplompris 2017. I 2016 modtog han bevillinger fra Villum Young Investigator Programmet (5 mio. kr.) og Aarhus Universitets Forskningsfond (1.6 mio. kr.) til at starte sin egen forskningsgruppe ved Aarhus Universitet. Modtager af Aarhus Universitets Ph.d. pris i 2014. I 2013 blev han tildelt Videnskabsministerens EliteForsk rejsestipendie, som blev brugt til et udlandsophold ved Princeton University. Han har desuden modtaget flere priser for bedste forskningsartikel ved de højest rangerede internationale konferencer i teoretisk Datalogi. Kasper Green Larsen er 31 år gammel og bosat i Viborg med sin hustru og to børn på 8 og 6 år.