Analog dari penginderaan terkompresi

$x \in \mathbb{R}^n$$\|x\|_0 < k$A R $Ax$$A$$R$$n$$R \ll n$$A$$k$-Sparse dengan sekecil . Saya mungkin tidak memiliki parameter yang paling dikenal tetapi ini adalah ide umum.R O ( k n o ( 1 )$x$$R$$O(k n^{o(1)})$

Pertanyaan saya adalah: apakah ada fenomena serupa di pengaturan lain? Yang saya maksud adalah bahwa sinyal input bisa berasal dari beberapa "keluarga dengan kompleksitas rendah" menurut ukuran kompleksitas yang tidak selalu sparsity. Kami kemudian menginginkan algoritma kompresi dan dekompresi, tidak harus peta linier, yang efisien dan benar. Apakah hasil seperti itu diketahui dalam konteks yang berbeda? Bagaimana dugaan Anda untuk teori penginderaan terkompresi yang lebih "umum"?

(Tentu saja, dalam aplikasi penginderaan terkompresi, linearitas dan sparsitas adalah masalah penting. Pertanyaan yang saya ajukan di sini lebih "filosofis".)

Pertanyaan Anda membahas masalah pemulihan "tepat" (kami ingin memulihkan k-jarang $x$ persis diberi $Ax$ ). Dalam berikut ini saya akan fokus pada versi "robust", di mana $x$ adalah vektor sewenang-wenang dan tujuan dari algoritma pemulihan adalah untuk menemukan pendekatan $k$ sparse $x'$ ke $x$ (perbedaan ini sebenarnya penting untuk beberapa diskusi di bawah ini ). Secara resmi Anda ingin mengikuti masalah (sebut saja $P_1$ ):

Desain sedemikian rupa sehingga untuk setiap x satu dapat pulih x ′ di mana ‖ x - x ′ ‖ L$A$$x$$x'$$\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$ , di mana berkisar di atas semua vektor sparse.$x"$$k$

Di sini, dan menunjukkan norma kiri dan kanan, dan C adalah "faktor aproksimasi". Ada berbagai pilihan yang mungkin untuk ‖ ⋅ ‖ L dan ‖ ⋅ ‖ R . Untuk konkret, orang dapat berpikir bahwa keduanya sama dengan ℓ 2 atau ℓ 1 ; itu bisa menjadi lebih berantakan. ‖ ⋅ ‖ $\| \cdot \|_L$$\| \cdot \|_R$$C$$\| \cdot \|_L$$\| \cdot \|_R$$\ell_2$$\ell_1$

Sekarang untuk beberapa analog dan generalisasi.

Dasar sewenang-wenang. Pertama, amati bahwa skema apa pun yang memenuhi definisi di atas dapat digunakan untuk menyelesaikan masalah yang lebih umum, di mana sinyal yang dipulihkan jarang dalam basis yang sewenang-wenang (katakanlah, wavelet Fourier), bukan hanya yang standar. Biarkan B menjadi matriks dasar. Secara formal, vektor u adalah k -sparse di dasar B jika u = B v di mana v adalah k -sparse. Sekarang kita dapat mempertimbangkan masalah umum (sebut saja P B ):$x'$$B$$u$$k$$B$$u=Bv$$v$$k$$P_B$

Desain sedemikian sehingga diberikan A B x , orang dapat memulihkan x ′ di mana ‖ x - x ′ ‖ L$A_B$$A_B x$$x'$$\|x-x'\|_L \le$

, di mana x " rentang atas semua vektor yang k -sparse di B .$\min_{x"} C \|x-x"\|_R$$x"$$k$$B$

Satu dapat mengurangi masalah ini ke masalah sebelumnya dengan mengubah dasar, yaitu, menggunakan matriks pengukuran A B = A B - 1 . Jika kita memiliki solusi untuk P 1 dalam norma ℓ 2 (yaitu, norma kiri dan kanan sama dengan ℓ 2 ), kita juga mendapatkan solusi untuk P B dalam norma ℓ 2 . Jika P 1 menggunakan norma-norma lain, kami menyelesaikan P B dalam norma-norma yang dimodifikasi dengan mengubah basis.$P_1$$A_B = A B^{-1}$$P_1$$\ell_2$$\ell_2$$P_B$$\ell_2$$P_1$$P_B$

Satu peringatan di atas adalah bahwa dalam pendekatan atas, kita perlu mengetahui matriks dalam rangka untuk menentukan A B . Mungkin mengejutkan, jika kita membiarkan pengacakan ( A B tidak tetap melainkan dipilih secara acak), adalah mungkin untuk memilih A B dari distribusi tetap yang independen dari B . Inilah yang disebut sebagai properti universalitas .$B$$A_B$$A_B$$A_B$$B$

Kamus Generalisasi selanjutnya dapat diperoleh dengan menjatuhkan persyaratan bahwa adalah basis. Sebagai gantinya, kami dapat mengizinkan B memiliki lebih banyak baris daripada kolom. Matriks semacam itu disebut kamus (overcomplete). Salah satu contoh populer adalah matriks identitas di atas matriks Fourier. Contoh lain adalah matriks di mana baris adalah vektor karakteristik dari semua interval dalam {1 ... n}; dalam hal ini, himpunan { B u : u adalah k-sparse } berisi semua " k- histogram", yaitu, fungsi konstan sebagian lebih dari {1 ... n} dengan paling banyak k buah.$B$$B$$Bu: \mbox{u is k-sparse}$$k$$k$

Sejauh yang saya tahu tidak ada teori umum untuk kamus sewenang-wenang semacam itu, meskipun ada cukup banyak pekerjaan pada topik ini. Lihat misalnya, Candes-Eldar-Needell'10 atau Donoho-Elad-Temlyakov, Transaksi IEEE tentang Teori Informasi, 2004 .

Sketsa histogram diselidiki secara luas dalam streaming dan literatur basis data, misalnya Gilbert-Guha-Indyk-Kotidis-Muthukrishnan-Strauss, STOC 2002 atau Thaper-Guha-Indyk-Koudas, SIGMOD 2002 .

Model. (juga disebutkan oleh Arnab). Generalisasi yang berbeda adalah untuk memperkenalkan pembatasan pada pola sparsity. Biarkan menjadi subset dari k -subset dari {1 ... n}. Kami mengatakan bahwa u adalah M -sparse jika dukungan u termasuk dalam unsur M . Kita sekarang dapat menimbulkan masalah (menyebutnya P M ):$M$$k$$u$$M$$u$$M$$P_M$

Desain sehingga untuk setiap x satu dapat memulihkan x ' di mana ‖ x - x ' ‖ L$A$$x$$x'$$\|x-x'\|_L \le$

, di mana x " berkisar pada semuavektor M- sparse.$\min_{x"} C \|x-x"\|_R$$x"$$M$

Misalnya, unsur-unsur bisa dari bentuk I 1 ∪ ... ∪ aku k , di mana setiap saya saya sesuai dengan salah satu "sub-blok" dari {1 ... n} dari beberapa panjang b , yaitu, I i adalah dari bentuk {jb + 1 ... (j + 1) b} untuk beberapa j . Ini adalah apa yang disebut model "block sparsity". $M$$I_1 \cup \ldots \cup I_k$$I_i$$b$$I_i$$j$

Manfaat dari model adalah bahwa seseorang dapat menghemat jumlah pengukuran, dibandingkan dengan pendekatan sparsity generik . Ini karena ruang sinyal M- sparse lebih kecil daripada ruang semua sinyal k- sparse, sehingga matriks A perlu menyimpan lebih sedikit informasi. Untuk lebih lanjut, lihat Baraniuk-Cevher-Duarte-Hegde, Transaksi IEEE pada Teori Informasi, 2010 atau Eldar-Mishali, Transaksi IEEE pada Teori Informasi, 2009 .$k$$M$$k$$A$

Semoga ini membantu.

Ada generalisasi penginderaan terkompresi ke pengaturan non-komutatif yang disebut penyelesaian matriks . Dalam pengaturan yang tepat, Anda diberi matriks M yang tidak diketahui yang, alih-alih sparsity, diketahui memiliki peringkat rendah r ≪ m , n . Tujuan Anda adalah merekonstruksi nilai singular r dan vektor singular dari matriks ini dengan hanya mengambil sampel koefisien ˜ O ( r m + r n ) dari matriks, daripada O ( m n ) seperti yang diperlukan dalam kasus terburuk. $m \times n$$M$$r \ll m,n$$r$$\tilde{O}(rm+rn)$$O(mn)$

Jika vektor singular cukup "tidak koheren" (kira-kira, tidak terlalu selaras) dengan dasar di mana Anda sampel elemen matriks, maka Anda dapat berhasil dengan probabilitas tinggi dengan menyelesaikan program cembung, mirip dengan penginderaan terkompresi standar. Dalam hal ini, Anda harus meminimalkan Schatten 1-norm, yaitu jumlah nilai singular.

Masalah ini juga memiliki banyak aplikasi, misalnya, untuk memberikan rekomendasi buku kepada pelanggan toko buku online dari hanya mengetahui beberapa peringkat yang dihasilkan oleh pelanggan lain. Dalam konteks ini, baris dan kolom -masing diberi label oleh buku dan pelanggan. Beberapa elemen matriks yang terlihat adalah peringkat pelanggan dari buku-buku yang sebelumnya mereka beli. Matriks M diharapkan peringkat rendah karena kami percaya bahwa biasanya hanya beberapa faktor utama yang mempengaruhi preferensi kami. Dengan menyelesaikan M , vendor dapat membuat prediksi yang akurat tentang buku mana yang mungkin Anda inginkan.$M$$M$$M$

Awal yang baik adalah makalah ini oleh Candés dan Recht, Exact Matrix Completion via Convex Optimization . Ada juga generalisasi yang sangat keren di mana Anda diizinkan untuk mengambil sampel secara sewenang-wenang untuk ruang matriks. Makalah ini oleh David Gross, Memulihkan matriks peringkat rendah dari beberapa koefisien dalam basis apa pun menggunakan generalisasi ini untuk secara substansial menyederhanakan bukti penyelesaian matriks, dan untuk beberapa basis Anda dapat menghapus asumsi inkoherensi juga. Makalah itu juga berisi batas terbaik hingga saat ini pada kompleksitas pengambilan sampel. Mungkin terdengar aneh untuk mengambil sampel secara sewenang-wenang, tetapi sebenarnya cukup alami dalam pengaturan mekanika kuantum, lihat misalnya makalah ini, tomografi keadaan kuantum melalui penginderaan terkompresi .

Ada penginderaan terkompresi berbasis manifold, di mana kondisi sparsity digantikan oleh kondisi bahwa data terletak pada submanifold dimensi rendah dari ruang alami sinyal. Perhatikan bahwa sparsity dapat diartikan sebagai berbaring pada bermacam-macam jenis (pada kenyataannya, variasi garis potong).

Lihat, misalnya makalah ini dan referensi dalam pengantar. (Saya akui tidak tahu apakah makalah ini mewakili wilayah tersebut - saya lebih akrab dengan topik terkait dari berbagai pengklasifikasi berbasis manifold a la Niyogi-Smale-Weinberger .)

Saya kira bahwa, pada tingkat generalitas di mana saya mengajukan pertanyaan, makalah "Kompresi sumber yang dapat dicoba" oleh Trevisan, Vadhan dan Zuckerman (2004) juga memenuhi syarat sebagai satu jawaban yang mungkin. Mereka menunjukkan bahwa dalam banyak kasus, jika sumber string input memiliki kompleksitas rendah (misalnya, disampel oleh mesin logspace), maka seseorang dapat mengompres, dan mendekompresi, dalam waktu polinomial untuk memanjang konstanta aditif menjauh dari entropi sumber.

Saya tidak benar-benar tahu apakah penginderaan terkompresi dapat dimasukkan ke dalam teori kompresi yang lebih besar.

Salah satu analog penginderaan tekan dalam pembelajaran mesin ketika Anda mencoba untuk memperkirakan vektor berat dimensi tinggi (misalnya, dalam klasifikasi / regresi) dari ukuran sampel yang sangat kecil. Untuk berurusan dengan sistem persamaan linear yang tidak ditentukan dalam pengaturan seperti itu, orang biasanya memberlakukan sparsity (melalui hukuman l0 atau l1) pada vektor bobot yang dipelajari. Untuk melihat koneksi, pertimbangkan masalah klasifikasi / regresi berikut dari pembelajaran mesin:

Mewakili N contoh dimensi D masing-masing (D >> N) sebagai matriks NxD X. Mewakili respons N (satu untuk setiap contoh) sebagai vektor Nx1 Y. Tujuannya adalah untuk memecahkan untuk theta vektor Dx1 melalui persamaan berikut : Y = X * theta

Sekarang di sini adalah analogi masalah ini untuk penginderaan tekan (CS): Anda ingin memperkirakan / mengukur theta yang merupakan vektor dimensi D (mirip dengan "sinyal" yang tidak diketahui dalam CS). Untuk memperkirakan ini, Anda menggunakan matriks X (mirip dengan matriks desain dalam CS) dan pengukuran N 1-D Y (mirip dengan sinyal terkompresi dalam CS, karena D >> N).

Lihat: http://www.damtp.cam.ac.uk/user/na/people/Anders/Inf_CS43.pdf