Brza Furijeova transformacija je postala još brža

U svetu informatike (kao nauke) nema važnijeg algoritma od Furijeove transformacije, a stručnjaci sa MIT-a su našli načina da ga ubrzaju.

Furijeova transformacija je jedan od fundamentalnih koncepata u informatičkoj nauci. Ona predstavlja metod za prikazivanje ne regularnih signala – kao što je dinamička promena napona u žici koja povezuje  MP3 uređaj sa zvučnikom – kao kombinacija čistih učestanosti (frekvencija). Njena primena je univerzalna u obradi signala, a može se iskoristiti prilikom kompresije slike ili digitalnog audio zapisa. Sem toga, može pomoći u rešavanju diferencijalnih jednačina ili u praćenju dinamike tržišta i berze.

Tajna leži, u stvari, u algoritmu koji nazivamo brza Furijeova transformacija, razrađena šezdesetih godina 20. veka, koja omogućava brži račun Fourijeove transformacije, tako reći, u letu. Od kada je algoritam razvijen i ušao u primenu, pa sve do sadašnjeg trenutka, ljudi su se pitali da li je moguće osmisliti neki novi algoritam koji bi bio još brži.

Tokom januara meseca na simpozijumu Diskretnih algoritama (Symposium on Discrete Algorithms [SODA]), grupa istraživača sa MIT univerziteta je predstavila novi algoritam koji, u velikom broju praktičnih primena, poboljšava brzu Furijeovu transformaciju. Pod određenim uslovima, poboljšanje može biti značajno – desetostruko ubrzanje. Novi algoritam je posebno koristan prilikom kompresije digitalne slike. To bi omogućilo uređajima kao što je smartphone da bežičnim putem emituju video materijal, a da im taj proces ne iscrpi skoro svu energiju iz baterija ili da ne potroše mesečni Internet protok za mnogo kraće vreme.

Poput postojećeg starog algoritma, i novi radi sa digitalnim signalima. Digitalni signal je, niz brojeva – diskretan uzorak analognih signala, kao što je zvuk muzičkog instrumenta. Oba algoritma postojeći digitalni signal sa određenim brojem signala izražavaju (prikazuju) kao težinsku sumu (weighted sum) istog broja frekvencija.

Pojam težinski uz reč „suma“ proizilazi iz činjenice da neka vrednost, u ovom slučaju frekvencija ima veći udeo u konačnom rezultatu (veću „težinu“). Zaista, mnoge frekvencije imaju zanemarljivi udeo u konačnom rezultatu, pa ih slobodno možemo otpisati. Ovo je razlog zašto je Furijeova transformacija korisna prilikom kompresije digitalnih podataka. Blok od 8×8 piksela (piksel – 1 tačka na monitoru) se može posmatrati kao signal od 64 podataka ili kao suma od 64 različite frekvencije. Međutim, kao što istraživači pokazuju u svom skorašnjem radu, empirijska istraživanja pokazuju da, u proseku, možemo zanemariti 57 od tih 64 frekvencije. Sa druge strane, gubitak kvaliteta slike je minimalan.

Teško deljenje

Signali koje Furijeova transformacija formira na osnovu relativnog malo broja „teških“ frekvencija se nazivaju „sparse“ (oskudan). Novi algoritam „prepoznaje“ težinu najtežih frekvencija u signalu; što je signal oskudniji, to je veće ubrzanje koje algoritam daje. U krajnjem slučaju, ako je signal dovoljno oskudan, algoritam ga može interpretirati po principu slučajnog izobara, umesto da ga čita potpuno.

„U prirodi, većina normalnih signala su ’oskudni’.“ tvrdi Dina Katabi (Dina Katabi),  jedan od članova istraživačkog tima koji je razvio novi algoritam. „Razmotrimo, na primer, snimanje neke muzičke partiture kamerne muzike. Krajnji, kombinovani zvuk se sastoji od zvukova koje proizvode nekoliko instrumenata i to jednu notu u trenutku. Sa druge strane, snimanje svih mogućih instrumenata koji proizvode sve moguće zvukove u isto vreme ne bi bilo oskudno – ali to ne bi bio signal do koga je nekome stalo!“

