Fredag 22/5: Vi repeterte del III ved å gå gjennom oppgaver fra kap.5 (KKT-betingelser), kap.4 (steepest descent og newtons metode), og kap. 2 (konvekse mengder og funksjoner). I andre time repeterte vi også noen av de viktigste tingene fra del I og del II. Dette var den siste forelesningen for i år. Regneøvelsene vil gå som vanlig de tre neste ukene, helt frem til eksamen.
Torsdag 21/5: Vi avsluttet kapittel 6 i del III med eksempel 6.3 og 6.4, der vi regnet ut minimum på tre forskjellige måter: Direkte, ved å bruke KKT-betingelser, og ved å bruke barriermetoden. Vi fikk slik verifisert teoremet som sier at minimum for barrierproblemet konvergerer mot minimum for det opprinnelige problemer når mu går mot 0. Disse oppgavene hadde ingen likhetsbetingelser. Vi gjorde også oppgave 6.2 og 6.3, der vi i tillegg hadde likhetsbetingelser. I begge tilfellene så vi på metoder (IPBopt og IPBopt2), som løse barrierproblemet for en sekvens av mu-verdier som gikk mot 0. I morgen repeterer vi resten av del III, og regner flere oppgaver. Dette blir den siste forelesningen i kurset. Vi har tre regneøvelser igjen, og vi bruker disse til å regne eksamensoppgaver
Fredag 15/5. Vi gikk gjennom teorien i kapittel 6 i del III. Vi startet med å forklare hvordan Newtons metode kan generaliseres til å løse optimeringsproblemer også med likhetsbetingelser. Deretter forklarte vi barrierproblemet, som er en metode for å angripe problemer der vi også har ulikhetsbetingelser. I barrierproblemet er det opprinnelige problemet oversatt til en serie problemer uten ulikhetsbetingelser, og vi viste hvordan løsningene på disse konvergerte mot løsningen på problemet MED ulikhetsbetingelser. Neste gang tar vi et par eksempler på bruk av barriermetoden, før vi fortsetter med repetisjon av alt stoffet i kurset.
Fredag 8/5. Vi gikk gjennom resten av kapittel 5 om konveks optimering, og så på et eksempel der vi sammenlignet det primale og duale problemet. Vi regnet også oppgave 3.4. Jeg rakk ikke oppgave 4.7 som planlagt, så vi starter med denne neste gang, før vi fortsetter med kapittel 6.
Torsdag 7/5. Vi gikk gjennom seksjon 5.1 og 5.2. Deler av dette var repetisjon på KKT-betingelsene, men vi gikk lenger ved å formulere andreordensbetingelser for optimering med likhets/ulikhetsbetingelser, og vi så på beviset i tilfellet uten ulikhetsbetingelser. I grove trekk gikk beviset ut på at man oversatte problemet til en serie ubetingede problemer, og tok en grenseverdi. Vi avsluttet med et eksempel, der vi også sjekket eventuelle punkter som ikke er regulære. I morgen avslutter vi kapittel 5, og rekker kanskje starte på kapittel 6.
Torsdag 30/4. Torkel (som var vikar) gikk gjennom hele kap. 4 i del III. Noe av kap. 4 hadde vi også gått gjennom tidligere, siden deler av oblig 3 bygget på det. Neste uke fortsetter vi i kap. 5.
Fredag 24/4. Vi gikk gjennom kapittel 3 i del III. Temaer var ikkelineære likninger, og numeriske metoder for å løse disse. Viktigheten av dette for optimering er at det å finne minimum ofte svarer til å finne nullpunkt til gradienten, slik at å finne minumum kan oversettes til å løse et ikkelineært likningssett. Vi viste først hvordan vi kunne finne fikspunkter ved fikspunktiterasjoner. Vi trengte her en Lipschitzbetingelse, og slike betingelser dukker også opp i en litt mer komplisert form når vi fomulerer når vi har konvergens for Newtons metode. Vi så også på et alternativ til Newtons metode (broydens metode) der vi ikke trenger å ha noe eksakt uttrykk for Jacobimatrisen. På torsdag neste uke skal vi gå gjennom kap. 4.
Torsdag 23/4. Vi gikk gjennom kapittel 2 i del III. Vi startet med å definere konvekse mengder, deretter definert vi konvekse funksjoner, og så på mange eksempler på slike, og hvordan vi kunne definere nye konvekse funksjoner basert på andre konvekse funksjoner. Vi så også på egenskaper for konvekse funksjoner, som at der karakterisert ved å ligge ovenfor sin førsteordens Taylortilnærming. I morgen kommer vi til å gå gjennom kapittel 3 i del III.
Fredag 17/4. Vi gikk gjennom stoff som er nødveldig for å gjøre oppgavene i oblig 3. Dette dreide seg om sek. 5.1 og sek. 5.2 (KKT-betingelser for optimering med likhets- og ulikhetsbetingelser. Vi så spesielt på eksempel 5.9). samt sek. 4.2 (linjesøkmetoder, med vekt på steepest descent og Newtons metode). Det nye med linjesøkmetoder er at vi la an til en mulighet til å velge steglengde, det vil si hvor langt vi skal gå i søkeretningen. Vi avsluttet med et resultat (Armijos regel) som angir en anbefalt steglengde. Den utvidede versjonen av Newtons metode, som dere skal bruke i oblig 3 (newtonbacktrack), bruker denne. Neste uke hopper vi tilbake til kapittel 2, og fortsetter gjennomgangen av del III derfra.
Torsdag 16/4. Vi gjennomgikk kapittel 1 i stoffet som utgjør del III av kurset. Vi startet med å forklare de grunnleggende begrepene i optimering, og startet med et enkelt eksempel der man kunne se minimum direkte. Vi fortsatte deretter med to anvendelsesrettede eksempler. Det ene på porteføljeforvaltning, det andre på maximum likelihood estimering (dette siste er basis for det dere skal gjøre i oblig 3). Vi avsluttet med å sette opp førsteordens- og andreordens Taylortilnærminger i flere variable, som er resultater vi skal bruke mye videre. I morgen skal vi begynne på kapittel 2, men vi kommer sannsynligvis til å ta noe fra kapittel 4 og, slik at vi får gjennomgått raskest mulig det dere trenger for oblig 3.
Fredag 10/4. Vi repeterte alt stoff om wavelets fra del II av kurset. Vi startet med de grunnleggende begrepene som resolusjonsrom og detaljrom, skaleringsfunksjon og moderwavelet, og brukte Haar-waveleten til å regne noen konkrete eksempler. Deretter repeterte vi koblingen mellom wavelet transformer og filtre, og så på de tilhørende frekvensresponsene. Til slutt repeterte vi litt om tensorprodukter. Neste uke starter vi på del III av kurset.
Torsdag 9/4. Vi fortsatte med å snakke om tensorprodukter i en wavelet kontekst. Vi definerte todimensjonal DWT (DWT2) som et koordinatskifte i et tensorprodukt, og så på hvordan dette kan implementeres. Deretter så vi på hva DWT2 gjorde når vi anvender den på bilder. Siden DWT svarer til å anvende et lavpass/høypassfilter, så svarer DWT2 til at vi anvende lavpass/høypassfilter på rader/søyler på alle mulige måter. Siden det å anvende et høypassfilter gjør oss i stand til å detektere kanter, så betyr det at DWT2 på et bilde gjør at vi i de fire hjørnene av et bilde etter DWT2 ser endringer i de forskjellige retningene i bildet. Vi testet alle mulige DWT2 på vårt testbilde (lena.png), og så også litt på hvordan wavelets blir brukt på fingeravtrykksbilder. I morgen repeterer vi alt i del 2 av kurset, og begynner på del 3 neste uke.
Fredag 20/3. Vi fortsatte med teorien for koordinatskifter i tensorprodukter, og viste at disse kan uttrykkes på samme måte som når vi filtrerer bilder vertikalt og horisontalt. Deretter testet vi dette med enkel kode som brukte dft til å gjøre koordinatskifter på bilder. Deretter hoppet vi til 10.1, hvor vi definerte tensorprukter av funkjonsrom, som vi jo trenger for å bruke teorien vår på wavelets. Vi gjorde så DWT koordinatskiftet på bilder, og tolket de nye koordinatene vi får i de fire forskjellige hjørnene av bildet. Vi fortsetter på dette neste gang.
Torsdag 19/3. Vi gikk gjennom en del eksempler på computational molecules, blant annet de som bruker glattingsfiltre. Vi så også på enkle høypassfiltre som kan brukes til kantedeteksjon, som dukker opp når man regner ut de partielle deriverte til et bilde. Vi så på et eksempel hvor vi anvender disse på enkle bilder med sjakkmønstre, for å illustrere hvordan de forskjellige filtrene kan brukes til kantdeteksjon i forskjellige retninger. Vi rakk så vidt begynen på koordinatskifter for tensorprodukter.
Fredag 13/3. Vi startet med å gjøre oppgave 5.5.2a), for å demonstrere det dere trenger å gjøre med forsvinnende momenter i oblig 2. Deretter fortsatte vi med kap. 9 med å definere bilder som matriser. Disse kunne ha enten to eller tre dimensjoner, avhengig av om det var fargebilder eller ikke. Vi så deretter på operasjoner for å lese inn, vise frem, eller skrive bilder til fil, før vi forstatte med operasjoner som å vise frem fargekomponenter, lage gråtonebilder fra fargebilder, eller fremheve kontrast. Til slutt definerte vi det som kalles for computational molecules, og viste at det å anvende et filter på radene i et bilde, og et annet filter på søylene svarte til et computational molecule. Vi fortsetter å se på viktige eksempler på computational molecules neste gang.
Torsdag 12/3. Vi regner et par oppgaver fra seksjon 6.1 på å skrive opp filtre fra gitte MRA-matriser. Deretter så vi på en generalisering av DWT til flere filtre, og forklarte at slike transformasjoner blir brukt i MP3-standarden. Vi gikk så gjennom seksjon 5.5, der vi forklarte hvordan vi kan legge til forsvinnende momenter, og vi forklarte til slutt hvorfor det er bra å ha forsvinnende momenter ved tanke på kompresjon. I morgen begynner vi på kapittel 9 om bilder.
Fredag 6/3. Vi avsluttet seksjon 5.4 ved å forklare kjernefunksjoner som kan brukes til å eksperimentere med stykkevis lineære wavelets, og lyttet til lavresolusjonsdelen i lyd for denne nye waveleten. Vi definerte deretter en generalisering av det vi så for stykkevis konstante og lineære funksjoner, som vi kalte for multiresolusjonsanalyse (MRA). Vi så deretter på hvordan DWT/IDWT koordinatskiftene kunne uttrykkes ved hjelp av filtre, og utledet hvordan DWT kunne regnes ut ved hjelp av to filtre H_0 og H_1, og hvordan IDWT kunne regnes ut ved hjelp av to filter G_0 og G_1. Vi regnet ut de tilhørende filtrene for waveletene for stykkevis konstante og lineære funksjoner, og plottet deres frekvensrespons. For Haar waveleten viste det seg at filtrene G_0, H_0 var lavpassfiltre, G_1, H_1 høypassfiltre, mens for waveleten for stykkevis lineære funksjoner så vi lavpassfiltre, men ikke noe godt høypassfilter. Det viser seg at dette gir grunnlag for å forbedre denne waveleten, og vi skal si mer om dette neste gang.
Torsdag 5/3. Vi startet med oppgave 5.2.1 og 5.3.11 på waveleten for stykkevis konstante funksjoner. Deretter begynte vi på seksjon 5.4, der vi definerte resolusjonsrom for stykkevis konstante funksjoner, og tilhørene basiser for disse. Disse basisfunksjonene var ikke ortogonale, slik at vi ikke kunne konstruere detaljrom ved å ta projeksjon på samme måte. Vi definerte detaljrom og basiser for disse på en litt annen måte. Utover dette definerer man DWT og IDWT som før, og vi avsluttet med å regne ut hvordan matrisene for disse måtte se ut. Vi avslutter 5.4 i morgen med et par eksempler, før vi går løs på seksjon 6.1 med å finne koblinger mellom wavelets og filtre. Det vi avsluttet dagens forelesning med er direkte knyttet til de første deloppgavene i oblig 2, som jeg straks straks skal legge ut. Dere vil få et par ting gratis for oblig 2 hvis dere får med dere morgendagens forelesning.
Fredag 27/2. Vi startet med å vise kode for DWT og IDWT, og demonstrerte denne på lyd ved å nullstille detaljomponent eller lavresolusjonskomponenten, og høre på resultatet. Deretter regnet vi ut DWT for en gitt vektor for hånd, og sjekket at vi fikk det samme med programmet vårt. Deretter regnet vi ut DWT for en gitt funksjon. Neste gang starter vi på seksjon 5.4, waveleten for stykkevis lineære funksjoner.
Torsdag 26/2. Vi begynte på del I med å motivere en annen måte å tilnærme funksjoner på, enn det vi har sett på i del I. Vi starter deretter å bygge opp maskineriet for å lage slike tilnærminger ved å bruke stykkevis konstante funksjoner. Vi definerte resolusjonsrom og detaljrom, og basiser for disse som konstrueres fra prototyper vi kalte for phi og psi. Vi regnet ut projeksjonene ned på disse rommene, samt koordinatskiftematriser mellom basisene for detaljrommene og resolusjonsrommene. Fra dette definert vi DWT (Diskret Fourier Transform). Vi starter i morgen med å programmere oog demonstrere denne.
Fredag 20/2. Vi repeterte hele del I av kurset. Først repeterte vi Fourierrekker, og gjorde to oppgaver som summerer opp det viktigste dere skal kunne gjøre for disse. Deretter repeterte vi DFT, et par enkle oppgaver som bruker viktige egenskaper ved DFT, samt oppgave 2 fra fjorårets eksamen. Til slutt repeterte vi filtre og frekvensrespons, og deres sammenheng med DFT. Vi begynner på del II på torsdag i neste uke med å snakke om waveleten for stykkevis konstante funksjoner (kap. 5 i kompendiet).
Torsdag 19/2. Vi fortsatte med eksempler på filtre. Først så vi på glidende middel filtre, og plottet deres frekvensresponser, som vi så at hadde små verdier for høye frekvenser, og høye verdier for lave frekvenser. Dette motiverte definisjonen av lavpassfiltre og høypassfiltre. Deretter så vi på ideelle lavpassfiltre, filtrene fra MP3-standarden, samt filtre som brukte koeffisienter tatt fra Pascals trekant. Vi forklarte at disse kunne brukes til å lage "bedre" lavpassfiltre. Til slutt så vi på hvordan vi kan lage høypassfiltre ved å legge på et alternerende fortegn i et lavpassfilter, og avsluttet med å demonstrere noen filtre på lyd. I morgen skal vi repetere alt vi har gått gjennom i del I, før vi i neste uke begynner på del II.
Fredag 13/2. Vi startet med et eksempel på hvordan man kan regne ut output fra et filter ved å skrive input som en sum av egenvektorer/Fourierbasisvektorer. Deretter definerte vi den kontinuerlige frekvensresponsen, utledet egenskaper til denne (samt sammenhengen med vektor-frekvensresponsen), og viste ved et par eksempler hvordan plott av denne kan forklare viktige egenskaper ved filtre. Vi så spesielt på et eksempel hvordan man kan regne ut filterkoeffisientene til et produkt av to filtre. Vi definerte også en kompakt notasjon for filtre, og snakket litt om hvordan man kan matlabs/pythons innebygde funksjoner for konvolusjon til å regne ut filtre. Vi rakk såvidt å begynne på seksjon 3.5, ved å se på frekvensresponsen for tidforsinkelsesfiltre og filtre som legger til ekko. Vi fortsetter i seksjon 3.5 neste gang.
Torsdag 12/2. Vi ga en (første) definisjon av digitale filtre basert på filterkoeffisienter, og viste ved et par eksempler hva de kunen gjøre med lyd, slik som å legge til ekko og redusere diskant. Vi forklarte at filtre kunne utrrykkes som matriser, når vi begrenset oss til periodiske vektorer. Vi så at matrisene for filtrene var det vi kalte for sirkulante Toeplitz-matriser, og vi forklarte hvordan vi kunne skrive ned matrisen fra filterkoeffisientene og omvendt. Vi ga deretter en formell definisjon av filtre ut fra å ha Fourierbasisvektorene som egenvektorer, og vi viste at dette var ekvivalent med den første definisjonen vi ga. Vi også at en matrse var et filter hvis og bare hvis operasjonen var tidsinvariant. Vi så til slutt at vi kunne regne ut frekvensresponsen ved å ta en DFT på første søyle i den sirkulante Toeplitz-matrisen, og viste dette på et enkelt eksempel. I morgen starter i med å avlutte seksjon 3.2 med eksempel 3.13, før vi går videre på seksjon 3.3.
Fredag 6/2. Vi gikk gjennom seksjon 2.4 om FFT. Først utledet vi en formel for hvordan en N-punkts FFT kunne regnes ut ved i stedet å regne ut to N/2-punkts FFT. Vi viste at dette reduserte antall reelle multiplikasjoner for N-punkts FFT til 2Nlog_2N, når N er en potens av 2, og vi utfører FFT-algoritmen rekursivt. Vi forklarte også hvordan FFT-algoritmen svarer til en faktorisering av DFT-matrisen i sparse matriser, og funksjonene i kodebasen vår som regner ut FFT-algoritmen (og som dere skal bruke i oblig 1). Vi fortalte også litt om bitreverserings-operasjonen, som våre algoritmer kjører på x i starten av FFT-algoritmen. Neste gang starter vi på filtre (kapittel 3).
Torsdag 5/2. Vi avsluttet seksjon 2.2 ved å vise egenskaper ved DFT som svarer til de vi viste for Fourierrekker, og gikk gjenneom et enkelt eksempel på bruk av disse egenskapene. Deretter forklarte vi sammenhengen mellom Fourierrekker og DFT, nemlig at vi kan regne ut Fourierkoeffisientene til en funksjon i V_(M,T) ved å ta en DFT på vektoren av sampler, så lenge vi tar mer enn 2M sampler. En tolkning av dette var samplingsteoremet, nemlig at en funksjon i V_(M,T) kan rekostruereres fra sine sampler så lenge samplingsfrekvensen er mer enn det dobbelte av høyeste frekvens. Til slutt gikk vi gjennom et lite eksempel der vi gjorde operasjoner på lyd ved å nullstille DFT-indekser som svarer til høye eller lave frekvenser. Dette svarer til å anvende et digitalt filter, og dette er tema for neste uke. I morgen skal vi gjennomgå FFT, seksjon 2.4.
Fredag 30/1. Vi begynte med å forklare en metode for å øke konvergenshastigheten til en Fourierrekke, ved å se på den symmetriske utvidelsen til en funksjon. Deretter hoppet vi til seksjon 2.2, der vi etablerte et rammeverk for å se på frekvenser i digital lyd. Vi definerte N-punkts Fourierbasis (også kalt digitale rene toner), som viste seg å være ortonormale under det standard skalarproduktet i R^N, og Fouriermatrisen som koordinatskiftet fra standardbasisen til Fourierbasisen, samt diskret Fourier transform. Vi fant også uttrykk for Fouriermatrisen, og viste hvordan vi kunne regne ut diskret Fourier transform for enkle uttrykk som involverer cos og sin. Vi regnet også ut diskret Fourier transform til en firkantpuls. Vi starter neste gang med å formulere og vise viktige egenskaper for DFT (teorem 2.21), før vi tar et enkelt eksempel på bruk av disse egenskapene i eksempel 2.22. Jeg utfordret dere til å ta dette eksempelet på tavla neste gang, så det er fritt fram for dere for dette på torsdag (en pose bamsemums til den som tør å ta eksempel 2.22 på tavla).
Torsdag 29/1. Vi definerte komplekse Fourierbasisvektorer og komplekse Fourierkoeffisienter. Disse var veldig like de reelle Fourierbasisvektorene og de reelle Fourierkoeffisientene, men var litt mer praktiske enn disse i den del tilfeller, blant annet fordi den komplekse basisen var ortonormal. Vi formulerte så en del viktige egenskaper ved Fourierrekker, slik som hva som skjer når man forskyver funksjonen i tid, eller hva som skjer når man ganger en funksjon med et komplekst eksponential. Til slutt forklarte vi hvorfor trekantpulsens Fourierrekke konvergerte raskere enn firkantpulsens Fourierrekke. Dette hadde sammenheng med at vi kunne få firkantpulsen ved å derivere trekantpulsen, og vi kunne regne ut Fourierrekka til den deriverte ved å derivere Fourierrekka. Fra denne sammenhengen var det klart at Fourierkoeffisientene til trekantpulsen kunne fås fra firkantpulsens ved å dividere med n,og da vil disse gå raskere mot 0. Vi starter morgendagen med å avslutte seksjon 1.4, før vi begynner på seksjon 2.2.
Fredag 23/1. Vi startet med et par eksempler til på mulige operasjoner på lyd, slik sp å spilel av en lyd baklengs, og med halv og dobbel samplingsrate. Deretter begynte vi på seksjon 1.2 ved å definere Fourierrommene og dens basisfunksjoner av rene toner, samt Fourierrekker. Vi viste at disse funksjonene var ortogonale, og hvordan koordinatene i Fourierbasisen (også kalt Fourierkoeffisientene) da kunne regnes ut ved hjelp av ortogonalt dekomposisjonsteorem. Vi regnet ut Fourierrekka til firkantpulsen, og så på hvor gode tilnærminger til firkantpulsen disse ga ved å høre på de tilsvarende lydene. Vi observerte også at Fourierrekka til firkantpulsen var en sinusrekka, og vi forklarte at det samme vil være tilfelle for alle antisymmetriske funksjoner. Neste gang fortsetter vi seksjon 1.3.
Torsdag 22/1. Vi ga en introduksjon til kurset, samt diverse praktisk informasjon angående forelesninger, regneøvelser, obligatoriske oppgaver, kompendiet, og websidene for kurset. Deretter gikk vi gjennom seksjon 1.1, ved å forteller om to sentrale egenskaper ved lyd: lydstyrke og frekvens. Vi definerte rene toner, som er våre byggeklosser for å lage mer kompliserte lyder, og forklarte hvordan vi kunne generere slike og høre på dem med matlab eller python. Vi så også på trekantpulsen og firkantpulsen, som er andre typer lyder, og hørte også på disse.Vi fikk vist noe av det man trenger å skrive for å lese/avspille/skrive lyd. Vi fortsetter med et par eksempler til på dette i morgen slik at dere har lært alt dere trenger for å løse oppgavene til neste uke. Deretter fortsetter vi med Fourierrekker i Seksjon 1.2.