20/5. Vi gjennomgikk i dag alle oppgavene på prøveeksamen. Løsninsgforslag er også lagt ut på kurssidene. Dette var den siste forelesningen i kurset. Gruppene går frem til eksamen.
16/5. Vi repeterte stoffet om filtre, ved blant annet å regne oppgaver om filter fra tidligere gitte prøveeksamen. Deretter repeterte vi stoffet om wavelets, og vi regnet oppgaven om wavelets som ble gitt på eksamen 2012. Tirsdag blir siste forelesning, og da kommer jeg til å regne gjennom prøveeksamen.
13/5. Vi fortsatte repetisjon fra del III med oppgave 1.9a og b, 2.16, 2.5a, samt oppgave 8 fra prøveeksamen 2013. Deretter repeterte vi Fourierrekker, og deler av DFT. På fredag fortsetter vi med DFT, samt resten av del I og II.
9/5. Vi avsluttet Kapittel 6 med Eksempel 6.4, og gikk deretter løs på repetisjon og oppgaver i del III. Vi fikk tatt oppgave 5.11, 5.14, 4.9, 3.4, og 3.5. Jeg gikk også gjennom et par ting som dere har lurt på i forbindelse med oblig 3. Neste gang fortsetter jeg med oppgaver fra kap. 1 og 2 i del III, før jeg begynner på repetisjon og oppgaver fra del I og II. Jeg legger ut en prøveeksamen i løpet av neste uke også.
6/5. Vi startet på kapittel 6 i del III ved å utvide Newtons metode til problemer med lineære likhetsbetingelser. Deretter så vi på en tilnærminger til å løse problemer også med ulikhetsbetingelse, ved å tilnærme med et problem med kun likhetsbetingelser, som vi kalte barrierproblemet. I barrierproblemet baker vi inn ulikhetsbetingelsene inn i en såkalt barrierfunksjon, som vi bruker til å modifisere objektivfunksjonen med, og vi har også en barrierparameter med. Når denne går mot 0 blir problemet mer og mer likt det opprinnelige problemet. Vi beviste at interior point barrier metoden, der vi lar barrier-parameteren gå mot 0, finner løsninger nær minimum for f. Til slutt så vi på en algoritme for interior point barrier metoden, og testet denne på eksempel 6.3. Vi avslutter kapittel 6 neste gang, og starter på repetisjon.
2/5. Vi så på konveks optimering med tilhørende resultater, der det antas at f og ulikhetsbetingelsene er konvekse funksjoner (med lineær likhetsbetingelse). Vi så på det duale problemet, og forklarte at for konvekse problemet så er det duale og det opprinnlige problement ekvivalente, under enkelte betingelser. Vi så også et eksempel på at det duale og det opprinnelige problemet kan være forskjellige, og hvilket av dem som er enklest å løse kan variere. I andre time løste vi også oppgaver 4.7, som er en vanskelig oppgave om steepest descent. Vi starter på kap. 6 neste gang.
29/4. Vi formaliserte igjen KKT-betingelsene med kun likhetsbetingelser, og beviste hvorfor disse er oppfylt i lokale minimum. Deretter ga vi en tolkning av hvorfor gradienten til f er ortogonal på tillatte retninger (retninger man kan gå som ikke bryter med likhetsbetingelsene), og andreordensbetingelser uten bevis. Vi forklarte også uten bevis det tilsvarende resultatet med ulikhetsbetingelser. I andre time regnet vi eksempler, der vi hadde konkrete f og betingelsesfunksjoner, og viste at det fort blir veldig mye regning når man løser KKT-betingelsene, spesielt når man også sjekker mulighetene der punktene ikke er regulære. Neste gang fortsetter vi i 5.3.
25/4. Vi startet med å forklare KKT-betingelsene for optimering med likhets- og ulikhetsbetingelser, og viste hvordan disse kunne brukes i forbindelse med oblig 3. Deretter så vi på eksempel 5.9, som også viste hvordan KKT-betingelsene sier helt generelle ting om minimum til en funksjon ved ulikhetsbetingelser, uansett f. Neste gang vil vi gjøre utregningene med konkrete f, og mer innfløkte betingelser. Vi gikk så tilbake til kapittel 4, der vi viste de siste resultatetene på minimering av konvekse funksjoner (lokalt min er globalt min, avstand fra minimumsverdi beskrives ved kvadratet av lengden til gradienten, samt konvergens av Newtons metode). Vi fortsetter i kap. 5 neste gang. Da kan jeg også gi panikkhjelp til obligen, til de som trenger det.
22/4. Vi brukte Taylortilnærmingene fra kap. 1 til å finne nødvendige og tilstrekkelige andreordensbetingelser for minimum av funksjoner. Deretter så vi på linjesøkmteoder, som er iterative metoder for å finne minimum til slike funksjoner numerisk. Disse utledes ved å minimere Taylortilnærmingen i stedet for funksjonen. Ved å bruke førsteordens Taylortilnærming får vi linjesøkmetoden som kalles steepest descent (søkeretning=den negative gradienten). Ved å bruke andreordens Taylortilnærming får man Newtons metode. I tillegg til valg av søkeretning er valget av steglengde viktig i linjesøkmetoder, og vi definerte backtracking linjesøk, som er en regel for valg av steglengde, som viser seg å fungere bra for Newtons metode. Til slutt så vi på en implementasjon av backtracking linjesøk med Newtons metode, som dere skal bruke i oblig 3. Vi avslutter kapittel 4 neste gang, og fortsetter på kap. 5.
11/4. Dagens tema for lösning av ikke-lineære ligninger, kapittel 3 i seksjon 3. Vi beviste fikspunktteoremet i detalj og gjennomgikk Newtons metode, med utgangspunkt i hvordan metoden ser ut i tilfellet med en variabel. Til slutt så vi raskt på Broydens metode.
8/4. Vi fortsatte med optimering, denne gangen med konveksitet, kapittel 2 i del 3 av kompendiet. Vi fokuserte på de overordnede tankene: At konveksitet ofte gir garanti for eksistens og entydighet av ekstrempunkter, og at ganske enkle 'byggekloss-resultater' gjør det mulig å vise konveksitet i ganske generelle situasjoner.
4/4. Dagens forelesning var introduksjon til optimering, kapittel 1 i del 3 av kompendiet. Vi så på et par av eksemplene i seksjon 1.2 og repeterte de ulike versjonene av Taylors formler i seksjon 1.3.
1/4. Forelesningen i dag var en oppsummering av wavelets, kap. 5, 6, 9, 10. Mesteparten av tiden brukte vi på å se på den generelle wavelet-strukturen, eksemplifisert ved de tre typene wavelets i kapittel 5 og hvordan disse kan implementeres. Vi snakket spesielt om det faktum at filterrepresentasjon egentlig bare er en permutasjon av den naturlige notasjonen i kapittel 5 som er hendig for å kunne bruke standard filtermetoder i programmer som Matlab og Mathematica.
21/3. Tema i dag var eksempler på bruk av tensorprodukter av wavelets i forbindelse med bildeanalyse, primært seksjon 10.3 i kompendiet. Vi så hvordan wavelettransformen naturlig deler et bilde fire like deler, en grov tilnærming og tre 'wavelet-komponenter' som svarer til å derivere bildet og dermed framhever ulike typer kantinformasjon.
18/3. Vi startet med å definere tensorprodukter av funksjonsrom og så hvordan basisskifte kan beregnes i denne settingen, se seksjon 10.1. Vi repeterte deretter tankegangen bak wavelets og så hvordan waveletformalismen kan utvides til tensorprodukter, se seksjon 10.2.
14/3. Vi definerte beregningsmolekyler og så hvordan disse gir opphav til naturlige operasjoner på bilder så som glatting og kantdeteksjon, se seksjon 9.3. Disse kan naturlig og enkelt konstrueres fra en-dimensjonale filtre ved hjelp av tensorprodukter, se teorem 9.17 og teorem 9.22. Vi demonstrerte med eksempler i Mathematica som vist i seksjon 9.3.
11/3. Tema var definisjon og grunnleggende aspekter av digitale bilder, seksjon 9.1 i kompendiet. Basert på dette demonstrerte vi en del elementære operasjoner på bilder, se seksjon 9.2. Jeg brukte Mathematica og ikke Matlab, men operasjonene er de samme.
4/3. Vi startet med Seksjon 6.3 ved å forklare funksjoner som regner ut DWT og IDWT, som tar filtrene i filterrepresentasjonen fra sist forelesning som input. Deretter definerte vi en litt annen wavelet for stykkevis lineære funksjoner (Seksjon 5.5), der vi la til det vi kalte forsvinnende momenter. Vi forklarte også løst hvorfor det er bra for psi-funksjonen å ha mange forsvinnende momenter. Til slutt testet vi ut programmer som spilte av detaljkomponenter og tilnærminger fra de tre waveletene vi har sett på til nå, og sammenlignet det vi hørte. Vi avsluttet med å regne et par av oppgavene fra Seksjon 5.2 og 5.3. På fredag er forelesningen avlyst. Knut tar over tirsdag 11/1, og fortsetter da med Kap. 9.
28/2. Vi gikk gjennom hele Seksjon 6.1. Vi repeterte sammenhengene mellom basisfunksjoner som ga oss DWT og IDWT koordinatskiftematrisene, og vi så at disse matrisene hadde en repeterende struktur, som lignet på det vi så for filtre. Fra dette utledet vi hvordan DWT kunne regnes ut ved hjelp av to filtre H_0 og H_1, og hvordan IDWT kunne regnes ved hjelp av to fikter G_0 og G_1. Vi regnet ut disse filtrene i tilfellene med stykkevis konstante og stykkevis lineære funksjoner, og plottet de tilhørende frekvensresponsene. Det kunne virke som G_0, H_0 var lavpassfiltre, og at G_1, H_1 var høypassfiltre, og at H_1 kunne fås fra G_0 ved å legge på alternerende fortegn. På tirsdag fortsetter vi med Seksjon 6.3 og 5.5.
25/2. Vi fortsatte med Seksjon 5.4, der vi i stedet så på tilnærminger med stykkevis ineære funksjoner. Resolusjonsrommene ble nå definert som rom av stykkekvis lineære funksjoner, og vi definerte en ny skaleringsfunksjon phi, som kunne brukes til å beskrive basiser for disse resolusjonsrommene. Basisfunksjonene var nå ikke lenger ortogonale, slik at det ikke var så lett å finne tilnærminger ved å regne ut projecksjoner. I stedet definerte vi en annen type tilnærming fra lavereresolusjonsrommene, og fant også en moderwavelet psi som kunne beskrive avvikene mellom funksjoner og deres lavereordenstilnærminger, og vi kunne bruke disse til å definere detaljrom. Som for stykkevis konstante funksjoner fikk vi dermed definert DWT som et koordinatskifte mellom basiser vi definerte, som splittet en funksjon opp i en lavereresolusjonstilnærming, og en detaljdel. Vi forklarte også i Seksjon 5.6 at multiresolusjonsanalyse (MRA) er en generalisering av det vi bygget opp for stykkevis konstante og lineære funksjoner. Neste gang fortsetter vi i Kapittel 6.
21/2. Vi fortsatte på Kaittel 5 ved å definere DWT, høyere ordens detaljrom, og DWT over flere nivåer. Deretter så vi på en implementasjon av DWT, og testet ut denne på lydfila vår. Vi gjenkjente første halvdel av DWT av lydfila som en tilnærming til lyden, mens andre halvdel er feilen i denne tilnærmingen. Vi testet også å høre på tilnærmingen, og å høre på feilen, for forskjellige antall nivåer i DWT. Til slutt regnet vi ut en DWT for hånd, på en vektor som var stykkevis konstant, og sjekket at vi fikk samme svar som matlab. Neste gang fortsetter vi med stykkevis lineære wavelets i seksjon 5.4.
18/2. Vi begynte på Kapittel 5 ved å definere en ny måte å tilnærme funksjoner på ved hjelp av stykkevis konstante funksjoner. Vi definerte resolusjonsrom, og ortonormale basiser for disse som man får ved å forskyve og presse sammen en funksjon phi. Vi definerte detaljrom som ortogalkomplementet til resolusjonsrommene, og ga en tolkning på hvordan vi buker disse rommene i forbindelse med bilder. Vi regnet ut formler for å projisere ned i resolusjonsrommene og detaljrommene. Vi fortsetter med dette neste gang, for å definere Diskret Wavelet Transform.
14/2. Vi repeterte i dag hele del I av kurset. Vi startet i Kapittel 1 med definisjonen av Fourierrekker, og utregning av noen Fourierkoeffisienter. Deretter fortsatte vi med DFT i Kapittel 2, og noen enkle utregninger av DFT of FFT. Til slutt repeterte vi definisjonen og ekvivalente karakterisinger av filter i Kapittel 3, samt hvordan vi bruker frekvensresponsen til å analysere filtre, og hvordan man bruker DFT til å regne ut denne. Neste gang starter vi på Kapittel 5 i del III.
11/2. Vi fortsatte i Seksjon 3.5 med flere eksempler på filtre. Først så vi på glidende middel filtre, og deretter definerte vi høypass- og lavpassfiltre. Vi så også på ideelle lavpassfiltre, som viste seg å ha mange filterkoeffisienter, og så på hva som skjedde med frekvensresponsen når vi droppet en del av filterkoeffisientene. Deretter snakket vi om filtre med koeffisienter fra Pascals trekant, som viste seg å være gode lavpassfiltre. Vi så også at vi kunne får et høypassfilter fra et lavpassfilter ved å legge på et alternerende fortegn, og vi forklarte at filtre med koeffisienter fra Pascals trekant kan faktoriseres som en potens av filtre som midler to naboer, eller trekker to naboer fra hverandre (derivasjon). Vi avsluttet med Seksjon 3.6 ved å vise at digitale filtre også kan karakteriseres ved at de er tidsinvariante. Fredag repeterer vi hele del I, før vi tirsdag i neste uke begynner på del II.
7/2. Vi fortsatte på kontinuerlig frekvensrespons, og forklarte hvordan denne brukes til å analysere egenskaper til filteret ved å se på hva den gjør ved forskjellige frekvenser. Vi viste egenskaper, spesielt hvordan vi kan regne ut kont. frekvensrespons til et produkt ved å gange samme frekvensresponsene. Vi definerte kompakt filternotasjon, og brukte denne notasjonen på flere av filterme. Vi snakket også om sammenhengen med konvolusjon, matlabs conv-funksjon, og rader i Pascals trekant. Vi startet så på seksjon 3.5 ved å se på de to enkleste filterne, tidsforsinkelses- og ekkofilter. Vi avsluttet timen med tre av ukesoppgavene til denne uka. Vi fortsetter på 3.5 neste gang.
4/2. Vi startet med en ny definisjon av digitale filtre ved å kreve at Fourier basisvektorene skal være egenvektorer. De tilhørende egenverdiene kalles frekvensresponsen. Vi viste at en matrise er et digitalt filter hvis og bare hvis den er en sirkulant Toeplitz matrise, og vi viste at egenverdiene for filtre kan regnes ut ved hjelp av en DFT på første søyle i matrisen. Dette gjør at filtre er enkle å analysere med tanke på egenverdier/egenvektorer. Videre så vi på hvordan vi kan regne ut output fra et filter ved å skrive input som en sum av Fourierbasisvektorer. Vi definerte kontinuerlig frekvensrespons, som er en funksjon som fanger opp alle verdiene til vektor-frekvensresponsen fra Seksjon 3.2, for all N. Til slutt regnet vi et par oppgaver. Vi fortsetter i Seksjon 3.3 på fredag.
31/1. Vi startet med Seksjon 2.8, der vi først viste et resultat som reduserte utregningen av en DFT av lengde N til to DFT'er av lengde N/2. Vi viste en algoritme som brukte dette, kalt FFT-algoritmen, og vi viste at algoritmen reduserte antall (reelle) multiplikasjoner for FFT'er av lengde N=2^r til 2Nlog_2 N. Dette er en betydelig reduksjon sammenliknet med matrisemultiplikasjon med Fouriermatrisen, som krever 4N^2 reelle multiplikasjoner (N^2 komplekse), noe som gjør FFT-algoritmen veldig nyttig. Vi definerte så filtre og filterkoeffisienter i Seksjon 3.1, og forklarte at matrisene disse gir opphav til er sirkulante Toeplitzmatriser. Vi forklarte også en regel for å skrive opp den sirkulante Toeplitzmatrisen fra filterkoeffisientene, og omvendt. I farten glemte jeg å avslutte timen med å regne et par av ukesoppgavene, som vi ble enige om, og vi tar derfor dette på slutten på tirsdag. Vi starter med Seksjon 3.2 på tirsdag.
28/1. Vi avsluttet Seksjon 2.4 ved å regne ut DFT av firkantpuls-type lyder, formulererte egenskaper til DFT (analoge til egenskapene til Fourierrekker) , og beviste to av dem. Vi fortsatte så på Seksjon 2.5, der vi formulerte og beviste sammenhengen mellom Fourierkoeffisienter og DFT-koeffisienter gjennom sampling. Konsekvensen av dette resultatet var at funksjoner i Fourierrommene kan rekonstrueres fra samplene, så lenge samplingsfrekvensen er dobbelt så høy som høyeste frekvens i lyden. Dette er det enkleste tilfellet av det som kalles samplingsteoremet, som sier at det samme gjelder også for funksjoner som ikke nødvendigvis er periodiske. Vi fortsatte så på Seksjon 2.6, der vi først forklarte sammenhengen mellom frekvens og DFT-indeks, hva som svarer til høye/lave frekvenser, og hvordan vi kan bruker dette sammen med DFT, IDFT til å eksperimentere på lyd ved å høre på lave frekvenser i lyden. Vi starter neste gang med å avslutte Seksjon 2.6, før vi fortsetter med FFT i Seksjon 2.8.
24/1. Vi avsluttet Kapittel 1 med Seksjon 1.7, der vi viste et par egenskaper ved Fourierrekker. Deretter begynte vi på Seksjon 2.3, der vi definerte indreprodukt og diskret Fourierbasis, og viste at denne var ortonormal. Vi definerte så Diskret Fourier Transform (DFT) som et koordinatskifte, Fourierkoeffisienter, Fouriermatrisen som den tilhørende koordinatskiftematrisen, og forklarte at Fouriermatrisen var en unitær matrise. Vi viste et eksempel der man kunne regne ut DFT ved først å uttrykke vektoren i Fourierbasisen, dvs. uten at man ganget med Fouriermatrisen. Vi så også på en manuell utregning av DFT, ved at man skrev ut selve Fouriermatrisen, og gjennomførte matrisemultiplikasjonen. Neste gang starter vi med å avslutte Seksjon 2.4.
21/1. Vi startet med å vise at Fourierrekkene til symmetriske/antisymmetriske funksjoner er cos/sin-rekker. Deretter fortsatte vi på seksjon 1.5, der vi definerte kompleks Fourierbasis og forklarte at den var ortonormal, komplekse indreprodukt og vektorrom, samt komplekse Fourierfoeffisienter. Vi viste et eksempel på utregning av Fourierkoeffisienter ved hjelp av Fourierintegralene, og et annet der vi slapp å regne ut disse integralene. Vi forklarte i Seksjon 1.6 hvorfor funksjoner som er mange ganger deriverbare har raskere konvergerende Fourierrekker, og forklarte ut fra dette hvorfor trekantpulsens Fourierrekke konvergerer raskere enn firkantpulsens. Vi avslutter kapittel 1 neste gang, og begynner å snakke om DFT i kapittel 2.
17/1. Vi startet med å definere funksjonsrommene (Fourierrommene), som vi skal bruke til å tilnærme lyder. Fourierrekka til en funksjon definerte vi som en beste tilnærming ra disse rommene. Lydene i Fourierrommene svarer består av alt som kan skrives som lineærkombinasjoner av rene toner med bestemte frekvenser. Vi viste at disse rene tonene (sin/cos) var ortogonale, og vi brukte dette i kombinasjon med ortogonalt dekomposisjonsteorem til å finne formler for Fourierkoeffisientene, dvs koeffisientene til de rene tonene. Vi regnet ut Fourierrekka til firkantpulsen, og så også på trekantpulsen. For å demonstrere at Foruierrekkene til disse konvergerer mot funksjonen, så lyttet vi på de forskjellige Fourierrekkene, for å høre om det var noen forskjell fra selve funksjonen, for forskjellige N. Matlabkoden for dette kan du finne her. Vi starter neste gang med å forklare hvorfor Fourierrekkene for firkant/trekantpulsene ble rene sin/cos rekker, og fortsetter deretter på seksjon 1.4.
14/1. Vi startet med en del praktisk informasjon om kurset, og fortsatte med å si litt om hva lyd er, samt måleenhetene Pascal og Decibel. Deretter snakket vi om periode og frekvens for lyder, rene toner, og hørte på litt forskjellige rene toner. Vi så også på trekantpulsen og firkantpulsen, som eksempler på periodiske lyder som ikke er rene toner. Vi snakket så om sampling av lyd og digital lyd, og definerte samplingsfrekvens. Til slutt viste vi hvordan man kan bruke Matlab til å lese inn lyder fra lydfiler, generere lyder slik som rene toner, firkantpuls og trekantpuls, og avspille disse. Matlabkoden for dette kan du finne her.