Imajući ovo u vidu, kao neku vrstu definicije prirode signala oko nas, nastao je novi algoritam. Autori su profesori Katabi i Piotr Indyk, oboje sa MIT odseka koji se bavi kompjuterskom naukom i veštačkom inteligencijom. Uz njih, na istraživanju su radili i Erik Prajs (Eric Price) i Haitham Hasanej (Haitham Hassanieh), njihovi studenti. Novi algoritam se bazira na dva ključne ideje. Prva stvar je postojeći signal podeliti na uže propusne signale, i to tako da ti odsečci sadrže samo frekvencije sa velikom težinom.

Prilikom obrade signala, osnovni alat za izdvajanje frekvencije je filter. Međutim, filtri često imaju nejasne ili mutne granice. To znači da će određeni opseg frekvencija proći kroz filter, više manje ne promenjen, a frekvencije odmah van opsega filtera će biti prigušene. Što je veća razlika između opsega filtra i neke frekvencije, to će ona biti više prigušena. U krajnjem slučaju, neke frekvencije daleko od opsega neće uopšte proći i biće otklonjene zahvaljujući filtru.

Opisani princip rada filtra može dovesti do situacije gde će se neka od frekvencija sa velikom težinom naći na ivici opsega filtra i samim tim u situaciji da bude prigušena i zanemarena. Zbog toga, istraživači su morali naći efikasan način da kombinuju filtre sa različitim opsezima koji se preklapaju, sve sa ciljem da ni jedna teška frekvencija u ciljanom opsegu ne završi prigušena, ali da granice između isečaka i dalje ostanu dovoljno oštre.

Kada jednom izoluju neki segment spektra, istraživači su i dalje u poziciji da moraju odrediti koje su frekvencije najteže u datom delu. To su postigli učestalim seckanjem posmatranog dela spektra na manje delove i zadržavajući samo one gde je veći deo signala bio skoncentrisan. Za sada, prema radu koji je još neobjavljen,  istraživači opisuju znatno efikasniju tehniku, koja se oslanja na strategiju obrade signala koju koriste 4G telefonske mreže. Frekvencije se mogu posmatrati kao sitna talasanja, ali se zato mogu razmatrati kao oscilacije; obradom istog dela opsega ali u različitim trenucima vremena, istraživači mogu ustanoviti koja je frekvencija dominantna u određenom ciklusu oscilacije.

Istraživanje i rezultat koji sam upravo opisao nije prvo u ovoj oblasti. Dva istraživača sa univerziteta u Mičigenu (SAD), Ana Gilbert (Anna Gilbert) i Martin Štraus (Martin Štraus) su već ranije predložili algoritam koji bi ubrzao svemoguću brzu Furijeovu transformaciju. Međutim, njihov algoritam doprineo ubrzanju u znatno manjem broju slučajeva nego ovaj novi algoritam sa MIT-a. Možda je čak i bolji ali manju vrednost u primenjivanju, manja mu je težina. 😉

Poenta cele priče je – ako želite ubrzanje u domenu obrade podataka, imate dva moguća pristupa:

a) Napraviti još bolji i brži kompjuter koji će moći da se nosi sa još većom količinom podataka nego njegov prethodnik, a da pri tome ne gubite ni jedan jedini podatak

ili

 b) Da optimizujete procese do te mere gde će algoritmi nalaziti pravu i suštinsku informaciju, a sve ostalo proglasiti šumom i nepotrebnim.

Ovaj drugi pristup je definitvno brži, ali morate uvek imati na umu da se prilikom njegove primene može desiti neželjeni, vitalni gubitak informacije. Novi algoritam je tu i verovatno će naći svoju primenu, a koliko će nam pomoći u razvoju nauke i kompjutera, to će tek vreme pokazati.

 ***

U akustici, fizičke barijere, napravljene od čvrstih tela imaju tendenciju da odbijaju zvuk više frekvencije, a da propuštaju zvuk niže frekvencije. Kada se izvor zvuka ili muzike nalazi u susednoj sobi, slušalac će mnogo lakše čuti niže tonove od viših, pod uslovom da je između njega i izvora samo zid (bez ikakvih otvora).

 

