projektionsmetode

Projeksjonsmetoden er en familie av iterative algoritmer som brukes til å løse feasibilitetsproblemer og konveks optimering ved å gjenta projisering av et kandidatpunkt på ulike restriksjonssett. Projeksjonen P_C(x) av et punkt x på et sett C defineres som det punktet i C som ligger nærmest x. Når C er lukket og konveks i et Hilbertrom, eksisterer P_C(x) og er unik.

I to-sett-tilfellet genererer metoden med vekselvise projeksjoner en følge gjennom x_{k+1} = P_B(P_A(x_k)) for sett A og B. Hvis A ∩ B ikke er tom, konvergerer følgen mot et punkt i A ∩ B; i endelige dimensjoner er konvergensen vanligvis sterk, og hastigheten avhenger av vinkelen mellom settene. For flere enn to sett brukes sykliske projeksjoner (projisere på A1, deretter A2, osv.) eller randomiserte projeksjoner, og konvergens til et punkt i skjæringsmengden kan etableres under konveksitet og regelmessighetsforutsetninger.

Numeriske varianter inkluderer Douglas–Rachford-algoritmen, som bruker speiling i stedet for projeksjoner og ofte gir god ytelse på krevende feasibilitetsproblemer. Kaczmarz-metoden er en klassisk projeksjonsmetode for å løse lineære ligningssystemer og itererer projeksjoner onto hyperplan definert av ligningene. Projeksjonsbaserte metoder omtales også som POCS (projection onto convex sets) i bildebehandling og signalbehandling.

Anvendelser omfatter bildebehandling, tomografi og signalbehandling, samt generelt løsning av lineære feasibilitetsproblemer. Ved ikke-konvekse problemstillinger kan konvergensen feile eller lede til sykluser, derfor er konveksitet av restriksjonene en vanlig forutsetning. Metoden har historiske røtter i von Neumanns arbeid med underrom og ble senere utviklet av blant andre Kaczmarz, Halperin og Bregman.