Dekomposisi Sinyal dan Pencarian Basis Ideal (2)

May 2008
M	T	W	T	F	S	S
« Apr		Jun »
	1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Posted by suksmono on May 16, 2008

Penggabungan berbagai basis ortogonal menjadi sebuah kamus basis-lewat-lengkap (overcomplete) diharapkan dapat menaikkan efisiensi dekomposisi sinyal. Peningkatan kinerja sistem kompresi terjadi karena dua hal: (1) tingkat kompresi tinggi karena koefisien yang diambil hanya sedikit, dan (2) sejumlah kecil koefisien tadi sudah cukup untuk merekonstruksi sinyal secara baik. Namun demikian pencarian vektor didalam basis overcomplete dengan kriteria cacah koefisien terkecil memerlukan sumberdaya komputasi yang sangat besar. Melalui prinsip ketidakpastian, masalah ini dapat diubah menjadi optimisasi konveks yang lebih mudah dipecahkan. Syaratnya, sinyal harus bersifat sparse.

Tinjau gabungan M buah sistem basis ortogonal ${\Phi}_{1}, {\Phi}_{2}, ...,{\Phi}_{M}$ yang masing-masing berukuran N×N menjadi satu buah basis overcomplete $\Phi={\Phi}_{1} \cup {\Phi}_{2} ...\cup {\Phi}_{M}$ . Basis baru $\Phi$ ; yang juga disebut sebagai dictionary (kamus basis), akan memiliki dimensi N×MN. Suatu sinyal s=[s₁ s₂ ... s_N]^T sepanjang N cuplikan dapat dinyatakan dengan berbagai macam kombinasi linier vektor-vektor basis yang ada didalam $\Phi$ , bahkan dari masing-masing sistem basis ortogonal ${\Phi}_{m}$ karena bersifat lengkap. Dengan pertimbangan efisiensi yang merupakan tuntutan kompresi sinyal, haruslah dipilih kombinasi yang berbentuk:

$s=\sum_{\gamma} {\alpha}_{\gamma}{\phi}_{\gamma}$ (1)

dimana ${\phi}_{\gamma}$ adalah vektor basis didalam $\Phi$ . Pada penjumlahan tersebut $\gamma = (m,i)$ menyatakan bahwa komponen tersebut adalah vektor basis ke–i didalam sistem basis ${\Phi}_{m}$ . Pertimbangan efisiensi mengharuskan cacah ${\alpha}_{\gamma}$ , yaitu

${||\alpha||}_{0} = \sum_{\forall \gamma} {|{\alpha}_{\gamma}|}_{0}$ (2)

sekecil mungkin. Sebagai ilustrasi arti norm diatas , tinjau contoh perhitungan berikut ini.

Suatu dictionary $\Phi$ yang merupakan hasil penggabungan 2 buah basis ortogonal memiliki dimensi 4×2, dimana
${\Phi}_{1}=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}$ , ${\Phi}_{2}= \frac{1} {\sqrt{2}} \begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$ , dan $\Phi=\begin{pmatrix}1 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 1 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix}$

Tiga dari empat basis didalam $\Phi$ ini dapat dipakai untuk menyatakan sebuah sinyal yang panjangnya dua cuplikan, misalnya ${s=\begin{pmatrix} -0.75/\sqrt{2} & 1-0.75/\sqrt{2} \end{pmatrix}}^{T}$ . Sinyal ini dapat terbentuk dari $\gamma \in \Gamma= \begin{Bmatrix}(1,2), (2,1), (2,2) \end{Bmatrix}$ , masing-masing dengan koefisien ${\alpha}_{(1,2)}=0.25, {\alpha}_{(2,1)}=-0.25, dan \: {\alpha}_{(2,2)}= -0.5$ . Dengan demikian ${\alpha}_{(1,2)}=0.25, {\alpha}_{(2,1)}=-0.25, {\alpha}_{(2,2)}= -0.5$ , sehingga
${||\alpha||}_{0}={0.25}^{0}+{0.25}^{0}+{0.5}^{0}=1+1+1=3$
Terlihat bahwa norm diatas hanya menghitung cacah dari koefisien terpilih.

Pencarian basis representasi sinyal s didalam $\Phi$ dengan cacah terkecil disebut sebagai masalah (P₀) yang dapat dinyatakan sebagai optimisasi berikut:

$({P}_{0}): min {||\alpha||}_{0}, \: \; s.t.\; \; s=\sum_{\gamma} {\alpha}_{\gamma}{\varphi}_{\gamma}$ (3)

Mengingat ada sejumlah tak-berhingga solusi dari sistem persamaan linier yang underdetermined, apakah nilai minimum ini dapat ditemukan? Untuk pasangan basis waktu-frekuensi, Donoho memberikan batasan supaya pencarian menemukan solusi yang unik dengan menggunakan prinsip ketidakpastian sebagai berikut.

Teorema 1. Jika s(n) adalah sinyal waktu diskrit sepanjang N cuplikan yang memiliki N_t buah support (koefisien tak-nol), sedangkan S(k) adalah transform Fourier sinyal tersebut yang memiliki N_w buah support, maka ${N}_{t} {N}_{\omega} \geq \sqrt{N}$ atau
${N}_{t}+{N}_{\omega} \geq 2 \sqrt{N}$ (4)

Jika cuplikan yang bernilai tak-nol (support) dari sinyal di kedua wilayah kurang dari setengah batas prinsip ketidakpastian diatas, maka P₀ akan memiliki solusi yang unik.

Teorema 2. Tinjau sinyal s(n) yang tersusun dari himpunan T vektor basis kawasan waktu dan himpunan $\Omega$ basis dari kawasan frekuensi. Jika
$|T|+|\Omega| \leq \sqrt{N}$ (5)
maka P₀ akan memiliki solusi yang unik. Sementara itu akan ada sinyal s(n) lain sedemikian hingga $|T|+|\Omega| = \sqrt{N}$ dan P₀ akan memiliki solusi yang tidak unik.

Pada teorema ini, notasi |.| menyatakan kardinalitas atau banyaknya anggota himpunan. Donoho menunjukkan hasil diatas dengan meninjau kasus fungsi ekstremal sisir Dirac (Dirac comb) yang telah dijelaskan sebelumnya. Untuk N bilangan kuadrat sempurna (perfect square), misalnya 4, 9, 16, … dst, sisir Dirac memiliki support sebesar $\sqrt{N}$ di kawasan waktu maupun kawasan frekuensi. Ini berarti bahwa sebuah sisir Dirac dapat dinyatakan sebagai $\sqrt{N}$ buah vektor basis impuls atau $\sqrt{N}$ buah basis Fourier, sehingga representasinya didalam basis gabungan impuls-Fourier tidaklah unik. Akibatnya solusi dari P₀ juga tidak unik. Sebaliknya, jika jumlah support-nya kurang dari $K= \sqrt{N}$ , maka akan hanya ada satu buah solusi saja, sehingga solusi P₀ akan bersifat unik.

Meskipun solusinya unik, memecahkan masalah P₀ bukanlah hal yang mudah. Untuk mengatasi hal ini, Chen dan Donoho mengajukan teknik Basis Pursuit, yaitu dengan menggantikan P₀ dengan optimisasi P₁ sebagai berikut:

$({P}_{1}): min {||\alpha||}_{1}, \: \; s.t.\; \; s=\sum_{\gamma} {\alpha}_{\gamma}{\varphi}_{\gamma}$ (6)

Keberadaan solusi P₁ memerlukan batasan support sinyal didalam $\Phi$ yang lebih kecil lagi, yaitu kurang dari setengah batas P₀. Untuk basis waktu-frekuensi, ketentuan ini dinyatakan dalam teorema berikut.

Teorema 3. Untuk sinyal s seperti pada Teorema 2, jika
$|T| + |\Omega| \leq \frac{1}{2}\sqrt{N}$
maka solusi dari P₁ adalah unik, yang juga merupakan solusi unik untuk P₀. Sementara itu, ada sinyal yang jika $|T| + |\Omega| = \frac{1}{2}\sqrt{N}$ dimana P₁ memiliki solusi yang tidak unik.

Sinyal dengan support dibawah batas ketentuan P₁ ini disebut sebagai sinyal sparse karena dapat dibentuk hanya dari sejumlah kecil vektor basis didalam $\Phi$ . Secara singkat dapat dirangkum sebuah hasil penting berikut ini:

Jika suatu sinyal s bersifat sparse dalam kawasan waktu-frekuensi, maka dekomposisinya bersifat unik dan algoritma Basis Pursuit atau P₁ akan dapat menemukannya.

Bagaimana dengan pasangan basis selain waktu-frekuensi? Pada tulisan sebelumnya dikatakan bahwa prinsip ketidakpastian di sebarang kawasan telah diperumum oleh Elad dan Bruckstein dengan memasukkan faktor koherensi antara sistem basis $\mu ({\Phi}_{1}, {\Phi}_{2})$ yang secara konsisten akan kembali menjadi WHUP jika kedua basis adalah pasangan waktu-frekuensi. Dasar pemikiran ini dipakai oleh Elad-Bruckstein maupun Donoho-Huo untuk menghasilkan teorema keunikan dari solusi P₁ berikut.

