Une matrice asymétrique de Bernoulli satisfait-elle le RIP?

Définissez une matrice de détection par avec probabilité , et avec probabilité . Est-ce que satisfaire la Propriété de isométrie restreinte ? $n\times N$ $A$ $A_{ij} = 0$ $p$ $A_{ij} = 1/\sqrt{n}$ $1-p$ $A$

Pour référence, le cas symétrique est répondu dans l'article suivant:

RG Baraniuk, MA Davenport, RA DeVore et MB Wakin, «A simple proof of the restricted isometry property for random matrices», Constructive Approximation, 28 (3) pp. 253-263, décembre 2008. ( pdf )

compressive-sensing olivia
la source

Cela peut être un pointeur: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5512379 (malheureusement, il est payant et je n'en ai pas trouvé de copie OA). Je ne connais pas le document en détail, mais ce que je peux voir d'un coup d'œil, c'est qu'ils ne considèrent pas un cas aussi général que vous le demandez; ils considèrent p = 1/2. Aussi, je ne sais pas à quel point ils sont approfondis sur le RIP de telles matrices.

Thomas Arildsen

Cela pourrait également être un indice: rauhut.ins.uni-bonn.de/RauhutSlidesLinz.pdf (page 98). Malheureusement, il semble que ce qu'il appelle les variables aléatoires de Bernoulli sont aléatoires +/- 1 - pas 0/1 (j'appellerais ces Rademacher).

Thomas Arildsen

Permettez-moi de répéter l'essentiel d'un commentaire que j'ai fait sur le poste identique (maintenant supprimé) sur stats.SE : Cela aiderait à rendre cette question plus précise et à indiquer ce qui vous intéresse exactement et ce que vous avez du mal à adapter. Le commentaire de @Thomas est pertinent; nous ne savons pas non plus à quel degré (c'est-à-dire l'ordre) de rareté qui vous intéresse. Même si nous considérons les fonctions de Rademacher, la réponse est clairement non dans un sens uniforme (en ), car soit (ou suffisamment proche) ) de sorte qu'il existe (une forte probabilité) qu'une sous-matrice soit tout entière. (suite)

p

$p$

p

$p$

1

$1$

cardinal

En choisissant une séquence en fonction de , cela sera rendu vrai pour certains pour n'importe quelle matrice de taille. En revanche, pour fixe , si, nous modifions la construction de telle sorte que avec probabilité et avec probabilité , alors la réponse est clairement oui , car cela découle de la théorie beaucoup plus générale relative aux matrices aléatoires sous-gaussiennes à moyenne nulle.

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)$

cardinal

merci @cardinal, la matrice n'est pas de moyenne nulle, mais la théorie des matrices aléatoires sous-goussiennes répond à cette question. Je me demandais comment pourrait satisfaire le RIP étant donné qu'il ne préserve pas la norme, mais il est évident qu'il existe une échelle appropriée de qui le fait

A

$A$

A

$A$

A

$A$

Olivia

Comme d'autres l'ont indiqué dans les commentaires, la réponse est "non". La moyenne non nulle de la matrice dicte qu'un vecteur moyen non nul (disons, tous les uns), aura un gain sensiblement plus élevé qu'un vecteur aléatoire avec une moyenne nulle (disons uniformément aléatoire + 1, -1).

Considérons la norme quadratique de A fois un vecteur constant y devrait être n * (p * N) ^ 2. (itération des attentes)

La norme quadratique de A fois un vecteur x tiré uniformément de (-1, + 1) devrait être n * (p * N). (calculable par la somme des variances de la distribution binomiale)

Les normes de x et y sont les mêmes, mais l'attente des normes transformées diffère d'un facteur p * N - divergeant à mesure que les dimensions grandissent.

Voici le code matlab pour aider à démontrer.

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
la source

Une matrice asymétrique de Bernoulli satisfait-elle le RIP?

Réponses: