Hubungan Penginderaan Terkompresi dengan Regulasi L1

Saya mengerti bahwa penginderaan terkompresi menemukan solusi yang paling jarang

y = A x

$y = Ax$ dimana

x \in R^{D}

$x \in \mathbb{R}^D$ ,

A \in R^{k \times D}

$A \in \mathbb{R}^{k \times D}$ , dan

y \in R^{k}

$y \in \mathbb{R}^{k}$ ,

k << D

$k << D$ .

Dengan cara ini kita dapat merekonstruksi $x$ (asli) menggunakan $y$ (Kompresi), cukup cepat. Kami mengatakan itu $x$ adalah solusi paling jarang. Sparsity dapat dipahami sebagai $l_0$ -norm untuk vektor.

Kita juga tahu bahwa $l_1$ -norm (dipecahkan menggunakan pemrograman linier) adalah pendekatan yang bagus untuk $l_0$ -norm (yang merupakan NP-hard untuk vektor besar). Karena itu $x$ juga yang terkecil $l_1$ solusi untuk $Ax=y$

Saya pernah membaca bahwa penginderaan terkompresi mirip dengan regresi dengan penalti laso ( $l_1$ ). Saya telah melihat interpretasi geometris dari ini juga, tetapi saya belum membuat koneksi secara matematis.

Selain meminimalkan $l_1$ norma, apa hubungan (matematis) antara kompresi dan Lasso?

lasso sparse ilanman
sumber

terkait: quora.com/...

Charlie Parker

menurut pemahaman saya, Compressed Sensing adalah bidang yang mempelajari pemulihan Sinyal Jarang dan Regulasi L1 hanyalah satu formulasi khusus untuk kira-kira menyelesaikannya.

Charlie Parker

Pada dasarnya tidak ada perbedaan. Itu hanya terminologi ahli statistik vs terminologi insinyur listrik.

Penginderaan terkompresi (lebih tepatnya, pencarian basis denoising [1]) adalah masalah ini:

$\text{arg min}_x \frac{1}{2}\|Ax - b\| + \lambda \|x\|_1$

sedangkan Lasso [2] adalah masalah ini

$\text{arg min}_{\beta} \frac{1}{2}\|y - X\beta\| + \lambda \|\beta\|_1$

Sejauh ada perbedaan, itu adalah bahwa dalam aplikasi Penginderaan Terkompresi, Anda (insinyur) bisa memilih untuk "berperilaku baik" sementara, untuk Lasso, Anda (ahli statistik) tidak bisa memilih dan harus berurusan dengan data apa pun (dan jarang "bagus" ...). Akibatnya, banyak literatur Penginderaan Terkompresi berikutnya telah berfokus pada memilih untuk menjadi "seefisien" mungkin, sementara banyak literatur statistik berikutnya telah berfokus pada perbaikan pada laso yang masih bekerja dengan yang "memecah" laso. $A$ $X$ $A$ $X$

[1] SS Chen, DL Donoho, MA Saunders. "Dekomposisi Atom oleh Basis Pursuit." Jurnal SIAM untuk Scientific Computing 20 (1), hal.33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani "Penyusutan dan Pemilihan Regresi melalui laso." Jurnal Masyarakat Statistik Kerajaan: Seri B 58 (1), hal.267–88, 1996. JSTOR 2346178.

mweylandt
sumber

tetapi biasanya penginderaan terkompresi disebut sebagai sedemikian rupa sehingga . Apakah itu benar-benar setara dengan min jika demikian mengapa dan bagaimana lambda jatuh dalam gambar aslinya?

m i n ‖ x ‖_{1}

$min \| x \|_1$

A x = b

$Ax=b$

‖ A x - b ‖ + λ ‖ x ‖_{1}

$\|Ax - b \| + \lambda \| x \|_1$

Charlie Parker

Formulasi yang Anda berikan (dengan batasan kesetaraan) adalah "batas" dalam arti sebagai . Itu muncul ketika Anda menganggap tidak ada noise dalam sistem (sehingga sering disebut "basis pengejaran" sebagai lawan "pengejaran basis pengejaran").

λ \to 0

$\lambda \to 0$

mweylandt

sesuatu yang saya bingung adalah saya mencocokkan metode pengejaran di mana algoritma serakah untuk (kurang-lebih) menyelesaikan . Namun, saya pikir algoritma thresholding lunak di mana solver yang tepat untuk formulasi relaksasi cembung . Jadi, jika ini benar apakah mereka akan mengarah ke solusi yang sama? yaitu tampaknya Lasso dan OM menyelesaikan masalah yang sama tetapi dengan formulasi yang sangat berbeda. Algoritma apa pun untuk LASSO menghasilkan solusi yang sama karena cembungnya jika OM adalah algoritma serakah untuk L0 maka saya akan menganggap mereka sangat berbeda. Apakah ini benar?

‖ X w - y ‖^{2} + λ ‖ w ‖_{0}

$\| Xw - y \|^2 + \lambda \| w \|_0$

‖ X w - y ‖^{2} + λ ‖ w ‖_{1}

$\| Xw - y \|^2 + \lambda \| w \|_1$

Charlie Parker

Saya pikir ini layak ditanyakan dalam pertanyaan terpisah. Secara umum, tidak ada - solusi L1 (laso) dan L0 (subset terbaik) berbeda. Tetapi ada keadaan khusus yang dipelajari dengan baik di mana versi L0 dan L1 dari masalah pengejaran basis (bukan basis pengejaran noise) memberikan solusi yang sama.

mweylandt

Ini pertanyaan lain: stats.stackexchange.com/questions/337113/…

Charlie Parker

Hubungan Penginderaan Terkompresi dengan Regulasi L1

Jawaban: