matrisefullføring

Matrisefullføring er problemet med å rekonstruere manglende innslag i en delvis observert matrise. Gitt en matrise M og et sett Omega av observerte indekspar, søker man en fullstendig matrise X som stemmer overens med de kjente verdiene i Omega. Ofte antas M å være lav-rang eller tilnærmingslav-rang, noe som gjør rekonstruering mulig fra få observasjoner.

Teori og antakelser: Under antakelser om lav rang, inkohærens og tilstrekkelig observasjonsandel kan M gjenopprettes med høy sannsynlighet. En sentral tilnærming er convex avslapning via den nukleære normen. Målet er normalt å minimere ||X||_* under betingelsen at P_Omega(X) = P_Omega(M), der P_Omega er projeksjonen på de observerte posisjonene. For støyfulle data brukes ofte en variant som tillater avvik mellom observerte verdier og løsningen.

Metoder: Den dominerende tilnærmingen er matrisefaktorisering og/eller nuclear-norm-minimering. Ikke-konvekse metoder inkluderer X = UV^T med rangrensing gjennom alternating least squares (ALS) eller gradientbaserte metoder. Vertreter av metoder inkluderer singular value thresholding (SVT) og andre algoritmer som skalerer til store matriser.

Anvendelser: Matrisefullføring brukes i anbefalingssystemer, bilde- og video-inpainting, sensornettverk og bioinformatiske data, der verdier mangler eller er støyete.

Utfordringer og evaluering: Ikke tilfeldig utvalg, støy og modell-missforhold kan påvirke resultatet. Evaluering skjer ofte ved RMSE på et hold-out-set eller gjennom kryssvalidering, og avhenger av riktig modellantakelse og tilstrekkelig observasjonsdekning.