Kebingungan tentang masalah penginderaan terkompresi

13

Saya membaca beberapa referensi termasuk ini .

Saya agak bingung apa masalah optimasi terkompresi penginderaan membangun dan mencoba untuk menyelesaikannya. Apakah itu

\begin{array}{ll} minimize & ‖ x ‖_{1} \\ subject to & A x = b \end{array}

$\begin{array}{ll} \text{minimize} & \|x\|_1\\ \text{subject to} & Ax=b\end{array}$

atau dan

\begin{array}{ll} minimize & ‖ x ‖_{0} \\ tunduk pada & SEBUAH x = b \end{array}

$\begin{array}{ll} \text{minimize} & \|x\|_0\\ \text{subject to} & Ax=b\end{array}$

atau sesuatu yang lain?

optimization Tim
sumber

18

Brian sangat tepat. Tapi saya pikir sangat membantu untuk menambahkan beberapa konteks penginderaan terkompresi.

Pertama, perhatikan bahwa apa yang disebut 0 norma — fungsi kardinalitas, atau jumlah nilai bukan nol dalam — bukan norma . Mungkin terbaik untuk menuliskannya sebagai sesuatu seperti dalam konteks apa pun kecuali yang paling kasual. Jangan salah paham, Anda berada di perusahaan yang baik ketika Anda menggunakan singkatan, tapi saya pikir itu cenderung menimbulkan kebingungan. $\|x\|_0$ $x$ $\mathop{\textbf{card}}(x)$ $\|x\|_0$

Orang sudah lama mengetahui bahwa meminimalkan norma cenderung menghasilkan solusi yang jarang. Ada beberapa alasan teoritis untuk ini yang ada hubungannya dengan saling melengkapi linier. Tetapi yang paling menarik bukanlah bahwa solusinya jarang, tetapi sering kali paling jarang . Artinya, meminimalkan benar-benar memberi Anda solusi kardinalitas minimum dalam kasus-kasus tertentu yang bermanfaat. (Bagaimana mereka mengetahui hal ini, ketika masalah kardinalitas minimum NP-keras? Dengan membangun masalah buatan dengan solusi jarang dikenal.) Ini bukan sesuatu yang bisa diprediksi oleh teori komplementaritas linier. $\ell_1$ $\|x\|_1$ $\|x\|_1$

Bidang penginderaan terkompresi lahir ketika para peneliti mulai mengidentifikasi kondisi pada matriks yang akan memungkinkan mereka untuk memastikan sebelumnya bahwa solusi juga yang paling jarang. Lihat misalnya, makalah-makalah paling awal oleh Candé, Romberg, dan Tao , dan diskusi-diskusi lain tentang properti isometry yang dibatasi, atau RIP . Situs web lain yang bermanfaat jika Anda benar-benar ingin mempelajari beberapa teori adalah halaman penginderaan terkompresi Terence Tao . $A$ $\ell_1$

Michael Grant
sumber

12

Kami akan senang bisa menyelesaikannya

$\min \| x \|_{0}$

st

$Ax=b$

tetapi masalah ini adalah masalah optimasi kombinatorial NP-Hard yang tidak praktis untuk dipecahkan dalam praktik ketika , , dan memiliki ukuran tipikal dalam penginderaan tekan. Dimungkinkan untuk menyelesaikan secara efisien $A$ $x$ $b$

$\min \| x \|_{1}$

st

$Ax=b$

baik secara teori (dapat dilakukan dalam waktu polinomial) dan dalam praktik komputasi untuk masalah yang bahkan cukup besar yang muncul dalam penginderaan tekan. Kami menggunakan sebagai "pengganti" untuk . Ini memiliki beberapa pembenaran intuitif (minimisasi satu-norma lebih suka solusi dengan lebih sedikit entri bukan nol dalam ), serta pembenaran teoretis yang jauh lebih canggih (teorema bentuk "Jika memiliki solusi k-jarang maka minimalkan akan menemukan solusi dengan probabilitas tinggi. " $\| x \|_{1}$ $\| x \|_{0}$ $x$ $Ax=b$ $\| x \|_{1}$

$Ax=b$ $\| Ax - b \|_{2} \leq \delta$

$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

Brian Borchers
sumber

8

$\ell^1$ $\ell^0$

min ‖ x ‖_{0} s.t A x = b

$\min\|x\|_0\quad\text{s.t}\quad Ax=b$

min ‖ x ‖_{1} s.t. A x = b .

$\min\|x\|_1\quad\text{s.t.}\quad Ax=b.$

Dimungkinkan untuk mengidentifikasi sinyal jarang dari beberapa pengukuran.

Compressed Sensing benar-benar tentang mengambil pengukuran sesedikit mungkin untuk mengidentifikasi sinyal di kelas sinyal tertentu.

Satu frase yang menarik adalah:

Mengapa kamera 5 megapiksel Anda benar-benar mengukur 15 juta nilai (tiga untuk setiap piksel) yang menghabiskan biaya 15 megabita data saat hanya menyimpan sekitar 2 megabita (setelah kompresi)?
Mungkinkah untuk mengukur 2 megabita segera?

Ada beberapa kerangka kerja yang sangat mungkin:

pengukuran linier
yang non-linear (mis. yang tanpa phas)
data vektor, data matriks / tensor
sparsity hanya sebagai jumlah bukan nol
sparsity sebagai "peringkat rendah" atau bahkan "kompleksitas rendah").

Dan ada juga lebih banyak metode untuk menghitung solusi jarang seperti pencocokan pengejaran (varian seperti pengejaran pencocokan ortogonal (OMP), pengejaran pencocokan ortogonal yang diatur (ROMP), CoSaMP) atau metode yang lebih baru berdasarkan pada algoritma passing pesan .

$\ell^1$ $\ell^0$

Namun, jika seseorang hanya tertarik untuk mendapatkan solusi yang jarang untuk sistem linier, ia melakukan sesuatu yang saya sebut rekonstruksi jarang .

Beladau
sumber

Terima kasih! Dapatkah Anda menguraikan kembali yang berikut ini ke dalam formulasi matematika: "Dimungkinkan untuk mengidentifikasi sinyal jarang dari beberapa pengukuran. Penginderaan Terkompresi sebenarnya tentang mengambil pengukuran sesedikit mungkin untuk mengidentifikasi sinyal dalam kelas sinyal tertentu."

Tim

1

Tidak, saya tidak bisa, karena Penginderaan Terkompresi bukanlah teori matematika melainkan konsep rekayasa.

Dirk

1

Saya pikir jawaban ini merupakan kontribusi yang baik, dan saya memilihnya. Sedangkan untuk frasa yang menarik, saya selalu punya masalah dengan itu. Ini menunjukkan bahwa CS sangat kuat sehingga Anda bisa membuang 13 juta piksel dan memulihkan gambar. Tapi tidak, Anda tidak boleh membuang data secara acak, bahkan dalam sistem CS --- algoritma pemulihan yang baik selalu dapat menggunakan lebih banyak data. Janji CS adalah potensi untuk mengembangkan sensor yang mengumpulkan lebih sedikit data di tempat pertama dengan imbalan penghematan praktis yang penting: penghematan daya, pengumpulan lebih cepat, dll.

Michael Grant

@MichaelGrant Saya setuju: Jangan membuang data yang sudah Anda ukur dan gunakan tanggal yang dapat Anda ukur dengan sedikit usaha.

Dirk

Kebingungan tentang masalah penginderaan terkompresi

Jawaban: