Zastosowanie jednostajnych praw wielkich liczb do analizy złożoności algorytmu Er-SpUD

Niech A będzie macierzą n na n, X macierzą prostokątną n na p, zaś Y = AX. Oczywiście w ogólności obserwacja macierzy Y nie pozwala na odtworzenie macierzy A oraz X. Niemniej w 2012 r. D. Spielman, H. Wang i J. Wrigth zaproponowali algorytm Er-SpUD (Exact Recovery of Sparsely Used Dictionaries), który z dużym prawdopodobieństwem znajduje nieznane macierze A, X (z dokładnością do permutacji i przeskalowania odp. kolumn i wierszy) na podstawie obserwacji Y, przy założeniu, że A jest deterministyczną macierzą odwracalną, zaś X jest odpowiednio rzadką macierzą losową, której niezerowe współczynniki są niezależnymi, podgaussowskimi zmiennymi losowymi.

Spielman, Wang i Wright wykazali, że algorytm ten działa o ile p jest rzędu przynajmniej n^2 \log n, zaś sam problem jest dobrze postawiony dla p rzędu przynajmniej  n\log n.

W referacie wykażę, że prosta modyfikacja algorytmu Er-SpUD pozwala na  znalezienie A i X (w sensie jak wyżej) już dla p rzędu n \log n, co jest optymalne z dokładnością do stałej uniwersalnej. Analiza oparta będzie o prostą nierówność dla procesów empirycznych, bazującą na zasadzie kontrakcji Talagranda.

Zbliżone wyniki uzyskane zostały niedawno także przez J. Błasioka i J. Nelsona przy pomocy miar majoryzujących.