Nova saznanja iz talasne optike obećavaju – apsolutna zvučna izolacija je moguća

Tokom našeg svakodnevnog života, mnoge stvati prihvatamo, takave kakvim ih vidimo, bez mnogo razmišljanja. Jednostavno, to tako radi.

Bez obira na činjenicu, da se jednosmerna ogledala najviše mogu videti u policijskim serijama, skoro isti sistem se koristi i kod naočara za sunce. Kada se malo bolje razmisli, ako prostorije oko policijskog ogledala osvetlimo na određeni način (najčešće, da se uključe dovoljno jaka svetla na obe strane), ogledalo postaje propusno u oba smera. Zaključak se sam nameće: koristeći se jednostavnim trikom, mi pravimo iluziju nepropusnog ogledala, koje ima svoje praktične primene.

Sada, pokušajmo da zamislimo, da zaista možemo da napravimo površinu koje je na jednu stranu propusna za talase (svetlost i zvuk se šire kroz prostor u obliku talasa), na drugu sasvim solidna i nepropusna barijera. Za sada ne postoje materijali sa takvom osobinom, ali prema najnovijim studijama, postoji mogućnost da se napravi pravo jednosmerno ogledalo.

Stefano Lepri (Stefano Lepri) sa italijanskog istraživačkog centra i Đulio Kazati (Giulio Casati) sa univerziteta u gradu Insubria u Italiji i nacionalnog univerziteta Singapura su razradili teoretski model za materijale koji transmituju talase na asimetričan način. Njihov rad je objavljen u časopisu Physical Review Letters u izdanju od 18. aprila, ove godine.

Njihov predlog se bazira na korišćenju nelinearnih materijala, koji se različito ponašaju zavisno od toga kakav talas prolazi kroz njih. Još preciznije, reakcija zavisi od atributa talasa koji prolazi kroz njih. “Kada uvedete nelinearne interakcije i sile, mnoge intuitivne spoznaje o ponašanju talasa više ne važe.”, tvrdi Lepri za Physical Review Focus, časopis koji se bavi popularizacijom naučnih radova iz fizike. “Koriteći se nelinearnim interakcijama možemo da izađemo iz osnovnog zakona reciprociteta”, koji zahteva da svi talasi imaju isti tretman, bez obzira na smer njihovog dolaska.

Znači, postavljajući nelinearne materijale zajedno sa linearnim materijalima, koji su poređani na asimetričan način, talas bi mogao da prođe po jednom smeru, ali bi se potpuno odbio kada bi dolazio iz suprotnog smera. Na žalost, kako ističu sami istraživači, ovkava jednosmerna konstrukcija nije univerzalna – svaka kombinacija materijala bi bila dobra za određeni spektar talasnih amplituda. Praktično gledano, moguće je blokirati sve zvukove, ali nema te kombinacije koja bi vas odvojila od bilo kog zvuka u isto vreme.

Za sada, iznesena tvrđenja se baziraju na numerčkim simulacijama, bez pravih eksperimentalnih provera. Međutim, ako se pokaže da su te simulacije dobra aproksimacija realnih materijala, onda bi to “otvorilo nove mogućnosti u kontroli i optimizaciji prostiranja talasa i u dizajniranju uređaja za transformaciju zvučnih i svetlosnih talasa.”

Sami autori ističu ograničenost na određene opsege, ali ako je svaki od tih opsega dovoljno dobro prigušen, ili još bolje, ugušen, onda je sa razvojem tehnologije i dodatnim istraživanjem, realno očekivati, da će se pojaviti materijal, koji će se ponašati kao apsolutni izolator talasa po jednom smeru, a propusan po drugom. Još jednom, sve navedeno važi, samo ako je razvijeni matematički model dovoljno blizak osobinama realnih materijala, koji se mogu naći u prirodi ili na neki način jeftino proizvesti. U suprotnom… ostaće zapamćen kao dobar teoretski pokušaj.