Kaczmarz-metoden är en algoritm för att hitta lösningen till ett överbestämt konsekvent system av linjära ekvationer Ax = b genom att iterativt projicera på lösningsutrymmena. Den randomiserade versionen framtagen av Strohmer och Vershynin ger bevisligen exponentiell konvergens i förväntan, vilket för mycket överbestämda system även överträffar konjugatgradientmetoden. I denna artikel presenterar vi en modifierad version av den randomiserade Kaczmarz metoden som vid varje iteration väljer den optimala projektionen från en slumpmässigt vald uppsättning, vilket i de flesta fall avsevärt förbättrar konvergensen. Vi använder en Johnson-Lindenstrauss dimension reduktion teknik för att hålla körtiden på samma ordning som den ursprungliga randomiserade versionen, lägga till endast extra förbehandlingstid. Vi presenterar en rad empiriska studier som visar den anmärkningsvärda accelerationen i konvergensen till lösningen med hjälp av denna modifierade metod.
Radien är proportionell mot avståndet b från bildutrymmet för A. REF presenterade en modifierad version av den randomiserade Kaczmarz-metoden som vid varje iteration väljer den optimala projektionen från en slumpmässigt vald uppsättning.
Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma
{'venue': 'Numerical Algorithms', 'journal': 'Numerical Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}