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

minimizex1subject toAx=b

atau dan

minimizex0tunduk padaSEBUAHx=b

atau sesuatu yang lain?

Tim
sumber

Jawaban:

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 xbukan norma . Mungkin terbaik untuk menuliskannya sebagai sesuatu seperti kartu ( x ) dalam konteks apa pun kecuali yang paling kasual. Jangan salah paham, Anda berada di perusahaan yang baik ketika Anda menggunakan x 0 singkatan, tapi saya pikir itu cenderung menimbulkan kebingungan.x0xcard(x)x0

Orang sudah lama mengetahui bahwa meminimalkan norma x 1 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 x 1 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.1x1x1

Bidang penginderaan terkompresi lahir ketika para peneliti mulai mengidentifikasi kondisi pada matriks yang akan memungkinkan mereka untuk memastikan sebelumnya bahwa solusi 1 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 .A1

Michael Grant
sumber
12

Kami akan senang bisa menyelesaikannya

minx0

st

Ax=b

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

minx1

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 x 0 . Ini memiliki beberapa pembenaran intuitif (minimisasi satu-norma lebih suka solusi dengan lebih sedikit entri bukan nol dalam x ), serta pembenaran teoretis yang jauh lebih canggih (teorema bentuk "Jika A x = b memiliki solusi k-jarang maka minimalkan x 1 akan menemukan solusi dengan probabilitas tinggi. " x1x0xAx=bx1

Ax=bAxb2δ

minAxb22+λx1

Brian Borchers
sumber
8

10

minx0s.tAx=b
minx1s.t.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 .

10

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