Czy asymetryczna matryca Bernoulliego spełnia RIP?

Zdefiniuj $n\times N$ matryca czujnikowa $A$ przez $A_{ij} = 0$ z prawdopodobieństwem $p$ , i $A_{ij} = 1/\sqrt{n}$ z prawdopodobieństwem $1-p$ . Robi $A$ speł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 )

compressive-sensing 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

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 (w

p

$p$ ) sens, na let

p

$p$ być

1

$1$ (lub wystarczająco blisko), aby istniała (wysokie prawdopodobieństwo), że podmacierz jest wszystkim. (cd.)

kardynał

Wybierając sekwencję

p_{n} \in (0, 1)

$p_n \in (0,1)$ jako funkcja

n

$n$ , dla niektórych będzie to prawdą

p

$p$ dla dowolnej matrycy rozmiarów. Z drugiej strony, dla ustalonych

p

$p$ , jeśli zmodyfikujemy konstrukcję tak, aby

A_{i j} = (1 - p) / \sqrt{n}

$A_{ij} = (1-p)/\sqrt{n}$ z prawdopodobieństwem

p

$p$ i

- p / \sqrt{n}

$-p/\sqrt{n}$ z prawdopodobieństwem

(1 - p)

$(1-p)$ , 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

A

$A$ nie jest wartością zerową, ale teoria subgaussowskich macierzy losowych odpowiada na to pytanie. Zastanawiałem się jak

A

$A$ może spełnić RIP, ponieważ nie zachowuje normy, ale oczywiste jest, że istnieje odpowiednie skalowanie

A

$A$ to robi

olivia

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

Czy asymetryczna matryca Bernoulliego spełnia RIP?

Odpowiedzi: