November 2009
M	T	W	T	F	S	S
« Oct
	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

Archive for the ‘Signal Decomposition and Search of Basis’ Category

Dekomposisi Sinyal dan Pencarian Basis Ideal (4)

Posted by suksmono on May 22, 2008

Masalah pencarian vektor basis ideal dari sebuah sinyal telah dapat diformulasikan sebagai proses optimisasi berkendala (constrained optimization) P₁. Tulisan ini akan terlebih dahulu membahas secara sekilas konsep optimisasi linier, khususnya LP (Linear Programming), dan metode pemecahannya. Meskipun kendala dalam P₁ sebenarnya bersifat tak-linier, pengaturan parameter yang tepat dan batas-batas yang sesuai dapat mengubahnya menjadi permasalahan pemrograman linier. Suatu contoh pencarian basis ideal dari sinyal hasil bentukan sepasang ortobasis dipakai untuk menunjukkan kegunaan LP. Jika batasan sparsity terpenuhi, LP dapat menemukan seluruh basis penyusun sinyal sehingga sinyal dapat direkonstruksi secara eksak.

Pemrograman Matematika dan Optimisasi

Didalam optimisasi ada suatu fungsi objektif yang akan dioptimumkan; dibuat minimum atau maksimum. Kendala memberi batas wilayah dimana fungsi ini berlaku. Dari berbagai macam metoda optimisasi yang ada, salah satu yang memiliki pemakaian luas adalah pemrograman linier (LP/Linier Programming), suatu bentuk khusus dari pemrograman matematika (Mathematical Programming). Bahkan metoda Simpleks yang ditemukan oleh G. Dantzig untuk mencari solusi masalah LP dinobatkan sebagai satu dari sepuluh algoritma terbaik abad keduapuluh.

LP pada dasarnnya merupakan masalah pencarian nilai optimum dari suatu fungsi linier dengan kendala yang juga berbentuk linier. Berikut ini contoh sederhana dari permasalahan LP:

Tentukan harga ${x}_{1}$ dan ${x}_{2}$ yang meminimumkan nilai ${x}_{1}-{x}_{2}$ , dengan syarat bahwa ${x}_{1}+{x}_{2} \leq 10$ , ${x}_{1}-{x}_{2} \leq 5$ , dan ${x}_{1} \geq1 \: , {x}_{2} \geq 1$ .

Masalah diatas dapat dituliskan kedalam bentuk baku sebagai berikut:

minimize ${x}_{1}-{x}_{2}$

subject to:

${x}_{1}+{x}_{2} \leq 10$ ,

${x}_{1}-{x}_{2} \leq 5$ ,

${x}_{1} \geq1 \: , {x}_{2} \geq 1$ .

Nilai yang akan dioptimalkan disebut sebagai fungsi obyektif, dalam soal diatas adalah ${x}_{1}-{x}_{2}$ . Pemecahan masalah ini dapat dilakukan secara grafis dengan cara menggambarkan semua kendala, lalu mencari titik dimana nilai obyektif mencapai optimum dalam daerah solusi:

Gambar 1. Ilustrasi pencarian titik optimum dalam LP

Pada Gambar 1 diatas, daerah yang diarsir adalah pasangan $\left( {x}_{1},{x}_{2} \right)$ yang memenuhi semua kendala yang diberikan atau disebut juga feasible region. Kita harus mencari satu titik dimana nilai fungsi obyektif mencapai optimal. Pada LP, solusi selalu terletak di pojok wilayah daerah atau titik simpul. Program Matlab berikut dapat dipakai untuk mencari solusinya:

%pemrograman linier untuk masalah sederhana

% min c’x s.t. Ax<=b; x1>=1, x2>=1

%——————————————

c=[1;-1]; % koefisien fungsi obyektif

A=[1 1; 1 -1]; %matriks A

b=[10; 5]; % kendala

lb=[1 1] ; %batas bawah x1 dan x2

[x, fval,exitflag,output,lambda]=linprog(c,A,b,[],[],lb);

disp(sprintf(‘x1= %f x2=%f\n’,x(1),x(2))); %tampilkan

Dari eksekusi program akan diperoleh nilai ${x}_{1}=1, {x}_{2}=9$ yang akan menghasilkan nilai fungsi objektif paling kecil, yaitu -8. Posisi titik optimum ini terletak dipojok paling kiri atas dari politop yang menyatakan daerah solusi.

Metoda simpleks dari Dantzig melakukan perunutan setiap tepian wilayah hingga ditemukan titik optimal yang selalu terletak di sudut atau verteks dari politop. Dengan demikian, dapat ditunjukkan bahwa pada kondisi terburuk, metoda ini akan memiliki kompleksitas yang tumbuh secara eksponensial. Namun kebanyakan masalah praktis dapat dipecahkan dengan cukup cepat, karena kompleksitas rata-ratanya cukup kecil hingga dapat ditangani.

Masalah pertumbuhan kompleksitas perhitungan dalam metoda Simpleks akhirnya dapat diatasi oleh Narendra Karmakar dengan metoda interior point (IPM), yang memiliki kompleksitas polinomial. IPM tidak hanya dipakai pada optimisasi linier, kasus lain yang taklinier-pun dapat dipecahkan dengan metoda ini asalkan daerah solusi bersifat konveks. IPM mencapai kompleksitas polynomial karena tidak lagi merunut tepian daerah solusi, tapi masuk menerobos kedalam wilayah ini sampai solusi yang dicari dapat ditemukan.

Masalah optimisasi seperti diatas dapat dituliskan dalam bentuk umum sebagai berikut:

minimize ${c}_{1} {x}_{1} + {c}_{2} {x}_{2} + ... + {c}_{n} {x}_{n}$

subject to:

${a}_{11} {x}_{1}+ {a}_{12} {x}_{2} + ... + {a}_{1n} {x}_{n}$

${a}_{21} {x}_{1}+ {a}_{12} {x}_{2} + ... + {a}_{2n} {x}_{n}$

$.........................................$

${a}_{m1} {x}_{1}+ {a}_{m2} {x}_{2} + ... + {a}_{mn} {x}_{n}$

${x}_{1}, {x}_{2}, ..., {x}_{n} \geq 0$

bahkan dengan dengan menggunakan slack variables

${x}_{n+1} = {b}_{j} \sum_{j=1 .. n} {a}_{ij} {x}_{j}$ , i = 1, 2, …, m

LP dapat dituliskan dalam bentuk matriks yang lebih ringkas, yaitu

minimize ${c}^{T} x$ subject to $Ax=b, \: x \geq 0$

Masalah mencari nilai minimum suatu fungsi obyektif dapat diubah menjadi pencarian maksimum fungsi obyektif yang lain dan demikian pula sebaliknya. Dengan demikian, pencarian nilai minimum diatas memiliki solusi yang sama dengan masalah dual-nya, yaitu pencarian nilai maksimum. Jika fungsi objektif dan kendala tidak lagi linier, fungsi dari peubah x ini dapat ditulis sebagai c(x) dan kendala dapat ditulis sebagai ${a}_{i}(x) \geq {b}_{i}$ .

Metode Basis Pursuit dengan Pemrograman Linier

Metoda basis pursuit merumuskan pencarian basis ideal ${\phi}_{m}$ didalam kamus-basis $\Phi$ berdimensi NxM sebagai masalah pemrograman konveks:

(P₁): $min \; {||\alpha ||}_{0} \; s.t. \; \Phi \alpha = s$

Telah diketahui sejak lama bahwa optimisasi non-linier l₁ seperti ini ekivalen dengan LP

$min \; {c}^{T}x \; s.t. \; Ax=b, x \geq 0$

jika dilakukan substitusi sebagai berikut

M↔2M; x↔ $( {\alpha}_{1},{\alpha}_{2})$ ; c↔[1 1 …. 1; 1 1… 1]; A↔ $\left[ \Phi, -\Phi \right]$ ; b↔s

Artinya, kamus-basis digabung dengan nilai negatif dari kamus tersebut untuk menggantikan peran matriks A, batas kendala b digantikan dengan sinyal s, panjang vektor solusi dibuat menjadi dua-kalinya, sedangkan fungsi objektif adalah penjumlahan masing-masing koefisien vektor solusi sparse $\alpha$ dan dimensi kolom diperbesar menjadi duakali-nya.

Cara ini selanjutnya akan dipakai untuk memecahkan masalah dekomposisi sinyal s terdahulu yang terdiri dari dua impuls dan dua vektor basis DCT. Sebagai tambahan, sinyal ini tercampur dengan derau acak Gaussian. Berikut ini kode Matlab-nya.

%———————————————–

%Basis pursuit on overcomplete basis

%Using Matlab Optimization Toolbox

%To search for solution … modified

%———————————————–

%length of signal

clear;close all;clc;

N=64; %signal dimension

over_factor=2; %over complete factor

nAtoms=N*over_factor;

%create pair of orto-basis dictionary

D1=eye(N,N); D2=dct(eye(N,N)); D=[D1;D2]‘;

%create a signal with N_support’

N_support=4;

pN=[8 32 73 125]; %dpt diganti dng indeks acak jika perlu

x=zeros(N,1); X=zeros(nAtoms,1);%’transformed-domain signal

for k=1:N_support;

x=x+D(:,pN(k)); X(pN(k))=1;

end;

x0=x;

figure(1);plot(x0);title(‘Original Signal’);

%perform measurement, >> add noise

derau=randn(N,1);

y = x0 + 5*derau/(derau’*derau);

min_y=min(y);

D_pos=-D;

%define dictionary A

A=zeros(N,2*over_factor*N);

A(:,1:over_factor*N)=D;

A(:,over_factor*N+1:2*over_factor*N)=D_pos;

%Basis Pursuit on random basis

f=ones(2*nAtoms,1); lb=zeros(2*nAtoms,1);

alpha=linprog(f,[],[],A,y,lb);

figure(2);plot(1:nAtoms,X,’r:’,1:nAtoms,alpha(1:nAtoms),’b–’);

