Apakah matriks Bernoulli asimetris memenuhi RIP?

Tentukan sensing matrix oleh dengan probabilitas , dan dengan probabilitas . Apakah memenuhi properti isometri terbatas ? $n\times N$ $A$ $A_{ij} = 0$ $p$ $A_{ij} = 1/\sqrt{n}$ $1-p$ $A$

Untuk referensi, kasus simetris dijawab dalam makalah berikut:

RG Baraniuk, MA Davenport, RA DeVore, dan MB Wakin, "Bukti sederhana dari properti isometry terbatas untuk matriks acak," Perkiraan Konstruktif, 28 (3) hlm. 253-263, Desember 2008. ( pdf )

compressive-sensing olivia
sumber

Ini mungkin sebuah pointer: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5512379 (sayangnya, paywalled dan saya belum menemukan salinan OA). Saya tidak tahu kertas secara detail, tetapi apa yang bisa saya lihat dari pandangan sekilas adalah bahwa mereka tidak menganggap kasus umum seperti yang Anda minta; mereka menganggap p = 1/2. Juga, saya tidak tahu seberapa teliti mereka tentang RIP dari matriks seperti itu.

Thomas Arildsen

Ini juga bisa menjadi petunjuk: rauhut.ins.uni-bonn.de/RauhutSlidesLinz.pdf (halaman 98). Sayangnya, sepertinya apa yang dia sebut variabel acak Bernoulli adalah acak +/- 1 - bukan 0/1 (saya sebut Rademacher ini).

Thomas Arildsen

Izinkan saya mengulangi inti dari komentar yang saya buat pada pos yang sama (sekarang dihapus) di stats.SE : Ini akan membantu untuk membuat pertanyaan ini lebih tepat dan menunjukkan apa yang benar-benar Anda minati dan apa yang Anda perjuangkan untuk beradaptasi. Komentar @Thomas 'relevan; kami juga tidak tahu apa gelar (yaitu, order) dari sparsity Anda tertarik. Bahkan jika kita menganggap fungsi Rademacher, jawabannya adalah jelas tidak ada dalam seragam apapun (dalam ) pengertian, untuk membiarkan menjadi (atau, cukup dekat ) sehingga ada (kemungkinan tinggi) sebuah submatrix menjadi yang semuanya. (lanjutan)

p

$p$

p

$p$

1

$1$

kardinal

Dengan memilih urutan sebagai fungsi dari , ini akan dibuat benar untuk beberapa untuk matriks ukuran apa pun. Di sisi lain, untuk tetap , jika, kita memodifikasi konstruksi sehingga dengan probabilitas dan dengan probabilitas , maka jawabannya jelas ya , karena ini mengikuti dari teori yang jauh lebih umum terkait dengan matriks acak subgausia rata-rata.

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

terima kasih @ cardinal, matriks tidak berarti nol, tetapi teori matriks acak subgausia menjawab pertanyaan ini. Saya bertanya-tanya bagaimana dapat memenuhi RIP mengingat itu tidak mempertahankan norma, tetapi jelas ada skala yang sesuai dari yang tidak

A

$A$

A

$A$

A

$A$

olivia

Seperti yang dinyatakan orang lain di komentar, jawabannya adalah "Tidak". Rata-rata non-nol dari matriks menentukan bahwa vektor bukan nol berarti (katakanlah, semua vektor), akan memiliki keuntungan yang jauh lebih tinggi daripada vektor acak dengan rata-rata nol (katakan acak seragam + 1, -1).

Pertimbangkan norma kuadrat dari A kali vektor konstan y diharapkan menjadi n * (p * N) ^ 2. (iterasi harapan)

Norma kuadrat dari A kali vektor x diambil secara seragam dari (-1, + 1) diharapkan menjadi n * (p * N). (dihitung dengan jumlah varian distribusi Binomial)

Norma x dan y adalah sama, tetapi harapan dari norma yang diubah berbeda dengan faktor p * N - divergen ketika dimensi tumbuh besar.

Berikut kode matlab untuk membantu menunjukkan.

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
sumber

Apakah matriks Bernoulli asimetris memenuhi RIP?

Jawaban: