Erfüllt eine asymmetrische Bernoulli-Matrix den RIP?

Definieren Sie eine Erfassungsmatrix durch mit der Wahrscheinlichkeit und mit der Wahrscheinlichkeit . Erfüllt die eingeschränkte Isometrieeigenschaft ? $n\times N$ $A$ $A_{ij} = 0$ $p$ $A_{ij} = 1/\sqrt{n}$ $1-p$ $A$

Als Referenz wird der symmetrische Fall in der folgenden Abhandlung beantwortet:

RG Baraniuk, MA Davenport, RA DeVore und MB Wakin, "Ein einfacher Beweis für die eingeschränkte Isometrieeigenschaft für Zufallsmatrizen", Constructive Approximation, 28 (3), S. 253-263, Dezember 2008. ( pdf )

compressive-sensing Olivia
quelle

Dies kann ein Zeiger sein: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5512379 (leider ist es paywalled und ich habe keine OA-Kopie davon gefunden). Ich kenne das Papier nicht im Detail, aber was ich auf einen Blick sehen kann, ist, dass sie einen Fall nicht so allgemein betrachten, wie Sie es wünschen. sie betrachten p = 1/2. Ich weiß auch nicht, wie gründlich sie über den RIP solcher Matrizen sind.

Thomas Arildsen

Dies könnte auch ein Hinweis sein: rauhut.ins.uni-bonn.de/RauhutSlidesLinz.pdf (Seite 98). Leider sieht es so aus, als ob das, was er Bernoulli-Zufallsvariablen nennt, zufällig +/- 1 ist - nicht 0/1 (ich würde diese Rademacher nennen).

Thomas Arildsen

Gestatten Sie mir, den Kern eines Kommentars zu wiederholen, den ich zu dem identischen (jetzt gelöschten) Beitrag zu Statistiken abgegeben habe. SE : Es wäre hilfreich, diese Frage präziser zu gestalten und anzugeben, woran Sie genau interessiert sind und woran Sie sich nur schwer anpassen können. @ Thomas 'Kommentar ist relevant; Wir wissen auch nicht, an welchem Grad (dh an welcher Reihenfolge) der Sparsamkeit Sie interessiert sind. Selbst wenn wir Rademacher-Funktionen betrachten, lautet die Antwort eindeutig nein in einem einheitlichen (in ) Sinne, denn sei (oder ausreichend nahe) ), so dass (mit hoher Wahrscheinlichkeit) eine Submatrix alle eins ist. (Forts.)

p

$p$

p

$p$

1

$1$

Kardinal

Durch Auswahl einer Folge als Funktion von wird dies für einige für jede Größenmatrix wahr gemacht . Andererseits modifizieren wir für festes , wenn, die Konstruktion so, dass mit der Wahrscheinlichkeit und mit der Wahrscheinlichkeit , dann lautet die Antwort eindeutig Ja , denn dies folgt aus der viel allgemeineren Theorie, die sich auf subgaußsche Zufallsmatrizen mit dem Mittelwert Null bezieht.

p_{n} \in (0, 1)

$p_n \in (0,1)$

n

$n$

p

$p$

p

$p$

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

$A_{ij} = (1-p)/\sqrt{n}$

p

$p$

- p / \sqrt{n}

$-p/\sqrt{n}$

(1 - p)

$(1-p)$

Kardinal

danke @cardinal, die Matrix ist kein Nullmittelwert, aber die Theorie der subgaußschen Zufallsmatrizen beantwortet diese Frage. Ich habe mich gefragt, wie den RIP erfüllen kann, da er die Norm nicht

A

$A$

A

$A$

A

$A$

beibehält

Wie andere in den Kommentaren angegeben haben, lautet die Antwort "Nein". Der Nicht-Null-Mittelwert der Matrix schreibt vor, dass ein Mittelwertvektor ungleich Null (z. B. alle Einsen) eine wesentlich höhere Verstärkung aufweist als ein Zufallsvektor mit einem Mittelwert von Null (z. B. gleichmäßig zufällig + 1, -1).

Betrachten Sie die quadratische Norm von A mal, wenn erwartet wird, dass ein konstanter Vektor y n * (p * N) ^ 2 ist. (Wiederholung der Erwartungen)

Es wird erwartet, dass die quadratische Norm von A mal einem Vektor x, der gleichmäßig aus (-1, + 1) gezogen wird, n * (p * N) ist. (berechenbar durch die Summe der Varianzen der Binomialverteilung)

Die Normen von x und y sind gleich, aber die Erwartung transformierter Normen unterscheidet sich um einen Faktor von p * N - divergierend, wenn die Dimensionen größer werden.

Hier ist Matlab-Code zur Veranschaulichung.

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
quelle

Erfüllt eine asymmetrische Bernoulli-Matrix den RIP?

Antworten: