Czy asymetryczna matryca Bernoulliego spełnia RIP?

9

Zdefiniuj n×N matryca czujnikowa A przez Aij=0 z prawdopodobieństwem p, i Aij=1/n z prawdopodobieństwem 1p. RobiAspełniać ograniczoną właściwość izometrii ?

Dla porównania na przypadek symetryczny odpowiada następujący artykuł:

RG Baraniuk, MA Davenport, RA DeVore i MB Wakin, „Prosty dowód ograniczonej właściwości izometrycznej dla macierzy losowych”, Constructive Approximation, 28 (3) str. 253-263, grudzień 2008. ( pdf )

olivia
źródło
Może to być wskaźnik: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5512379 (niestety jest on zaporowy i nie znalazłem jego kopii OA). Nie znam szczegółowo tego artykułu, ale widzę go szybko, że nie uważają tak ogólnej sprawy, jak prosisz; rozważają p = 1/2. Nie wiem też, jak dokładni są do RIP takich matryc.
Thomas Arildsen
Może to być także wskazówka: rauhut.ins.uni-bonn.de/RauhutSlidesLinz.pdf (strona 98). Niestety wygląda na to, że to, co nazywa losowymi zmiennymi Bernoulliego, to losowe +/- 1 - nie 0/1 (nazwałbym to Rademacher).
Thomas Arildsen
2
Pozwólcie, że powtórzę sedno komentarza, który wypowiedziałem na temat identycznego postu (teraz usuniętego) na stats.SE : Pomogłoby to uściślić to pytanie i wskazać, czym dokładnie jesteście zainteresowani i co staracie się dostosować. Komentarz @ Thomas jest istotny; my też nie wiemy, co stopień (tj kolejności) z sparsity jesteś zainteresowany. Nawet jeśli weźmiemy pod uwagę funkcje Rademacher, odpowiedź jest wyraźnie nie w każdym mundurze (wp) sens, na let p być 1(lub wystarczająco blisko), aby istniała (wysokie prawdopodobieństwo), że podmacierz jest wszystkim. (cd.)
kardynał
2
Wybierając sekwencję pn(0,1) jako funkcja n, dla niektórych będzie to prawdą pdla dowolnej matrycy rozmiarów. Z drugiej strony, dla ustalonych p, jeśli zmodyfikujemy konstrukcję tak, aby Aij=(1p)/n z prawdopodobieństwem p i p/n z prawdopodobieństwem (1p), odpowiedź brzmi: tak , ponieważ wynika to z dużo bardziej ogólnej teorii związanej z losowymi macierzami subgaussowskimi o zerowej średniej.
kardynał
dzięki @cardinal, macierz Anie jest wartością zerową, ale teoria subgaussowskich macierzy losowych odpowiada na to pytanie. Zastanawiałem się jakA może spełnić RIP, ponieważ nie zachowuje normy, ale oczywiste jest, że istnieje odpowiednie skalowanie Ato robi
olivia

Odpowiedzi:

1

Jak powiedzieli inni w komentarzach, odpowiedź brzmi „nie”. Niezerowa średnia macierzy dyktuje, że niezerowy średni wektor (powiedzmy wszystkie), będzie miał znacznie wyższe wzmocnienie niż losowy wektor z zerową średnią (powiedzmy równomiernie losowo + 1, -1).

Rozważmy kwadratową normę A razy, gdy stały wektor y ma wynosić n * (p * N) ^ 2. (iteracja oczekiwań)

Oczekuje się, że kwadratowa norma A razy wektor x narysowany równomiernie z (-1, + 1) będzie wynosić n * (p * N). (obliczalne przez sumę wariancji rozkładu dwumianowego)

Normy xiy są takie same, ale oczekiwanie norm transformowanych różni się współczynnikiem p * N - rozbieżnym w miarę wzrostu wymiarów.

Oto kod Matlab, aby pomóc zademonstrować.

n=2000;
N=1000;
p=.9;
A=double(rand(n,N)<p); 
x=sign(randn(N,1)); 
y=ones(N,1);
Ex_normSqAx = n*(N*p);  % E[ squared norm of A times random signs ]
Ex_normSqAy = n*(N*p)^2; % E[ squared norm of A times constant vector ]
normSqAx = norm(A*x)^2;
normSqAy = norm(A*y)^2;
Mark Borgerding
źródło