Browsing by Author "Mikkola, Visa"

Satunnaisprojektio on menetelmä korkeaulotteisen datamatriisin X ∈ \R^{n × m} ulottuvuuksien vähentämiseksi. Menetelmässä alkuperäinen n-ulotteinen data kuvataan satunnaisista suunnista virittyvälle matalaulotteiselle, k << n, aliavaruudelle siten, että datavektorien väliset etäisyydet säilyvät approksimatiivisesti. Kuvauksen tekevän matriisin R∈ R^{k × n} alkiot voidaan valita esimerkiksi normaalijakaumasta ja siksi menetelmän laskennallinen toteutus saadaan hyvin kevyeksi. Tästä syystä monissa tutkimuksissa menetelmä on asetettu vastakkain perinteisen pääkomponenttianalyysin (engl. Principal component analysis, PCA) kanssa, joka on usein laskennallisesti huomattavasti vaativampi ulottuvuuksienvähentämismenetelmä. Samaa vastakkainasettelua käytetään tämän tutkielman satunnaisprojektiosta kertovassa johdantoluvussa, kun menetelmästä esitettyä teoriaa havainnollistetaan numeerisin testein. Satunnaisprojektion toimivuutta on jo tutkittu muun muassa kasvojentunnistuksen sekä kuva- ja tekstidatan ulottuvuuksien vähentämisen yhteydessä. Tutkielman pääaiheeksi on nostettu menetelmän sovellus käänteisongelmaan, jossa pyrkimyksenä on palauttaa tuntematon vektori x∈\R^n approksimatiivisesti siitä tehdyistä satunnaisista mittauksista, kun x oletetaan heikkoon kuulaan wlp(L) sisältyväks vektoriksi. Oletus tarkoittaa, että järjestettäessä vektorin x koordinaatit itseisarvoiltaan laskevaan järjestykseen, x_{arr}, suppenevat ne kohti nollaa kuulan sädettä L > 0 ja suppenemisparametria 0 < p < 1 noudattaen seuraavasti: |x_{arr}| ≤ L · l^{-\frac{1}{p}}, kun, 1 ≤ l ≤ n. Tutkielma seuraa Emmanuel Candèsin ja Terence Taon artikkelissaan Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? (2006) antamaa ratkaisua ongelmalle: heikkoon kuulaan wlp(L) sisältyvän vektorin x ∈ R^n ja mittausmatriisilla R ∈ R^{k× n} tehdyistä mittauksista Rx \ell_1-optimoinnilla palautetun ratkaisun ˆx välinen virhe noudattaa ylärajaa \lTwo{x-ˆ x } ≤ C_{p, α} · L · (\frac{k}{β})^{\frac{1}{2}-\frac{1}{p}}. Ylärajassa C_{p, α} on vakio ja β käytettyyn mittausmatriisiin liittyvä parametri. Tulosta ei siis suoraan johdeta yksittäiselle mittausmatriisityypille, vaan annettaan ominaisuudet, jotka omaavaa matriisia voidaan mittausmatriisina käyttää. Tukielmassa erikseen todistetaan normaalijakaumasta kehitetyn satunnaismatriisin sopivan mittausmatriisiksi parametrin β arvolla log n. Tällä matriisivalinnalla teoriaa myös esitellään numeerisesti. Esitelty virheen yläraja ja muut ongelmaa koskevat tulokset johdetaan tutkielmassa suoraan lineaarialgebran ja todennäköisyyslaskennan perusteista tuoden aiheen siten helpommin lähestyttäväksi; alkuperäisen artikkelin todistuksissa useat päättelyt on jätetty vaille tarkempia yksityiskohtia.