legend(‘original’,'alpha’);

%obtain a few largest component, by sorting alpha

[z,imax]=sort(alpha(1:nAtoms));

%Reconstruct estimated signal

x_hat=zeros(N,1);

for k=1:N_support;

x_hat=x_hat+ D(:,imax(nAtoms-k+1));

end;

x_hat1=D*alpha(1:nAtoms);

figure(3);plot(1:N,x0,’k.’,1:N,y,’b-’,1:N,x_hat,’r:’,1:N,y-x0,’g-’,1:N,x_hat1,’k–’);

legend(‘original’,'noisy’,'estimated’,'noise-level’,'D*alpha’);

figure(4);plot(1:N,y-x0,’r-’,1:N,x_hat-x0,’b-’,1:N,x_hat1-x0,’k-’);

legend(‘initial error’,'estimation error’,'D*alpha error’);

Gabungan pasangan sistem-basis impulse-DCT menghasilkan sebuah kamus-basis berukuran 64×128. Batas sparsity Elad-Bruckstein untuk pasangan basis ini adalah sekitar (0.9).8 atau sekitar 7. Dengan hanya mengambil 4 buah vektor basis penyusun, yaitu vektor pada urutan ke 8, 32, 73, dan 125 haruslah P1 dapat menemukan solusi eksak-nya.

Gambar 2. Vektor basis terpilih didalam kamus basis

Gambar 2 menunjukkan vektor basis terpilih oleh P1 yang tepat berhimpit dengan basis penyusun sinyal. Dengan demikian seluruh komponen sinyal telah berhasil ditemukan. Disamping itu, koefisian basis lainnya jauh lebih kecil daripada komponen basis penyusun. Komponen ini biasanya dihilangkan dengan peng-ambangan (tresholding).

Gambar 3. Sinyal asal dan hasil rekonstruksi

Gambar 4. Sinyal kesalahan

Berbagai sinyal dibandingkan dalam Gambar 3. Terlihat bahwa sebenarnya tingkatan sinyal derau (kurva berwarna hijau) cukup tinggi jika dibandingkan dengan sinyal asalnya (titik-titik hitam), menghasilkan distorsi yang signifikan (sinyal warna biru). Namun demikian, karena semua koefisien berhasil ditemukan, sinyal dapat direkonstruksi secara eksak. Hal ini ditunjukkan pada Gambar 4, dimana sinyal kesalahan (biru) berharga nol.

Catatan: Beberapa browser menerjemahkan karakter ‘prime’ secara salah sehingga program yang ada di blog ini tidak bisa langsung di-copy paste dari halaman web ke Command Window Matlab untuk dijalankan. Perbaiki terlebih dahulu kesalahan ini sebelum menjalankan program.

Posted in Compressive Sensing, Signal Decomposition and Search of Basis, Theory and Concept, Uncategorized | Leave a Comment »

Dekomposisi Sinyal dan Pencarian Basis Ideal (3)

Posted by suksmono on May 19, 2008

Pencarian basis untuk pasangan transformasi waktu-frekuensi dapat diperluas untuk sebarang pasangan basis ortonormal. Berbagai macam basis baru yang telah ditemukan seiring maraknya penelitian wavelet dan analisis multiresolusi, baik yang ortonormal (mis. wavelet, Fourier, DCT, Hadamard, ridgelets), yang tak-ortonormal (mis. Gabor, pseudo-polar FFT), maupun transformasi non-kuadratis (Laplacian pyramid, wavelet invarian-geser) perlu dielaborasi supaya bisa dipakai untuk menyatakan berbagai macam bentuk sinyal yang ditemui di dunia nyata. Pencarian vektor basis ”ideal” didalam gabungan berbagai macam basis memerlukan generalisasi sifat keunikan dari representasi sinyal sparse. Tulisan ini memberikan penjelasan secara garis besar hasil-hasil yang telah dicapai oleh Elad-Bruckstein dan perbandingannya dengan formulasi dari Donoho.

Batas Keunikan Elad-Bruckstein dari Pasangan Orto-basis

Pada tulisan terdahulu telah diberikan batas Donoho-Huo (DHB: Donoho-Huo Bound) dari jumlah komponen penyusun sinyal ${|| \alpha ||}_{0}$ untuk setiap pasangan sistem basis ortonormal (ortobasis) $\Theta$ dan $\Psi$ supaya sinyal $s=[ \Psi , \Theta ] \alpha$ dapat dinyatakan secara unik dan P₁ sanggup menemukannya, yaitu

Batas P₁ Donoho-Huo: ${|| \alpha ||}_{0} < 0.5 (1+{\mu}^{-1})$

dimana $\mu = \mu (\Psi , \Theta )$ adalah koherensi antar basis. Pada kasus pasangan ortobasis ini, Elad dan Bruckstein memberikan batas yang lebih baik, sehingga cukup penting untuk dijelaskan terlebih dahulu.

Sebuah sinyal s sepanjang N-cuplikan dapat dinyatakan dalam sebarang sistem ortobasis, misalnya sebagai $s= \Theta {\alpha}_{1}$ atau $s= \Psi {\alpha}_{2}$ . Sebagaimana yang telah disinggung pada tulisan sebelumnya, koherensi antar sistem basis dapat dinyatakan sebagai

Koherensi pasangan basis: $1/\sqrt{N} \leq \mu( \Psi , \Theta) = \max_{\theta \in \Theta , \psi \in \Psi} | < \psi , \theta> | \leq 1$ (1)

Jumlah support sinyal s dari kedua kawasan adalah ${|| {\alpha}_{1}||}_{0} + {|| {\alpha}_{2}||}_{0}$ . Untuk setiap dua bilangan bulat positif x dan y, maka akan berlaku sifat ${x}^{2}+{y}^{2} \geq 2xy$ . Karena ${(x+y)}^{2} = ( {x}^{2} + {y}^{2} ) + 2xy$ maka akan berlaku pula ${ \left( x+y \right)}^{2} \geq 4xy$ , sehingga $x+y \geq 2 \sqrt{xy}$ . Dengan demikian relasi berikut akan berlaku:

Teorema 1. ${|| {\alpha}_{1}||}_{0} + {|| {\alpha}_{2} ||}_{0} \geq 2 \sqrt{ {|| {\alpha}_{1} ||}_{0}{|| {\alpha}_{2}||}_{0} } \geq \frac{2}{\mu}$ (2)

Hubungan antara dua suku terakhir pada pertidaksamaan diatas, yaitu $2 \sqrt{ {|| {\alpha}_{1} ||}_{0}{|| {\alpha}_{2} ||}_{0} } \geq \frac{2}{\mu}$ , dapat dijelaskan dengan analisis sederhana sebagai berikut:

Nilai $\sqrt{ {|| {\alpha}_{1} ||}_{0}{|| {\alpha}_{2} ||}_{0} }$ minimum terjadi jika keduanya basis impuls yang hanya memiliki satu komponen vektor bernilai tak-nol ${\alpha}_{1}$ dan ${\alpha}_{2}$ , sehingga ${|| {\alpha}_{1}||}_{0}= {|| {\alpha}_{2} ||}_{0} =1$ dan $\sqrt{{||{\alpha}_{1} ||}_{0}{|| {\alpha}_{2} ||}_{0}} = 1$ . Untuk pasangan basis ini, nilai koherensi mencapai maksimum atau $\mu=1$ sehingga $\sqrt{ {|| {\alpha}_{1} ||}_{0}{|| {\alpha}_{2} ||}_{0} } = 2/ \mu$ berlaku.
Disisi lain, nilai ${|| {\alpha}_{1}||}_{0} + {|| {\alpha}_{2} ||}_{0}$ maksimum terjadi jika semua komponen dari vektor ${\alpha}_{1}$ dan ${\alpha}_{2}$ tak nol, misalnya jika keduanya basis Hadamard. Pada saat tersebut ${|| {\alpha}_{1} ||}_{0}= {|| {\alpha}_{2} ||}_{0} =N$ dan $\sqrt{{||{\alpha}_{1} ||}_{0}{||{\alpha}_{2} ||}_{0}} = N$ . Nilai koherensi akan mencapai nilai maksimum juga, yaitu $\mu=1$ . Dengan demikian $\sqrt{ {|| {\alpha}_{1} ||}_{0}{|| {\alpha}_{2} ||}_{0} }=N \geq 2/ \mu$ juga berlaku.

Akhirnya diperoleh hubungan antara koherensi $\mu$ dengan batas dari jumlah koefisien dikedua kawasan, yaitu:

Batas P₁ Elad-Bruckstein: ${|| {\alpha}_{1} ||}_{0} + {|| {\alpha}_{2} ||}_{0} \geq \frac{2}{\mu}$ (3)

Batas atas ini tentu lebih baik daripada yang telah diperoleh Donoho-Huo sebelumnya, yang untuk kasus sinyal s ini dapat dituliskan:

Batas P₁Donoho-Huo: ${|| {\alpha}_{1} ||}_{0} + {|| {\alpha}_{2} ||}_{0} \geq 0.5 \left( 1+ {\mu}^{-1} \right)$ (4)

Andaikan bahwa sinyal ternormalisasi (berenergi satu satuan) s dapat dinyatakan dengan dua cara berbeda didalam kamus-basis $\Phi = \Psi \cup \Theta$ , yaitu $s = \Phi {\alpha}_{1}$ $= \Phi {\alpha}_{2}$ . Dengan demikian

$0 = \Phi \left( {\alpha}_{1} - {\alpha}_{2} \right) = \begin{pmatrix} \Psi & \Theta \end{pmatrix} \begin{pmatrix} {x}_{1} \\ {x}_{2} \end{pmatrix}$

Akibatnya $\Psi {x}_{1} + \Theta {x}_{2}=0$ atau $\Psi {x}_{1} = -\Theta {x}_{2}$ . Berdasarkan prinsip ketidakpastian, maka

$\frac{2}{\mu} \leq {||{x}_{1}||}_{0} + {||{x}_{2}||}_{0} = {||{\alpha}_{1}-{\alpha}_{2}||}_{0} \leq {||{\alpha}_{1}||}_{0} + {||{\alpha}_{2}||}_{0}$ , atau ${||{\alpha}_{1}||}_{0} + {||{\alpha}_{2}||}_{0} \geq \frac{\mu}{2}$

Ini berarti bahwa dua representasi dari sinyal yang sama tidak akan sekaligus sparse. Akhirnya diperoleh hasil berikut:

Teorema 2. Jika ada suatu representasi yang memenuhi syarat

batas keunikan P₀ Elad-Bruckstein: ${|| \alpha ||}_{0} < \frac {1}{\mu}$ (5)

maka haruslah representasi itu unik atau yang paling sparse.

Sampai dengan tahap ini, pencarian basis ideal $\alpha$ masih mengandalkan P₀. Tahap berikutnya adalah mencari batas sparsity dimana P₁ sanggup menemukan solusi yang identik dengan solusi P₀.

Untuk suatu sinyal $s=[ \Psi ; \Theta] \alpha$ , dengan asumsi sparsity pada $\alpha$ dan jumlah koefisien k₁<k₂ sehingga vektor

$\alpha= \begin{pmatrix} {\alpha}_{1} & {\alpha}_{2} & ... &{\alpha}_{N} & ; & {\alpha}_{N+1} & {\alpha}_{N+2} & ... {\alpha}_{2N} \end{pmatrix}$

memiliki k₁ buah koefisien tak nol dalam N koefisien pertama (yaitu di dalam $\Psi$ ) dan k₂buah tak nol untuk N koefisien kedua (didalam $\Theta$ ), Elad-Bruckstein mendapatkan hasil berikut:

Jika k1 dan k2 memenuhi hubungan $2{\mu}^{2}{k}_{1}{k}_{2} + \mu {k}_{2} - 1 <0$ , maka P₁ akan dapat menemukannnya.

Hasil yang lebih lemah tapi bentuknya sederhana diberikan oleh ${k}_{1} + {k}_{2} < \frac{\left (\sqrt{2} - 0.5 \right)}{\mu}$ , sehingga

Batas Keunikan P₁ Elad-Bruckstein: ${|| \alpha ||}_{0}<\frac{\sqrt{2}-0.5}{\mu} \sim \frac{0.9142}{\mu}$ (6)

Sebagai ilustrasi, untuk sinyal s sepanjang N=1024 cuplikan yang tersusun dari komponen pasangan basis impulse-Fourier, maka P₀ akan sanggup menemukan solusi untuk 32 vektor basis. Bandingkan dengan P₁ yang memberikan harga lebih kecil lagi, yaitu 16 menurut DHB. Untuk kasus pasangan basis ini, EBB memberikan angka untuk P₁ yang lebih besar, yaitu 29 buah.

Batas Keunikan P₀ dan P₁ untuk Kamus Basis

Keunikan untuk sepasang ortobasis telah diturunkan secara langsung dari prinsip ketidakpastian. Sebuah kamus basis bersifat overcomplete, yakni jumlah vektor basisnya jauh lebih banyak dari yang seharusnya cukup untuk membentuk sebuah vektor berdimensi N. Andaikan suatu sinyal s sepanjang N-cuplikan dapat dinyatakan dalam dua representasi didalam kamus-basis $\Phi$ yang dinyatakan sebagai matriks berdimensi NxK, dimana K>>N $s= \Phi {\alpha}_{1} = \Phi {\alpha}_{2}$ , dengan demikian $\Phi ({\alpha}_{1}-{\alpha}_{2}) = 0$ atau $\Phi v = 0$

Hasil terakhir menyatakan kombinasi linier vektor-vektor kolom dari $\Phi$ yang saling bergantung dan akan dicari sekelompok vektor yang demikian. Untuk keperluan ini akan diperkenalkan konsep spark dari suatu matriks yang dilambangkan sebagai $\sigma$ sebagai berikut

Definisi. Spark dari suatu matriks $\Phi$ yang dituliskan sebagai $\sigma = spark( \Phi )$ adalah bilangan bulat terkecil yang menyatakan banyaknya anggota dari sekelompok vektor kolom dari $\Phi$ yang saling bebas.

Berikut ini ilustrasi dari konsep nilai spark untuk dua buah matriks yang sederhana.

$spark\left[\begin{pmatrix}1 & 0 & ...&0 & 1\\ 0 & 1 & ... &0 & 1\\ ... & ... & ...&... & ... \\ 0 & 0 &0 & 1 & 1 \end{pmatrix} \right]=N+1$

sedangkan

$spark\left[\begin{pmatrix}1 & 0 & ...&0 & 1\\ 0 & 1 & ... &0 & 0\\ ... & ... & ...&... & ... \\ 0 & 0 &0 & 1 & 0 \end{pmatrix} \right]=2$

Apa hubungannya dengan rank? Rank sebuah matriks adalah jumlah maksimum vektor kolom yang saling-bebas, sedangkan spark adalah jumlah minimum vektor kolom yang tidak-saling-bebas. Secara umum hubungan berikut ini akan berlaku:

$2 \leq \sigma=spark (\Phi) \leq rank {{}\Phi{}} + 1$

Berdasarkan definisi, untuk sinyal s yang diatas akan berlaku ${||v||}_{0} \geq \sigma$ , dengan demikian $||{\alpha}_{1}-{\alpha}_{2} {||}_{0} \geq \sigma$ atau $\sigma \leq || {\alpha}_{1}-{\alpha}_{2} {||}_{0} \leq ||{\alpha}_{1} {||}_{0} + ||{\alpha}_{2} {||}_{0}$ .Akhirnya untuk kamus basis $\Phi$ akan diperoleh hubungan yang mirip dengan prinsip ketidakpastian yaitu

$||{\alpha}_{1} {||}_{0} + ||{\alpha}_{2} {||}_{0} \geq \sigma$ (7)

yang artinya bahwa dua buah representasi berbeda dari suatu sinyal s didalam kamus-basis $\Phi$ tidak boleh keduanya sekaligus sparse. Selanjutnya akan diperoleh persyaratan keunikan sinyal s sebagai berikut

Teorema 3. Representasi sinyal $s=\Phi \alpha$ dimana $|| \alpha {||}_{0} < \sigma/2$ akan bersifat unik.

Koherensi suatu kamus-basis $\Phi$ dapat didefinisikan dengan cara yang mirip seperti pasangan orto-basis sebagai berikut

Koherensi kamus-basis: $2 \leq \mu (\Phi) = {max}_{m \neq n} \left| <{\phi}_{m}, {\phi}_{n}> \right| \leq 1$ [8]

Berdasarkan teorema piringan Gershgorin, dapat ditunjukkan bahwa batas bawah (pesimistik) spark adalah $\sigma \geq (1+{\mu}^{-1})$ . Dengan demikian, dari [8] akan diperoleh

$||{\gamma}_{1} {||}_{0} +||{\gamma}_{1} {||}_{0} \geq \sigma \geq (1+{\mu}^{-1})$

dan dari Teorema 3 akan diperoleh

Teorema 4. Representasi sinyal $s=\Phi \alpha$ dimana $||\alpha {||}_{0} \leq 0.5( 1+ {\mu}^{-1} ) \leq \sigma/2$ akan bersifat unik.

Dengan cara yang sama seperti sebelumnya, keunikan sinyal s didalam kamus basis $\Phi$ terhadap optimasi P₁ dapat dinyatakan sbb;

Teorema 5. Diberikan suatu sinyal s dengan representasi $s=\Phi \alpha$ , jika $||\alpha {||}_{0} < 0.5( 1+{\mu}^{-1})$ maka P₁ atau algoritma Basis Pursuit akan dapat menemukannya.

Apa bedanya dengan yang diperoleh Donoho-Huo pada tulisan sebelumnya? Perbedaan pertama, jumlah support dari sinyal yang dibentuk pasangan orto-basis dalam penurunan Elad-Bruckstein lebih tinggi dari yang diberikan Donoho-Huo. Yang kedua, Elad-Bruckstein memberikan generalisasi dari pasangan basis ortogonal ke kamus-basis dengan batas sparsity yang diberikan oleh (9).

Contoh Permasalahan

Soal-1: Tentukan koherensi antara ortobasis DCT dan ortobasis acak tersebar normal, masing-masing berdimensi 512×512. Tentukan batas sparsity untuk P₁ berdasarkan DHB (Donoho-Huo Bound) dan EBB (Elad-Bruckstein Bound).

Jawab: Perhatikan bahwa sistem yang ditinjau adalah dua orto-basis, bukan kamus-basis. Dengan demikian, perhitungan koherensi akan memakai rumus (2) sedangkan batas sparsity adalah rumus (1) untuk DHB dan rumus (6) untuk EBB. Kode Matlab berikut dapat dipakai.

% progam menghitung koherensi dan batas sparsity

% antara basis DCT dengan basis acak Gaussian

clear;close all;clc;

N=512; %panjang sinyal yang diasumsikan

%buat basis DCT berdimensi NxN

THETA=dct(eye(N,N));

%buat basis acak Gaussian NxN

PSI=orth(randn(N,N)’)';

%hitung koherensi antara DCT dengan Gauss

mu_DCT_Gauss=mu_THETA_PSI(THETA,PSI);

disp(sprintf(‘koherensi DCT-Gauss = %f\n’, mu_DCT_Gauss));

%Tentukan batas sparsity

%kasus-1: DHB (Donoho-Huo bound)

N_DHB=floor(0.5*(1+1/mu_DCT_Gauss));

disp(sprintf(‘batas sparsity Donoho-Huo= %d\n’, N_DHB));

%kasus-2: EBB (Elad-Bruckstein bound)

N_EBB=floor((sqrt(2)-0.5)/mu_DCT_Gauss);

disp(sprintf(‘batas sparsity Elad-Bruckstein= %d’, N_EBB));

%==FUNGSI ===

%fungsi menghitung koherensi dua orto basis

function [mu]=mu_THETA_PSI(THETA,PSI);

[M,N]=size(PSI); %THETA diasumsikan berdimensi sama

CORR=transpose(conj(THETA))*PSI;

mu=max(max(CORR));

Hasil perhitungan memberikan nilai koherensi $\mu =0.219030$ , DHB =2, dan EBB = 4. Terlihat perbedaan cukup signifikan antara EBB dengan DHB.

Soal-2: Tentukan tingkat koherensi dari sebuah kamus-basis acak tersebar normal yang berdimensi 64×1024 dan hitunglah batas sparsity dari sinyal s sepanjang 64 cuplikan yang terbentuk dari kamus-basis ini!

Jawab: Didalam compressive sensing, basis acak dapat dianggap sebagai basis universal karena bersifat hampir ortogonal ke semua sistem basis lain. Koherensi dihitung menurut rumus (7) sedangkan batas sparsity memakasi rumus (9). Program Matlab berikut ini dapat dipakai untuk membantu pemecahan masalah ini.

% progam menghitung koherensi dan

% batas sparsity basis acak Gaussian

clear;close all;clc;

N=64;M=1024; %dimensi kamus basis

%buat basis acak Gaussian MxN

D=orth(randn(N,M)’)';

%hitung koherensi kamus basis D

mu=mu_PHI(D);

disp(sprintf(‘koherensi kamus-basis = %f\n’, mu));

%Tentukan batas sparsity

N_sparse=floor(0.5*(1+1/mu));

disp(sprintf(‘batas sparsity = %d’, N_sparse));

% === fungsi yang dipakai ===

%fungsi menghitung koherensi kamus basis

function [mu]=mu_PHI(PHI);

[M,N]=size(PHI);

CORR=transpose(conj(PHI))*PHI;

mu=max(max(CORR));

Hasil running program Matlab diatas menghasilkan nilai koherensi $\mu \sim 0.094$ dan batas sparsity sebesar 5. Dengan demikian, sebarang sinyal sepanjang 64 cuplikan yang terbentuk dari kombinasi linier kamus basis berukuran 64×1024 akan dapat ditemukan dengan optimasi P₁ atau algoritma Basis Pursuit.

Referensi

M.Elad and A.M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of bases”, IEEE Trans. on Information Theory, Vol. 48, pp. 2558-2567, September 2002.
D. L. Donoho and M. Elad, “Maximal sparsity representation via l1 minimization”, Proc. of the National Academy of Science, Vol. 100, pp. 2197-2202, March 2003.
S.S. Chen, D. Donoho, and MA Saunders, ”Atomic decomposition by basis pursuit,” SIAM J. on Scientific Computing, 20(1):33-61, 1999.

Posted in Compressive Sensing, Signal Decomposition and Search of Basis, Theory and Concept, Uncategorized | Leave a Comment »

Dekomposisi Sinyal dan Pencarian Basis Ideal (2)

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.

Posted in Compressive Sensing, Signal Decomposition and Search of Basis, Theory and Concept, Uncategorized | 3 Comments »

Dekomposisi Sinyal dan Pencarian Basis Ideal (1)

Posted by suksmono on May 14, 2008

Pemanfaatan transformasi ortogonal untuk kompresi sinyal telah ditunjukkan pada tulisan sebelumnya. Secara intuitif dapat difahami bahwa sistem kompresi menghendaki terkumpulnya energi di kawasan transformasi hanya ke sejumlah kecil koefisien supaya tingkat kompresi nya tinggi dengan kualitas hasil rekonstruksi yang terjaga. Namun demikian hal ini tidak selalu bisa dilakukan karena bagaimanapun setiap sistem basis hanya cocok untuk segolongan sinyal-sinyal tertentu saja. Basis sinusoid dalam transformasi Fourier atau DCT melakukan pengkompakan energi dengan baik jika sinyal asalnya tersebar di kawasan waktu. Sebaliknya, sinyal yang terlokalisir dalam kawasan ini sebaiknya memakai basis impuls atau wavelet.

Gambar 1. Beberapa vektor basis impuls

Gambar 2. Beberapa vektor basis DCT

Gambar diatas memperlihatkan beberapa vektor basis dari sistem basis impuls $\Phi$ dan sistem basis DCT $\Psi$ . Sifat lokalisasi sinyal terlihat dengan jelas pada kedua gambar; basis impuls terlokalisir sedangkan DCT tersebar. Program Matlab berikut dapat dipakai untuk menampilkan vektor-vektor basis seperti diatas.

%———————————————–

% Sistem Basis Impuls dan DCT

%———————————————–

N=64; %dimensi vektor basis

x=1:N; %buat sumbu x

PHI=eye(N,N); %Basis Impulse

PSI=dct(eye(N,N)); %Basis DCT

figure(1);plot(x,PHI(2,:),x,1+PHI(4,:),x,2+PHI(8,:),…

x,3+PHI(16,:),x,4+PHI(32,:),x,5+PHI(60,:));

title(‘Vektor basis impuls’);

figure(2);plot(x,PSI(2,:),x,0.5+PSI(4,:),x,1+PSI(8,:), …

x,1.5+PSI(16,:),x,2+PSI(32,:),x,2.5+PSI(60,:));

title(‘Vektor basis DCT’);

Suatu sinyal biasanya merupakan campuran dari komponen yang terlokalisir dan yang tersebar. Basis mana yang harus dipilih dalam kasus yang demikian? Tinjau suatu sinyal s(n) yang terbentuk dari sistem basis $\Phi$ berupa vektor basis ke-4 dan ke-32 dan dua buah lainnya dari sistem basis $\Psi$ , yaitu vektor basis ke-8 dan ke-60. Prinsip kompresi sederhana yang sudah dijelaskan dapat dicobakan untuk setiap sistem basis, yaitu dengan mengalikan matriks transformasi-nya dengan vektor s(n),

Dekomposisi sinyal ke basis impuls: ${S}_{1}= \Phi .s$

Dekomposisi sinyal ke basis DCT: ${S}_{2}=\Psi.s$

Langkah berikutnya, ambil beberapa koefisien dengan energi (magnitudo) terbesar. Tentu cara lain dapat dilakukan, misalnya tresholding dengan mencari koefisien-koefisien yang energi/magnitudo-nya berada diatas ambang nilai tertentu. Untuk indeks dari koefisien $k \in K & vektor basis terpilih, rekonstruksi dilakukan dengan cara menjumlahkan vektor dari basis yang telah diboboti, yaitu: Rekonstruksi dengan basis impuls:$ latex {\hat{s}}_{1}(n)=\sum_{k \in K}{S}_{1}(k) \Phi(k) &s=-2 $

Rekonstruksi dengan basis DCT: ${\hat{s}}_{2}(n)=\sum_{k \in K}{S}_{s}(k) \Psi(k)$

Kinerja dari rekonstruksi sinyal dapat dilihat dari energi sinyal kesalahan (error) rata-rata atau RMSE (Root Mean Square Error) masing-masing, yang dinyatakan sebagai:

$RMSE=\frac{1}{N}\sqrt{\sum_{n=0}^{N-1}{e(n)}^{2}}$ , dimana $e(n)=s(n)-\hat{s}(n)$

Semakin kecil nilai ini, maka secara obyektif hasil rekonstruksi semakin baik. Nilai RMSE yang besar menandakan terjadinya distorsi signifikan pada sinyal.

Gambar 3. Sinyal asli s(n)

Gambar 4. Magnitudo koefisien terurut

Gambar 3 menunjukkan sinyal asal s(n) berupa gabungan dua sinusoid dan dua sinyal impuls. Sinyal ini akan didekomposisi dengan basis impuls dan kemudian dengan basis DCT. Dekomposisii sinyal ini kedalam sistem basis tersebut akan menghasilkan koefisien yang dinyatakan sebagai vektor S₁ dan S₂. Untuk mengamati sebaran energi, magnitudo atau nilai mutlak S₁ dan S₂ diurutkan dan kemudian dibuatkan kurvanya. Kedua kurva diberikan pada Gambar 4. Terlihat bahwa, meskipun beberapa koefisien awal dominan, penurunan nilai energi koefisien lainnya tidaklah terlalu tajam. Dengan demikian, pengambilan sejumlah kecil komponen dominan akan tetap menghasilkan sinyal kesalahan yang cukup tinggi energinya. Ini artinya rekonstruksi sinyal kurang berhasil.

Gambar 5. Perbandingan sinyal asli dengan hasil rekonstruksi

Gambar 6. Sinyal kesalahan

Gambar 5 memperlihatkan hasil rekonstruksi dengan menggunakan delapan buah vektor basis. Kurva biru merupakan hasil dari basis impuls, sedangkan kurva merah dari basis DCT. Perbandingan dengan sinyal asli yang dinyatakan sebagai titik-titik berwarna hitam memperlihatkan beda yang cukup signifikan. Perbedaan ini semakin jelas setelah sinyal kesalahan e₁(n) dan e₂(n) diperlihatkan pada Gambar 6.

Gambar 7 Kinerja RMSE

Kinerja rekonstruksi dapat dievaluasi dengan mengukur RMSE berbagai jumlah vektor basis seperti yang diperlihatkan pada Gambar 7. Penurunan RMSE terjadi secara perlahan dan mencapai nol ketika seluruh N vektor basis diikutsertakan; yang artinya tidak ada kompresi. Program Matlab berikut dapat dipergunakan untuk menunjukkan proses proyeksi dan rekonstruksi diatas.

% Pencarian basis

clear;%close all;clc;

N=64; %dimensi vektor basis

x=1:N; %buat sumbu x

PHI=eye(N,N); %Basis Impulse

PSI=dct(eye(N,N)); %Basis DCT

%bentuk sinyal dari basis DCT saja

s1=zeros(N,1);s1=zeros(N,1);

s1=(PHI(4,:)+PHI(32,:))’;

s2=(PSI(8,:)+PSI(60,:))’;

s=zeros(N,1); s=s1+s2;

figure(1);plot(x,s); title(’sinyal kombinasi impuls dan DCT’);

xlabel(‘n’);ylabel(’s(n)’);

S1=PHI*s; S2=PSI*s; %cari koefisien

%urutkan koefisien dan ambil dua terbesar

[S1_oval,S1_oidx]= sort(abs(S1),’descend’);

[S2_oval,S2_oidx]= sort(abs(S2),’descend’);

% rekonstruksi sinyal

s_hat1=zeros(N,1); s_hat2=zeros(N,1);

for k=1:8; s_hat1=s_hat1+(S1(S1_oidx(k))*PHI(S1_oidx(k),:))’; end;

for k=1:8; s_hat2=s_hat2+(S2(S2_oidx(k))*PSI(S2_oidx(k),:))’; end;

%hitung kesalahan

e1=s-s_hat1;e_rms1=sqrt(e1′*e1)/N;

disp(sprintf(‘rms error-Impulse %f’,e_rms1));

e2=s-s_hat2;e_rms2=sqrt(e2′*e2)/N;d

isp(sprintf(‘rms error-DCT %f’,e_rms2));

figure(2); plot(x,S1_oval,’r-’, x,S2_oval,’b-’);

title(‘magnitudo koefisien terurut’);

xlabel(‘index’);ylabel(‘|S|-terurut’);

legend(‘proyeksi Impuls’,'proyeksi DCT’);

figure(3);plot(x,s,’k.’,x,s_hat1,’b:’,x,s_hat2,’r-’);

title(‘perbandingan hasil rekonstruksi’);

xlabel(‘n’);ylabel(’s(n)’); legend(‘asli’,'rek. impuls’,'rek. DCT’);

figure(4);plot(x,e1,’r-’,x,e2,’b–’);title(’sinyal kesalahan’);

xlabel(‘n’);ylabel(‘e(n)’);

legend(’sinyal error impulse’,’sinyal error DCT’);

%data error beberapa nilai k

x_e=[2 4 8 16 32 64]‘;

e_PHI=[2.18e-2 2.05e-2 1.78e-2 1.33e-2 5.94e-3 0.0]‘;

e_PSI=[2.16e-2 2.02e-2 1.77e-2 1.32e-2 6.28e-3 0.0]‘;

figure(5);plot(x_e,e_PHI,’r-’,x_e,e_PSI,’b-’); title(‘kinerja RMSE pengkodean’);

xlabel(‘jumlah koefisien’);ylabel(‘RMS Error’); legend(‘Impulse’,'DCT’);

Melihat hasil yang kurang baik saat menggunakan satu buah basis ortogonal saja, apakah mungkin kinerja-nya meningkat seandainya dua atau lebih sistem basis digabungkan? Memang cara inilah yang paling masuk akal, akan tetapi cara ini menimbulkan satu masalah besar lainnya. Gabungan kedua basis akan menghasilkan suatu basis baru yang dimensinya menjadi Nx2N. Dilihat dari sistem persamaan linier, permasalahan menjadi lebih sulit dipecahkan karena kita harus mencari solusi dari N buah persamaan dengan 2N peubah yang tak diketahui . Sistem persamaan linier yang demikian disebut sebagai underdetermined.

Sebagai ilustrasi, tinjau suatu matriks transformasi A berukuran 2×2 yang bisa dianggap sebagai transformasi vektor pada bidang atau transformasi sinyal 2 cuplikan x=[x₁ x₂] menjadi y=[y₁ y₂]. Pencarian koefisien transformasi x(n) yang tepat dari sinyal teramati y(n) dapat dinyatakan sebagai persamaan matriks: Ax=y dengan x tak diketahui atau

$\begin{pmatrix}{a}_{11} & {a}_{12} \\ {a}_{21} & {a}_{22} \end{pmatrix}\begin{pmatrix}{x}_{1}\\ {x}_{2} \end{pmatrix}= \begin{pmatrix} {y}_{1} \\ {y}_{2}\end{pmatrix}$

Bentuk sistem persamaan liniernya adalah

${a}_{11}{x}_{1}+{a}_{12}{x}_{2}={y}_{1}$

${a}_{21}{x}_{1}+{a}_{22}{x}_{2}={y}_{2}$

Karena yang tak-diketahui ada dua {x₁, x₂} dan ada dua persamaan, jika matriks A tak-singular tau memiliki inverse, maka sistem persamaan linier diatas dapat dipecahkan dengan eliminasi Gauss atau mengalikan inverse A dengan vektor [y₁ y₂ ]^T dari kiri.

Sebaliknya, penggabungan sistem basis A dengan basis baru B menjadi D=[A;B] akan membuat persamaan matriks diatas menjadi

$\begin{pmatrix}{a}_{11} & {a}_{12} & {b}_{11} & {b}_{12} \\ {a}_{21} & {a}_{22} & {a}_{21} & {a}_{22} \end{pmatrix} \begin{pmatrix}{x}_{1}\\ {x}_{2}\\ {x}_{3}\\{x}_{4} \end{pmatrix}=\begin{pmatrix} {y}_{1}\\ {y}_{2} \end{pmatrix}$

Atau dinyatakan sebagai sistem persamaan linier berikut:

${a}_{11}{x}_{1}+{a}_{12}{x}_{2}+{b}_{11}{x}_{3}+{b}_{12}{x}_{4}={y}_{1}$

${a}_{21}{x}_{1}+{a}_{22}{x}_{2}+{b}_{21}{x}_{3}+{b}_{22}{x}_{4}={y}_{2}$

Sistem persamaan linier ini terdiri dari empat buah variabel, yaitu {x₁, x₂, x₃, x₄} sedangkan jumlah persamaan hanya ada dua. Karena masing-masing sistem basis bersifat lengkap, akan ada banyak sekali kombinasi yang dapat muncul untuk menyatakan suatu vektor y. Pencarian basis ke seluruh ruang solusi memerlukan sumberdaya komputasi yang sangat besar karena termasuk permasalahan kombinatorial. Bagaimana cara mengatasinya?

Posted in Compressive Sensing, Signal Decomposition and Search of Basis, Theory and Concept, Uncategorized | Leave a Comment »

Chaotic Pearls

Lamunan dari seberang GKU lama …

Meta

Blogroll

Students

Categories

Recent Posts

Top Posts

Archive for the ‘Signal Decomposition and Search of Basis’ Category

Dekomposisi Sinyal dan Pencarian Basis Ideal (4)

Dekomposisi Sinyal dan Pencarian Basis Ideal (3)

Dekomposisi Sinyal dan Pencarian Basis Ideal (2)

Dekomposisi Sinyal dan Pencarian Basis Ideal (1)