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.