Torsdag 31/5. Vi gjennomgikk Oppgave 9 og 8d p? pr?veeksamen, og tok en siste runde p? sp?rsm?l rundt eksamen.
Torsdag 24/5. Vi gjennomgikk oppgave 2, 4, deler av 5, og 7, fra pr?veeksamen,
Mandag 21/5. I f?rste time repeterte vi stoff om DFT, filtre, frekvensrespons, og FFT. I andre time gikk vi over p? del II av kurset, der fokus var p? Haar-waveleten, grunnleggende definisjoner for wavelets, og sammenhengen mellom wavelets og filtre. Vi avsluttet med litt repetisjon om tensorproduktkonstruksjonen, og hvordan denne blir brukt i bildebehandling. De siste forelesningene vil bli brukt til pr?veeksamen, og jeg kan g? gjennom oppgaver p? foresp?rsel fra dere.
Mandag 14/5. Vi avsluttet kapittel 14 i den f?rste timen ved ? ta for oss et eksempel p? bruk av internal point barrier metoden til optimering med ulikhetsbetingelser. Deretter begynte vi med repetisjon, og startet med ? repetere litt om lyd, samt stoffet om Fourierrekker, egenskaper til disse, og Fourierbasis. Vi repeterte ogs? DFT og definisjonen av denne. Neste gang vil vi starte med ? repetere noen enkle filtre, f?r vi repeterer den generelle teorien. Hvis vi rekker begynner vi ogs? ? repetere stoffet om wavelets. Jeg legger ut pr?veeksamen s? raskt som mulig, slik at vi kan bruke tid sammen p? denne mandag, onsdag, og torsdag til uka.
Torsdag 10/5. Vi begynte p? kapittel 14, der vi presiserte hvordan vi kunne bruke Newtons metode i tilfeller der vi ogs? har (likhets-)betingelser. Deretter formulerte vi igjen det mer generelle problemet hvor vi ogs? har ulikhetsbetingelser. Vi definerte "barrier-problemet", som er et problem uten ulikhetsbetingelser, konstruert fra problemet med ulikhetsbetingelser. I barrierproblemet inng?r det vi kalte for en barrierparameter, og vi viste at l?sningen til barrierproblemet konvergerte mot l?sningen til det opprinnelige problemet n?r barrierparameteren g?r mot 0 (ihvertfall i konvekse optimeringsproblemer). Dette ga oss en numerisk metode for ? optimere med ulikhetsbetingelser, siden vi kan bruke Newtons metode p? barrierproblemet. Neste gang vil vi avslutte kapittel 14 med et eksempel, f?r vi g?r over p? repetisjon.
Mandag 7/5. I dag kj?rte vi repetisjon av det vi har gjennomg?tt om ikkeline?r optimering opp til n? (kap. 9-13). Vi listet opp de sentrale begrepene, og supplerte ved ? ta en del av oppgavene fra regne?velsene. Vi hadde mest fokus p? stoff fra kap. 10 og kap. 13, da det er mest rengetunge oppgaver her. Vi regnet blant annet oppgave 9.3.8, 10.3.1, 10.3.4, 10.3.7, 11.2.4, og 13.3.13. L?sningsforslag til alle disse ligger p? kompendiesiden. De to neste gangene blir de siste med nytt pensum, og vil ta for seg kapittel 14.
Torsdag 3/5. Vi avsluttet kapittel 13 ved ? snakke om konveks optimering. F?rst viste vi generelle resultater for optimering n?r funksjonen vi optimerer er konveks, og deretter definerte vi det som kalles det duale optimeringsproblemet, som g?r ut p? ? finne maksimum for en ny funksjon vi definerer, med nye bibetingelser. Vi forklarte sammenhengen mellom det opprinnelige optimeringsproblemet, og det duale optimeringsproblemet. Til slutt gikk vi gjennom Oppgave 12.2.6, som dere ogs? kan finne l?sningsforslag for. P? mandag vil vi oppsummere alt vi har gjort i del III av kurset til n?, samt g? gjennom noen utvalgte oppgaver (send gjerne forslag til oss p? oppgaver).
Mandag 30/4. Vi fortsatte i kapittel 13 med ? snakke om et tilstrekkelig kriterium (en andreordensbetingelse) for minimum ved optimering med betingelser. Deretter gikk vi over til optimeringsproblemer med ulikhetsbetingelser, der vi ogs? formulerte n?dvendige og tilstrekkelige f?rste- og andreordens betingelser for minimum. Betingelsene vi n? fikk for minimum kalte vi for KKT-betingelsene, og vi skrev opp KKT-betingelsene i en del forskjellige eksempler, og tolket betingelsene geometrisk. Neste gang avslutter vi kapittel 13, og tar noen oppgaver for ? summere opp det vi har gjort til n?.
Torsdag 26/4. Vi avsluttet kapittel 12 ved ? snakke om konvergenshastighet og konvergens for Newtons metode, samt litt om hvor n?r vi garantert er et minimum n?r funksjonen er konveks. Deretter begynte vi p? optimering med bibetingelser, der vi utvidet f?resteordensbetingelsen for minimum (slik vi l?rte den i MAT1110) med en andreordensbetingelse n?r vi har bibetingelser (teorem 13.1). Vi forklarte hvordan vi kunne oversette et optimeringsproblem MED bibetingelser til et annet optimeringsproblem UTEN bibetingelser. Vi avsluttet med ? bevise det meste av teorem 13.1, som igjen bruker strategien med ? oversette til et optimeringsproblem uten bibetingelser.
Mandag 23/4. Vi begynte p? kapittel 12, der tema var ? finne minimum til ikkeline?re funksjoner. Vi starter med ? g? gjennom kjent stoff om f?rste- og andreordens betingelser for minimum til funksjoner, samt tilstrekkelige betingelser for n?r vi har et minimum. Spesielt s? vi p? tilfellet for konvekse funksjoner. Deretter gikk vi over p? iterative algorimer for ? finne minimum. Spesielt snakket vi om linjes?kmetoder og backtracking line search, der vi f?rst finner en s?keretning, deretter en steglengde. De linjestegmetodene vi er interessert i kaltes gradientmetoder, og spesielt snakket vi om steepest descent metoden og Newtons metode som viktige eksmpler. Vi skrev ogs? ned Armijos regel uten bevis, som vi bruker i kurset til ? finne en steglengde i v?re linjes?kmetoder. Vi avslutter kapittel 12 p? torsdag.
Torsdag 19/4. Idag var tema metoder for ? l?se ikke-line?re ligninger, kapittel 11. Vi gjennomgikk fikspunkt iterasjon og beviste teorem 11.1. Deretter s? vi p? Newtons metode og viste at den ofte er kvadratisk konvergent (en liten forbedring av teorem 11.2). Til slutt s? vi p? Broydens metode, som er en utvidelse av sekantmetoden til funksjoner av flere variable.
Mandag 16/4. Kapittel 10 var tema i dag, om konveksitet. Enda litt mer bakgrunnsstoff som er grunnlag for optimering. Vi gikk gjennom det hele, men tok ikke alle eksempler.
Torsdag 12/4. I dag begynte vi p? det tredje og siste temaet, ikkeline?r optimering. Vi gjennom gikk kapittel 9 i heftet ganske n?ye, stort sett eksempler p? slike problemer og repetisjon av n?dvendig teori.
Mandag 19/3. Vi fortsatte ? snakke om tensorprodukter av funksjonsrom. Vi s? spesielt p? basisskiftet i tensorprodukter vi f?r for funksjonsrom fra wavelets, satt opp funksjonene som blir en basis for tensorproduktet her, og forklarte i algoritme hvordan vi kan regne ut dette basisskiftet ved hjelp av den tidligere DWT-algoritmen og teorien fra tensorprodukter vi har l?rt til n?. Vi forklarte ogs? at detaljrommene for wavelets blir splittet opp i tre komponenter i tensorprodukter. Vi regnet spesielt p? waveleten for stykkevis line?re funksjoner, der vi kunne enkelt regne ut uttrykk for projeksjonen ned p? lavoppl?sningsrom og detaljrom. P? torsdag vil vi starte med ? kj?re DWT p? bilder for ? illustrere teorien fra i dag, samt oppsummere alt stoffet om wavelets.
Torsdag 15/3. Vi definerte tensorproduktet av to basiser, som kan sees p? som en basis for rommet av alle matriser. Videre forklarte vi at det er mer praktisk ? bruke koordinatmatrise enn koordinatvektor som begrep n?r det gjelder tensorprodukter, og vi viste at koordinatskifte for tensorprodukter kan implementeres p? samme m?te som det ? regne ut tensorproduktet av to lin?re transformasjoner. Vi formulerte algoritmen for ? regne ut dette, og s? deretter spesielt p? basisskiftet i tensorprodukter vi f?r med DCT og DFT. Vi viste noen eksperimenter p? bilder der vi bruker dette, der vi bruker DCT/DFT til bildekompresjon, p? samme m?te som bildestandarden JPEG gj?r det. Deretter skiftet vi fokus til funksjoner. Vi definerte tensorprodukt av funksjoner, funksjonsrom, og basiser for slike, og brukte eksempler med funksjonsrom av polynomer og Fourierrekker til ? forklare at tensorprodukter av funksjoner kan brukes i forbindelse med approksimasjon av funksjoner i to variable. P? mandag fortsetter vi med ? spesialisere dette til funkjonsrom definert fra wavelets.
Mandag 12/3. Vi begynte ? snakke om tensorprodukter, som er teori vi trenger for ? generalisere tidligere resultater fra en til to dimensjoner, det vil si fra lyd til bilder. Vi definerte tensorproduktet av to vektorer, og tensorproduktet av to matriser/line?re avbildninger, med et eksempel p? tensorproduktet av to glattingsfiltre. Videre utledet vi en formel for hvordan vi kan regne ut et slikt tensorprodukt, og forklarte at dette kan implementeres ved ? anvende den ene transformasjonen p? s?ylene, og den andre p? radene. Vi forklarte ogs? at rekkef?lgen p? rad- og s?yleoperasjonene ikke spiller noen rolle.
Torsdag 8/3. I f?rste time tok vi et par siste ting om wavelets: Jeg viste hvordan vi kunne regne ut waveletkoeffisientene for et spesielt tilfelle av en funsksjon, samt gikk gjennom oppsettet rundt filtre og implementasjon av DWT/IDWT som vi trenger for ? komme i gang i oblig 2.I andre time gikk vi gjennom kapitlet om bilder (kapittel 6). Vi snakket litt om hva lys er, hva digitale bilder er (gr?tonebilder, RGB-bilder), og viste hvordan vi kunne lese inn et bilde, vise fram et bilde, samt skrive bilde til fil, med Matlab. Deretter gikk vi gjennom noen operasjoner p? bilder, og viste hvordan disse kan impementeres med Matlab. Eksempler var ? trekke ut fargekomponenter i et bilde, konvertere mellom RGB- og gr?tonebilder, lage negativen til et bilde, kontrastjustering, utglatting, og kantdeteksjon. Neste gang begynner vi p? tensorprodukter (dette vil v?re kapittel 7, som blir lagt ut snart).
Mandag 5/3. I f?rste time startet vi med ? argumentere for at, i filtertolkningen av wavelets, s? er det ene filteret et lavpassfilter, mens det andre er et h?ypassfilter. Vi bekreftet dette ved ? sette opp filterne for Haar-waveleten og waveletene for stykkevis line?re funksjoner, og plotte deres frekvensresponser. Videre definerte vi hva det vil si for en waveletfunksjon ? ha forsvinnende momenter, og forklarte hvorfor waveleter med mange forsvinnende momenter er gode til bruk i kompresjon og f?r ? representere signaler. Vi forklarte at de waveletene vi har sett p? til n? b?de har 0, 1, og 2 forsvinnende momenter, og spilte av delene fra V_m og fra W_m for de forskjellige waveletene, for ? se om vi kunne h?re forskjell p? lyden, avhengig av hvor mange forsvinnende momenter vi har. Neste gang begynner vi p? bilder.
Torsdag 1/3. I f?rste time s? vi igjen p? waveleten for stykkevis line?re funksjoner, og satt opp de tilh?rende basisskiftematrisene som blir brukt i implementasjonen av DWT/IDWT. Det viste seg at disse minnet veldig om filtre, med det unntak at det var to forskjellige s?yler som repeterte seg, i motsetning til en s?yle i en sirkulant Toeplitz-matrise. Vi brukte denne observasjonen til ? sette opp en kobling mellom wavelets og filtre, der to filtre blir brukt til ? regne ut DWT, og to andre filtre blir brukt til ? regne ut IDWT. Denne koblingen gjelder mer generelt, og vi s? p? den ogs? for Haar-waveleten. Vi s? ogs? p? feildelen (delen i W_M-rommene) vi f?r etter en DWT, og plottet denne for de to waveletene vi har sett p? til n?, b?de for lydfilen fra obligen, og et utvalg av matematiske funksjoner. Neste gang vil vi starte med ? tolke filtrene vi st?ter p? i forbindelse med DWT/IDWT som lavpass/h?ypassfiltre, og verifisere dette ved ? plotte frekvensresponsene for disse for waveletene vi har brukt til n?.
Mandag 27/2. I dag definerte vi en multiresolusjonsanalyse av stykkevis line?re funksjoner. Vi gjennomgikk den samme oppskriften som for stykkevise konstanter, men m?tte gi opp kravet om ortogonalitet, b?de av basisfunksjonene i et rom, og kravet om projeksjon ved hjelp av ortogonal projeksjon. Vi klarte likevel ? spalte opp et rom V_1 i et grovere rom V_0 og et feilrom W_0, men n? bare som en direkte sum. Vi utviklet teorien og algoritmene for dette fra t.o. Teorem 5.36.
Torsdag 23/2. Vi fortsatte beskrivelsen av wavelets, og gjennomgikk seksjon 5.2 i detalj. Vi viste spesielt at 'feilrommene', eller 'detaljrommene', har en basis av translater og dilasjoner av en enkelt funksjon (en 'wavelet') som har integral 0. Det hele munnet ut i en algoritme for hvordan et rom V_1 kan spaltes opp ortogonalt i et underrom V_0 av samme type som V_1, og et feilrrom W_0. Deretter generaliserte vi dette til en oppspalting av et fint rom i et grovt rom og en f?lge av feilrom, se teorem 5.18. Til slutt testet vi ut det hele p? lyd og h?rte at om vi fjerner flere og flere av detaljkomponentene blir lyden etterhvert vedlig d?rlig.
Mandag 20/2. I dagbegynte vi p? wavelets. Vi begynte med ? se at et program som Google Earth trenger ? vise geografisk informasjon i forskjellige oppl?sninger, avhengig av hvor langt unna jordkloden i ?yeblikket er. Dette motiverer det som vanligvis kalles multiresolusjonsanalyse, se seksjon 5.1. Deretter gikk vi over til ? se p? det enklest mulige eksemplet av multiresolusjonsanalyse. Byggeklossen er funksjonen som er 1 p? intervallet [0,1) og 0 ellers, og translasjoner og s?kalte dilasjoner av denne funksjonen.
Torsdag 16/2. I f?rste time rundet vi av de siste tingene i seksjonen om filtre, da vi snakket litt mer om h?ypass- og lavpass-filtre, samt viste ved et eksempel hvordan frekvensresponsen forandrer seg hvis man ikke tar med absolutt alle filterkoeffisientene. Vi avsluttet med ? regne gjennom oppgavene til denne uka fra Seksjon 3.3 og 4.1. P? mandag begynner vi ? snakke om wavelets.
Mandag 13/2. I f?rste time snakket vi litt mer om DCT og symmetriske filtre, og sammenhenger med DFT. Vi snakket ogs? litt om effektive algoritmer for DCT, som kunne bruke FFT-implementasjonen. Videre snakket vi igjen om filtre, og fokuserte p? ting som ble lagt til i siste versjon av seksjon 3.3. Vi viste hvordan vi kan regne ut filterkoeffisientene til et product av to filtre, basert p? at vi kun har uttrykk for de to frekvensresponsene. Vi skilte ogs? mellom vektorfrekvensrespons og kontinuerlig frekvensrespons, og satt opp sammenhengen mellom disse. Mer generelt forklarte vi sammenhengen mellom filterkoeffisientene og f?rste s?yle i matriserepresentasjonen av et filter. P? torsdag avslutter vi Fourieranalysedelen av kurset ved ? ta et par ting til fra filterseksjonen. Vi kan ogs? regne en del av oppgavene til denne uka, som dere vel kanskje ikke rekker ? gj?re ellers p? grunn av obligen, samt litt mer repetisjon om DFT og Fourierrekker.
Torsdag 9/2. I f?rste time gikk vi gjennom FFT-algoritmen, der vi viste at en N-punkts DFT kan regnes ut ved hjelp av to (N/2)-punkts DFT'er. FFT-algoritmen er basert p? dette, og vi viste at FFT kan regnes ved hjelp av omtrent Nlog_2 N multiplikasjoner, mot N^2 multiplikasjoner for DFT. Denne store forbedringen er det som gj?r at FFT blir brukt mye i praksis. I andre time forklarte vi motivasjonen bak DCT, som var definert i forbindelse med filtre som bevarte symmetriske utvidelser av vektorer. Tanken er at dette er en god egenskap, siden symmetriske utvidelser hadde raskt kovergerende Fourierrekker (Seksjon 2.3). Vi satt opp et resultat som viste hvordan slike avbildninger blir diagonalisert, og DCT-matrisen var den tilh?rende matrisen med egenvecktorer. DCT blir brukt mer enn DFT i praksis. P? mandag vil vi bruke f?rste time p? DCT og algoritmer for DCT, f?r vi fortsetter med ? runde av Fourieranalyse-delen av pensumet.
Mandag 6/2. Vi avsluttet seksjonen om filtre. F?rst analyserte vi et filter som la til ekko, med tilh?rende frekvensrespons. Deretter s? vi p? et lavpassfilter, som nullet ut DFT-verdier som svarer til h?ye frekvenser, og regnet ut filterkoeffisientene for dette filteret. Videre definerte vi tidsinvarians, og viste at filtre kan karakteriseres som line?re avbildninger som er tidsinvariante. Vi formulerte ogs? noen setninger om frekvensresponsen, som at produktet av to filtre er et nytt filter, der frekvensresponsen til produktet f?s ved ? gange sammen de to frekvensresponsene. Vi brukte dette til ? forklare hvorfor verdiene i Pascals trekant dukker opp i filtre som reduserer diskant/bass. Til slutt forklarte vi hvorfor alternerende fortegn satt p? i et lavpassfilter gir opphav til et h?ypassfilter. Neste gang skal vi snakke om FFT.
Torsdag 2/2. Vi vendte tilbake til glidende middel filteret fra Kapittel 1, og viste at matrisen for denne var det vi kalte en (sirkulant) Toeplitz matrise. Deretter definerte vi filtere formelt, og viste at denne definisjonen falt sammen med det ? v?re en Toeplitz matrise. Videre definerte vi notasjon for filtre, frekvsensrespons, og forklarte sammenhengen mellom DFT og filtre, nemlig at Fouriermatrisen diagonaliserte alle filtre, og at DFT av filterkoeffisientene gir frekvensresponsen. Vi plottet til slutt frekvensreponsen til glidende middel filteret og et tidsforsinkelsesfilter, og ga litt intuisjon p? bruk av frekvensresponsplottet til ? finne egenskaper ved filteret. Vi fortsetter i filterkapitlet neste gang ved ? se p? et filter som legger til ekko, og et lavpassfilter (det vil si et filter som eliminerer de h?ye frekvensene i lyden).
Mandag 30/1. Vi begynte med ? se en gang til p? hvordan Fourier-matrisen framkommer og hvordan dens inverse er. Vi skrev s? opp DFT og IDFT p? komponentform og sammenlignet med formelen for en Fourier-rekke. Ut fra dette utledet vi en sammenheng mellom frekvensene i Fourier-rekka og i DFT og s? hvordan vi kan bruke DFT til ? beregne koeffisientene i Fourier-rekka. Dette finner du bedre forklart i seksjonene 3.2.1 og 3.2.2 i kompendiet.
Torsdag 26/1. I f?rste time avsluttet vi Kapittel 2 ved ? etablere Fourierrekker til noen viktige funksjoner, samt at vi viste noen viktige egenskaper ved Fourierrekker. Deretter begynte vi p? Kapittel 3, der vi f?rst definerte en tilsvarende setting for digital lyd som for funksjoner i Kapittel 2, slik som digitale rene toner, indreprodukt, periodisitet etc. Vi definerte N-punkts Fourierbasis, og viste at denne var ortonormal. Deretter definerte vi Diskret Fourier Transform (DFT) som skifte av basis til Fourierbasisen, og fant uttrykket for Fourier-matrisen, som er den tilh?rende basisskiftematrisen. Vi skrev ogs? opp uttrykket for Invers DFT, og avsluttet med et eksempel der vi regnet ut DFT til en vektor. P? mandag vil vi starte med ? avslutte Seksjon 3.1 f?r vi fortsetter med Seksjon 3.2.
Mandag 23/1. I f?rste time avsluttet vi Seksjon 2.1 med ? avspille Fourierrekkene til trekant/firkantpuls, si litt om konvergens av Fourierrekker, og om n?r Fourierrekkene blir rene sinus- eller cosinusrekker. Deretter definerte vi komplekse Fourierrekker (Seksjon 2.2), kompleks Fourierbasis, og regnet p? basisskiftematrisen fra reell Fourierbasis til kompleks Fourierbasis. For ? definere komplekse Fourierrekker m?tte vi f?rst definere hvordan indreprodukt b?r defineres for komplekse vektorrom. Til slutt viste vi hvorfor Fourierrekkene konvergerer raskere for funksjoner som er mange ganger deriverbare, og brukte det vi kalte den symmetriske utvidelsen av en funksjon til ? speede opp konvergensen ti en funksjon som bare har en diskontinuitet. Vi regnet et eksempel med en trekantpuls-type funksjon. P? torsdag avslutter vi Kapittel 2 med Seksjon 2.4 i f?rste time, f?r vi starter p? Kapittel 3. Kapittel 3 legges straks ut.
Torsdag 19/1. Vi brukte f?rste time p? ? avslutte kapittel 1. F?rst definerte vi firkantpuls og trekantpuls, og lyttet til disse. Deretter fortsatte vi med flere operasjoner p? lyd, slik som ? ? legge til st?y, legge til ekko, redusere diskant, og redusere bass. De siste operasjonene her var s?kalte digitale filtere, som vi skal komme tilbake til senere i kurset. I andre time begynte vi p? kapittel 2 og definerte de grunnleggende begrepene i Fourieranalyse, slik som Fourierrom, Fourierrekker, og Fourierkoeffisienter. Vi viste at Fourierbasisvektorene var ortogonale, og brukte dette til ? finne et uttrykk for Fourierkoeffisientene. Vi avsluttet med ? regne ut Fourierkoeffisientene til firkantpulsen, og skrive ogs? opp hva de ble for trekantpulsen. P? mandag vil vi starte med ? avslutte Seksjon 2.1 med ? avspille Fourierrekkene til trekantpulsene og firkantpulsene, si litt om konvergens av Fourierrekker, og om n?r Fourierrekkene blir rene sinus- eller cosinusrekker (slik de ble det for trekantpuls og firkantpuls). Deretter fortsetter vi p? Seksjon 2.2, 2.3, 2.4, s? langt vi rekker.
Mandag 16/1. Vi startet med litt administrativ informasjon. Deretter begynte vi p? kapittel 1 om lyd. Vi ga en overordnet beskrivelse av hva lyd er og at en gitt lyd kan skrives som en sum av basislyder, noe som er den grunnleggende ideen bak Fourier-analyse. TIl slutt demonstrerte vi noen enkel lydoperasjoner i Matlab.