Teorema 4. Andaikan $\Phi= {\Phi}_{1} \cup {\Phi}_{2}$ adalah gabungan kedua basis. Jika suatu sinyal waktu diskrit s dapat dinyatakan sebagai $s=\Phi \alpha$ dengan $\alpha$ memenuhi syarat
${||\alpha||}_{0} \leq \frac {1}{2} \left( 1+ \frac {1} {\mu ({\Phi}{1}, {\Phi}{2})} \right)$ (7)
maka $\alpha$ adalah solusi unik dari P₁ dan juga sekaligus merupakan solusi unik dari P₀.

Dalam bahasa yang kurang-teknis, teorema ini mengatakan bahwa suatu sinyal s yang terbentuk dari kombinasi linier vektor-vektor basis didalam kamus-basis $\Phi$ dapat ditemukan vektor basis penyusunnya dengan memecahkan masalah optimisasi (P₁), asalkan jumlah vektor basis penyusun sinyal ini kurang dari nilai tertentu.

Seberapa besar signifikansi perubahan optimisasi P₀ menjadi P₁? Meskipun sekilas optimisasi ini hanya mengubah norm dari l₀ menjadi l₁, perubahan yang terjadi sangat besar. Saat ini, kebanyakan algoritma optimisasi didalam pengolahan sinyal justru menggunakan kriteria atau fungsi biaya kuadratis yang tak lain adalah l₂. Penjelasan diatas bahkan menginginkan pencarian solusi ideal dengan kriteria l₀. Dari sudut pandang pencarian ruang solusi, optimisasi dengan kriteria l₂ dan l₁ bersifat konveks, sedangkan l₀ bukan konveks. Algoritma untuk mencari solusi dari optimisasi konveks yang efisien telah banyak tersedia. Transformasi dari masalah l₀ menjadi l₁ ini disebut juga sebagai proses konveksifikasi.

Salah satu contoh sederhana didalam statistik mengenai berbagai norm ini adalah perhitungan mencari nilai tengah dari populasi. Meminimumkan nilai kesalahan kuadrat terkecil, yang tak lain adalah l₂, akan menghasilkan nilai mean cuplikan, sedangkan jika yang diminumkan adalah nilai absolut kesalahan atau l₁, solusinya akan berupa median. Pada pengolahan sinyal atau citra dijital, para peneliti menemukan bahwa tapis median lebih kokoh (robust) terhadap derau jika dibandingkan dengan tapis mean. Analogi yang sama dapat dipakai untuk menjelaskan mengapa P₁ ini memiliki peranan yang sangat penting dalam pencarian basis sinyal yang ideal.

Referensi

[1]. M. Elad and A.M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of basis,” IEEE Trans. Info. Theory, 49. 2558-3567.

[2]. S.S. Chen, D. Donoho, and MA Saunders, ”Atomic decomposition by basis pursuit,” SIAM J. on Scientific Computing, 20(1):33-61, 1999.

[3]. DL Donoho & PB Stark, ”Uncertainty principles and signal recovery”, SIAM J. on Applied Math., 49(3):906-31, 1989.

[4]. DL Donoho & X. Huo, Uncertainty Principles and Ideal Atomic Decomposition, Tech. Report, Stanford University.

This entry was posted on May 16, 2008 at 2:41 pm and is filed under Compressive Sensing, Signal Decomposition and Search of Basis, Theory and Concept, Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Dekomposisi Sinyal dan Pencarian Basis Ideal (2)”

suksmono said

May 16, 2008 at 3:07 pm
Posting kali ini tanpa Matlab, sebagai bentuk protes pembatalan hari libur Senin 19 Mei 2008 minggu depan, he..he…’nggak ding

Reply
A.D Setiawan said

May 16, 2008 at 5:31 pm
Pak mau tanya: kalau koherensi antara matrik pengukuran dan matriks basis tidak sama dengan satu, artinya keduanya tidak fully incoherence apa akibatnya? Apakah basis pursuit masih bisa menemukannya dan sampai batas berapa harga koherensi agar si basis pursuit dapat menemukan solusi yang unik?

Reply
suksmono said

May 16, 2008 at 5:57 pm
Persamaan (7) dalam T.4 justru mengindikasikan bahwa semakin rendah $\mu$ , akan semakin “baik”, dalam arti, sinyal dengan komponen beragam dapat dicari vektor basisnya. Batasan dalam teorema tsb strict, kalau nilai (in-)koherensi hanya satu, sinyal yang mampu di-dekomposisi secara unik ya hanya sinyal yang terdiri dari satu komponen basis $\Phi$ . Krg lbh begitu tafsirannya.

Reply