NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCAN PADA ESTIMASI ARAH KEDATANGAN SINYAL BERBASIS REKONSTRUKSI SPARSE
LAPORAN KEMAJUAN 3
Oleh
KOREDIANTO USMAN NIM: 33213002 (Program Studi Teknik Elektro dan Informatika)
INSTITUT TEKNOLOGI BANDUNG Desember 2015
NON-EXHAUSTIVE SEARCH DENGAN TAIL-SCAN PADA ESTIMASI ARAH KEDATANGAN SINYAL BERBASIS REKONSTRUKSI SPARSE
Oleh Koredianto Usman NIM: 33213002 (Program Studi Teknik Elektro dan Informatika) Institut Teknologi Bandung
Menyetujui Tim Pembimbing Tanggal : 10 Desember 2015
Ketua,
(Prof. Andriyan Bayu Suksmono, Ph.D)
Anggota,
(Prof. Hendra Gunawan, Ph.D)
i
ABSTRAK
Estimasi arah kedatangan sinyal adalah teknik estimasi sudut kedatangan objek yang dideteksi dengan peralatan radar atau sonar. Teknik klasik untuk estimasi arah kedatangan antara lain adalah MVDR, MUSIC, dan ESPRIT. Peran dari Compressive Sensing (CS) adalah pengurangan jumlah sampel akuisisi pada sisi penerima. Pengurangan ini memberi dampak pada kecilnya data rate, sehingga dimungkinkan membangun sistem radar terdistribusi yang saling mengirimkan data untuk memantau daerah yang luas. Teknik terkini dalam estimasi arah kedatangan sinyal dengan compressive sensing adalah dengan metoda sparsitas sudut. Teknik ini mengasumsikan sinyal datang berasal dari beberapa sumber berbeda yang berjumlah terbatas. Teknik yang telah dikembangkan peneliti untuk skema ini adalah dengan menggunakan sensing matrix A yang tersusun atas steering vector yang berasal dari semua sudut yang dipindai (-900 sampai 900 ). Teknik pindai pada semua sudut ini disebut sebagai exhaustive search. Teknik exhaustive search ini memiliki permasalahan pada besarnya matrik sensing A, sehingga proses rekonstruksi CS menjadi berat. Kemungkinan pemindaian pada rentang sudut yang lebih kecil (non-exhaustive search), yaitu pada sudut-sudut yang diduga mengandung sumber sinyal diusulkan pada penelitian ini. Pengujian yang dilakukan pada penelitian ini menunjukkan bahwa teknik ini memiliki tingkat keberhasilan yang baik. Masih terdapat masalah tambahan yang harus diselesaikan pada teknik non-exhaustive search yaitu rekonstruksi CS tidak konvergen jika rentang sudut pindai terlalu sempit. Penambahan pemindaian di luar area pemindaian utama (tail-scan) untuk mengatasi masalah ini juga dilakukan pada laporan ini. Di samping penelitian pada teknik tail-scan, pada Kemajuan Tahap 3 ini juga dilakukan teknik alternatif penyelesaian permasalahan rekonstruksi CS dengan algoritma baru yang disebut dengan metode titik berat. Teknik metode titik berat ini juga dibahas dalam laporan ini. Kata kunci : compressive sensing, estimasi arah kedatangan sinyal, sparsitas, exhaustive search, non-exhaustive search, tail scan.
ii
DAFTAR ISI ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BAB I Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 State of The Art . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3 Premis dan Hipotesis . . . . . . . . . . . . . . . . . . . . . . . . I.4 Perbandingan Kemajuan 3 dengan Kemajuan sebelumnya . . . . I.5 Publikasi terkait . . . . . . . . . . . . . . . . . . . . . . . . . . . I.6 Kontribusi dan Kebaruan . . . . . . . . . . . . . . . . . . . . . . BAB II Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II.1 Model matematis sistem . . . . . . . . . . . . . . . . . . . . . . . II.2 Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . . . . II.3 Compressive sensing pada estimasi DoA . . . . . . . . . . . . . . II.4 CS solver dengan CVX Programming . . . . . . . . . . . . . . . BAB III Metode yang diusulkan . . . . . . . . . . . . . . . . . . . . . . . . . . III.1 Teknik Non-Exhaustive Search . . . . . . . . . . . . . . . . . . . III.2 Teknik Tail-scan . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3 Metode Titik Berat . . . . . . . . . . . . . . . . . . . . . . . . . BAB IV Hasil kemajuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.1 Hal yang telah dilakukan pada semester berjalan . . . . . . . . . IV.1.1 Hasil simulasi teknik non-exhaustive search dengan tail scan IV.2 Perbandingan akurasi regular dan random tail-scan tanpa interpolasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.3 Perbandingan akurasi regular dan random tail-scan dengan interpolasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV.4 Perbandingan kegagalan konvergensi pada tail-scan . . . . . . . . IV.5 Perbandingan waktu komputasi pada skema tail-scan . . . . . . . BAB V Penutup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BAB Lampiran A : Faktorisasi QR . . . . . . . . . . . . . . . . . . . . . . . 1 Faktorisasi QR untuk Over determined system . . . . . . . . . . BAB Penyelesaian Persamaan Underdetermined dengan faktorisai QR . . . 2 QR Faktorisasi dengan Transformasi Householder . . . . . . . . . 2.1 Prinsip: Membuat elemen nol pada vektor . . . . . . . . . 2.2 Pemaktoran Matrik ke komponen Q dan R . . . . . . . . 2.3 Contoh Ilustrasi . . . . . . . . . . . . . . . . . . . . . . . 2.4 QR dekomposisi dengan Column Pivoting . . . . . . . . . 2.5 Penyelesaian masalah sistem persamaan linier Underdetermined . . . . . . . . . . . . . . . . . . . . . . .
iii
ii iii v vi 1 1 3 4 5 7 7 8 8 9 11 14 15 15 17 20 28 28 28 29 30 30 31 32 33 36 38 40 42 42 46 48 50 52
DAFTAR GAMBAR
I.1 I.2 II.1 II.2
Perbandingan pekerjaan penelitian yang dilakukan pada Seminar Kemajuan I, II, dan III. . . . . . . . . . . . . . . . . . . . . . . . . . . Publikasi yang telah dilakukan dan yang direncanakan . . . . . . . . Antennas arrangement in ULA with distance d between element . . . Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steering vector sudut-sudut yang dipindai . . . . . . . . . . . . . . . . . . . .
III.1 Ilustrasi exhaustive search. Algoritma memindai pada semua arah untuk memperoleh arah sumber sinyal . . . . . . . . . . . . . . . . . . III.2 Blok diagram skema non-exhaustive search dengan fungsi pemindaian kasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.3 Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudut dalam koordinat polar (b). dalam koordinat kartesian . . . . . . . . . III.4 Ilustrasi tracking object dengan teknik non-exhaustive search serta update scanning window pada setiap waktu. (a),(b), dan (c) pergerakan objek beserta update scanning window yang bersesuaian. (d). ilustrasi pergeseran scanning window pada setiap waktu; W1, W2, W3 adalah scanning window berturut-turut pada t1, t2 dan t3 . . . . III.5 Ilustrasi detail tentang proses update scanning window dengan menggunakan median dari posisi objek. (a) hasil scanning kasar dengan algoritma klasik pada semua sudut,(b) penerapan scanning window pada sudut yang dianggap memiliki objek, (c) objek bergerak sehingga puncak scanning bergeser menuju batas window. (d). update scanning window, sehingga puncak scanning berada di tengah scanning window . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.6 Hasil simulasi: perbandingan skema exhaustive search terhadap . . . . III.7 Non-exhaustive search dengan tail-scan . . . . . . . . . . . . . . . . . III.8 Non exhaustive search dengan tail scan. (a) uniform tail scan, (b) random tail scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.9 Solusi persamaan Ax=y terletak pada garis (A). Solusi dari Norm-L1 (B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.10 (a). Iterasi awal dengan k0 yang cukup besar sehingga kurva Ax = y dan kxk1 = k0 berpotongan di P1 dan P2 . Titik tengah M1 dipilih sebagai iterasi berikutnya. (b). Norm di M1 dipilih sebagai nilai k berikutnya. Proses ini diulangi sehingga diperoleh titik yang konvergen. III.11 (a). Kasus dimensi 3, kxk1 = k0 membentuk oktahedron. Solusi dari Ax = y dengan matrik A 1x3 adalah suatu bidang. Jika k0 cukup besar, kxk1 = k0 akan memotong Ax = y. (b). Bidang perpotongan dengan titik sudut P1 sampai P5 . Titik M1 dipilih sebagai kombinasi konveks dari titik-titik P1 sampai P5 . . . . . . . . . . . . . . . . . . .
iv
6 7 8 13 15 16 17
18
19 20 20 21 21
22
23
DAFTAR GAMBAR III.12 Faktorisasi QR Householder dengan pivot kolom (a). Pivot kolom dengan urutan L2 -norm dari yang terbesar ke yang terkecil (b). Pivot kolom dengan urutan L2 -norm dari yang terkecil ke yang terbesar . . III.13 Perpotongan antara oktahedron norm L1 dengan solusi dari fungsi objektif yang berupa garis. Titik potong bidang dan garis dinotasikan dengan P1 dan P 2. Titik M1 yang merupakan kombinasi konveks dari P1 dan P 2 diilustrasikan pada gambar kanan . . . . . . . . . . . . . . 1
Tahap pengubahan suatu matrik X sebarang ke matrik segitiga atas .
v
25
26 46
DAFTAR TABEL
I.1 I.2
Perbandingan Referensi State of The Art . . . . . . . . . . . . . . . . . Premis dan Hipotesis yang dirumuskan dalam penelitian . . . . . . . .
4 5
IV.1 Parameter simulasi exhaustive dan non exhaustive search . . . . . . . .
28
vi
BAB I Pendahuluan I.1 Latar Belakang Teknik compressive sensing untuk estimasi arah kedatangan sinyal memperoleh perhatian yang besar pada dekade saat ini. Meski pun CS mulai dianggap sebagai bidang ilmu yang cukup matang pada pertengahan tahun 2000an (Donoho (2006), Candes dan Wakin (2008), Baraniuk (2007)), teknik yang mendasarinya telah berkembang lebih dahulu, seperti matching pursuit (Mallat dan Zhang (1993)), basis pursuit Chen dkk. (2001), algoritma greedy (Tropp (2004)) maupun wavelet. Penerapan teknik CS telah dilakukan pada berbagai bidang, antara lain: kompresi data (Candes dan Wakin (2008), Wahidah dan Suksmono (2010)), channel coding (Candes dan Wakin (2008)), MRI imaging (Swastika dan Haneishi (2012)), wireless channel estimation (Hayasi dkk. (2013)). Saat ini, teknik CS telah pula diterapkan pada bidang radar. Secara umum radar memiliki tiga fungsi, yaitu: estimasi arah kedatangan, estimasi jarak, dan estimasi kecepatan. Pada bidang estimasi arah kedatangan sinyal, teknik Compressive Sening ditujukan untuk mengurangi jumlah sampel yang harus diakuisisi oleh penerima. Jumlah sampel yang sedikit akan memberikan keuntungan pada kebutuhan bandwidth telekomunikasi yang rendah. Dengan demikian, skema distributed radar system dapat diimplementasikan lebih mudah untuk menjangkau wilayah yang luas. Secara perkembangan, teknik estimasi arah kedatangan sinyal sendiri telah berkembang sejak era analog, sampai dengan era digital. Pada era digital, teknik estimasi arah kedatangan sinyal dipelopori antara lain oleh algoritma Capon atau MVDR (Dmochowski dkk. (2007)). Dengan memanfaatkan kovariansi matrik sinyal penerima, serta steering vector pada arayh yang dipindai, algoritma ini berhasil memperoleh estimasi arah kedatangan sinyal dengan spektrum puncak yang cukup tajam. Schmidt melakukan terobosan pada bidang estimasi DoA ini dengan mengusulkan algoritma MUSIC (Multiple Signal Classification, Schmidt (1986)). Algoritma ini membuka dimensi baru dengan penggunaan teknik sub-space yang berasal dari dekomposisi nilai eigen dari matrik kovariansi. Roy dkk. (1986) juga menggunakan teknik sub-space untuk melakukan estimasi arah kedatangan sinyal. Teknik ini berbeda dengan MUSIC karena teknik ini tidak melakukan estimasi arah kedatangan sinyal dengan memindai semua arah, namun ia memanfaatkan struktur dari susunan antena penerima. Estimasi arah kedatangan diperoleh dengan manipulasi matematis dari susunan ini. Teknik ini populer dengan istilah ESPRIT (Estimation
1
of Signal Parameters via Rotational Invariant Techniques). Veen dan Buckley (1988) mengajukan skema yang sederhana dibandingkan dengan MUSIC dan ESPRIT, yaitu skema delay and sum (DAS). Skema ini memiliki prinsip estimasi arah kedatangan dengan mendelay fasa dengan suatu mekanisme pada setiap elemen antena. Pada nilai fasa tertentu, diperoleh sinyal terima terkuat. Sudut yang berkorespondensi dengan delay tersebut diambil sebagai estimasi arah kedatangan sinyal. Teknik klasik pada umumnya bersandar pada teorema sampling klasik Shannon-Nyquist dalam mengakuisisi data. Akuisisi data dilakukan dengan kecepatan sampling sekurang-kurangnya dua kali frekuensi tertinggi sinyal informasi. Akibat dari adanya skema akuisisi ini, data yang diolah oleh algoritma klasik adalah sangat besar. Teknik distributed radar system yang bersandar pada komunikasi antar unit (seperti wireless sensor network) akan memiliki masalah jika harus mentransmisikan data besar setiap saat. Oleh karena itu teknik CS untuk DoA sangat diperlukan pada kondisi tersebut. Secara umum, terdapat tiga kategori besar dalam pemanfaatan compressive sensing untuk estimasi arah kedatangan sinyal: skema sparsitas waktu, skema sparsitas ruang, dan skema sparsitas sudut. Sparsitas waktu mengambil asumsi bahwa sinyal yang diterima sensor bersifat sparse secara sampel per sampel. Mengambil asumsi ini, maka pengurangan sampel dilakukan dalam ranah waktu. Penelitian yang memanfaatkan skema ini antara lain adalah Wang dkk. (2009). Di sisi lain, skema sparsitas ruang mengambil asumsi bahwa sinyal yang diterima suatu sensor adalah sama dengan sinyal yang diterima oleh sensor yang lain dengan perbedaan pada fasa. Dengan asumsi ini, maka jumlah sensor dapat dikurangi sampai menjadi sebanyak sinyal yang diterima. Pengurangan jumlah sensor berarti juga mengurangi jumlah sampel yang diterima. Penelitian yang memanfaatkan skema ini antara lain adalah Gurbuz dan McClellan (2008), dan Jouny (2011). Skema sparsitas sudut mengambil asumsi bahwa sinyal yang datang hanya pada sudut-sudut tertentu. Dengan asumsi ini, maka algoritma estimasi arah kedatangan dilakukan dengan mencari spektral tak nol pada matrik sinyal penerima yang disusun terdiri dari semua sudut arah kedatangan yang dipindai. Penelitian yang menggunakan skema ini antara lain adalah Gorodnitsky dan Rao (1997) dan Stoica dkk. (2011). Skema sparsitas sudut memiliki keuntungan utama dari pada skema sparsitas waktu dan sparsitas sensor yaitu pada jumlah sampel yang sedikit. Penelitian Gorodnitsky dan Rao (1997) mengusulkan penggunaan satu sampel untuk estimasi arah kedatangan. Untuk keperluan rekonstruksi, Gorodnitsky dan Rao menggunakan algoritma Focal Underdetermined System Solver (FOCUSS). Dalam lingkungan dengan derau yang rendah, hasil estimasi arah kedatangan yang dilaporkan oleh Gorodnitsky dan Rao tersebut memiliki resolusi yang tajam. Meski keuntungan ini, algoritma FOCUSS
2
yang ditawarkan mengalami masalah pada lingkungan dengan derau tinggi (Usman dkk. (2014)). Teknik multi sampel yang dilakukan oleh Stoica dkk. (2011) memperbaiki performa yang lebih baik, namun proses komputasi yang lebih tinggi. Proses komputasi yang lebih tinggi ini disebabkan antara lain oleh jumlah sampel yang lebih banyak dan basis perhitungan pada bilangan kompleks. Permasalahan yang juga perlu diatasi pada skema sparsitas sudut adalah pemindaian yang dilakukan pada semua arah menyebabkan sensing matrix A memiliki dimensi yang sangat besar. Hal ini menyebabkan proses rekonstruksi CS berjalan lambat. Penelitian yang dilakukan ini adalah untuk menjawab permasalahan tersebut.
I.2 State of The Art Pada bagian ini, dipilih tiga referensi yang dijadikan sebagai state of the art. Pemilihan tiga referensi ini dikarenakan karena ketiga referensi ini adalah referensi langsung yang terkait pada upaya penyelesaian masalah yang diusulkan. Ketiga referensi ini adalah Gorodnitsky dan Rao (1997), Stoica dkk. (2011), dan Dai dkk. (2013). Detail dari ketiga referensi tersebut adalah sebagai berikut : 1. Gorodnitsky dan Rao (1997): Sparse Signal Reconstruction form Limited data Using FOCUSS: a re-weighted minimum norm algorithm, Publikasi : IEEE Transaction on Signal Processing, Vol. 45, No.3 (Referensi #1) 2. Stoica, Babu, dan Li (2011): SPICE: A sparse covariance-based estimation method for array processing, Publikasi : IEEE Transaction of Signal Processing, Vol.59, No.2 (Referensi #2) 3. Dai, Xu, dan Zhao (2013): Direction-of-Arrival Estimation Via Real-Valued Sparse Representation, Publikasi : IEEE Antennas and Wireless Propagation Letters (Referensi #3) Referensi #1 menjadi referensi utama dari skema sparsitas sudut. Sejauh yang penulis teliti, Referensi #1 dapat dianggap sebagai karya seminal dari teknik sparsitas sudut. Hal yang menarik dikaji adalah bahwa teknik ini dapat bekerja dengan menggunakan satu sampel sinyal saja. Referensi #2 membahas tentang teknik rekonstruksi dengan metode covariance-based. Teknik ini memperbaiki hasil dari Referensi #1 dalam hal ketahanan dalam lingkungan derau tinggi. Teknik ini mengakomodasi penggunaan multi sampel. Referensi #3 membahas tentang teknik penyederhaan perhitungan rekonstruksi compressive sensing dengan cara mengubah nilai-nilai kompleks menjadi nilai-nilai riil. Pengubahan ini diklaim oleh para penulisnya dapat mempercepat komputasi menjadi 4 kali. Dalam kerangka tiga
3
referensi ini penelitian ini dilakukan dan dikembangkan. Tabel I.1 memperlihatkan perbandingan tekniks dari ketiga referensi ini. Tabel I.1. Perbandingan Referensi State of The Art Perihal Aplikasi
Tujuan
Skema
Referensi #1 Estimasi arah kedatangan sinyal dengan algoritma FOCUSS Menunjukkan bahwa teknik CS dengan satu sampel dapat menghasilkan estimasi arah yang baik dan resolusi tinggi Jumlah sumber : 3 (pada sudut -44, -33, 56); Jumlah sensor : 8; Jumlah sampel 1 ; Algoritma Inisialisasi MVDR
Kekurangan Tidak robust pada lingkungan dengan derau tinggi
Kelebihan
Hanya menggunakan satu sampel, sangat efisien bandwidth jika ditransmisikan
Referensi #2 Estimasi arah kedatangan sinyal dengan algoritma SPICE Teknik estimasi arah kedatangan beberapa sampel sekaligus
Jumlah sumber : 3 (pada sudut 10, 40 dan 55 derajat); Jumlah sensor : 10 ; Jumlah sample : 200 ; Algoritma inisialisasi SPICE Kompleksitas tinggi karena melakukan exhaustive search pada semua arah
Mengakomodasi multi-sample sehingga lebih robust pada lingkungan dengan derau tinggi
Referensi #3 Estimasi arah kedatangan dengan compressive sensing dengan nilai riil Mempercepat perhitungan compressive sensing dengan transformasi unitary untuk memperoleh nilai matrik riil 2 sumber (pada sudut -2.5 dan 3.5 derajat) ; Jumlah sensor : 10 ; Jumlah sampel : 100 ; Algoritma inisialisasi : MUSIC kompleksitas tinggi: teknik Singular Value Decomposition (SVD) diterapkan pada matrik besar serta perhitungan dekomposisi memerlukan waktu yang besar komputasi yang lebih ringan dibandingkan
I.3 Premis dan Hipotesis Pada Kemajuan I telah disampaikan premis yang mendasari penelitian ini, yaitu : 1). Skema sparsitas sudut memiliki kelemahan pada lingkungan dengan derau tinggi, 2). Skema sparsitas sudut memiliki kompleksitas rekonstruksi yang tinggi. Kedua premis tersebut telah dibuktikan dengan simulasi komputer yang dilakukan. Hasil pembuktian tersebut telah dipublikasikan sebagai publikasi awal dari penelitian ini (Usman dkk. (2014)).
4
Pada Kemajuan II dilakukan simulasi lanjutan yaitu perbaikan skema yang ada dengan teknik non-exhaustive search. Dari percobaan-percobaan yang dilakukan, maka diperoleh premis-premis lanjutan, yaitu: 3). Skema sparsitas sudut dapat bekerja dengan sudut pindai yang lebih sempit (non-exhaustive search). Pada Kemajuan III ini, dilakukan percobaan yang lebih intensif pada teknik tail-scan serta pengembangan teknik rekonstruksi CS dengan dengan teknik titik berat (weight point) untuk memperoleh solusi yang dijamin kekonvergenannya. Premis-premis yang diajukan untuk tahap ini adalah: 4). teknik tail-scan memiliki kinerja yang lebih baik dari pada tanpa tail-scan, 5). Tail-scan uniform secara statistik memiliki kinerja yang lebih baik dari pada tail-scan random, 6). Rekonstruksi CS dengan menggunakan titik berat dari bidang perpotongan norm L1 dan fungsi objektif memberikan solusi CS yang dijamin kekonvergenannya. Tabel I.2. Premis dan Hipotesis yang dirumuskan dalam penelitian Premis Skema sparsitas sudut memiliki akurasi yang buruk pada lingkungan derau tinggi Skema sparsitas sudut memiliki kompleksitas rekonstruksi yang tinggi Metode teknik scanning non-exhaustive memiliki permasalahan pada konvergensi, khususnya jika menggunakan teknik rekonstruksi CS dengan pemrograman convex Teknik pemrograman convex yang berdasarkan metode interior point method dan iterasi Newton menimbulkan permasalahan pada nilai awal yang dapat menyebabkan ketidakkonvergenan
Hipotesis Akurasi pada lingkungan derau tinggi dapat ditingkatkan dengan teknik yang mengolah beberapa sampel sekaligus Pengurangan kompleksitas dapat dilakukan dengan pra-pemindaian dan pemindaian pada arah tertentu saja non-exhaustive search Perbaikan dilakukan dengan memberikan scanning tambahan di luar arah utama atau tail-scan untuk memberikan basis scanning pada semua arah agar konvergensi dapat dijamin Penggunakaan metode titik berat dapat memperbaiki masalah kekonvergenan tersebut
I.4 Perbandingan Kemajuan 3 dengan Kemajuan sebelumnya Pada Kemajuan I, penelitian diarahkan pada teknik sparsitas sudut yang dipelopori oleh Goronitsky dan Rao Gorodnitsky dan Rao (1997). Perbaikan dilakukan dengan menggunakan teknik transformasi unitary untuk mempercepat proses perhitungan dari
5
algoritma tersebut. Pada Kemajuan I ini, belum dilakukan upaya untuk mempercepat perhitungan dengan mengurangi lebar sudut pindai. Pengurangan lebar sudut pindai dilakukan pada Kemajuan II. Proses yang dilakukan adalah memindai pada semua sudut untuk memperoleh arah kedatangan sinyal, setelah itu, pada proses berikutnya (proses update), pemindaian dilakukan pada arah tertentu saja (non-exhaustive search) pada arah yang diidentifikasi terdapat objek. Pada Kemajuan III permasalahan ketidakkonvergenan diatasi dengan dua cara yaitu dengan teknik tail-scan (uniform dan random) dan dengan teknik rekonstruksi CS baru yang dikembangkan sendiri menggunakan metode titik berat dari bidang perpotongan norm L1 dan fungsi objektif rekonstruksi. Penggunaan metoda titik berat ini dilakukan sebagai alternatif dari metoda iterasi Newton dengan kelebihan pada jaminan konvergensi. Gambar I.1 memperlihatkan skema penelitian yang dilakukan pada setiap kemajuan ini. Direction of Arrival Estimation
Classical
Compressive Sensing
Time Sparsity
Spatial Sparsity
SK I
Angle Sparsity
Unitary Transf.
Non-Exhaustive
Search
Pre-Scanning
Teknik
Tail Scan L1-Solver Weight Point Algorithm
SK II SK III
Gambar I.1. Perbandingan pekerjaan penelitian yang dilakukan pada Seminar Kemajuan I, II, dan III.
6
I.5 Publikasi terkait Gambar I.2 memperlihatkan publikasi yang telah dan yang direncanakan pada setiap kemajuan. Peningkatan Kinerja Skema Estimasi Arah Kedatangan Sinyal dengan Compressive Sensing Sparsitas Sudut dan sampel Multisnap
Multiple Measurement Vector for Improving FOCUSS algorithm in Direction of Arrival Estimation International Conference 2014 — ICoDSE
2014 — Jurnal Nasional INKOM LIPI
Angle Sparsity
Unitary Transf.
Non-Exhaustive
Search
Pre-Scanning
Uniform Non-Exhaustive Search on Sparse Reconstruction for Direction of Arrival Estimation International Conference 2015 — APWIMob
SK II Teknik
Tail Scan L1-Solver Weight Point Algorithm
SK III Direction of Arrival Estimation Estimation using Compressive Sensing : a Survey
L1 Sparse Reconstruction using Iterative Weight Point Method 2015 — to be SUBMITTED Journal of Computational and Applied Mathematics Elsevier
SK IV
2015 — to be SUBMITTED Indonesian Journal of Electrical Engineering Direction of Arrival Estimation 2016 / 2017
IEICE/IEEE
Gambar I.2. Publikasi yang telah dilakukan dan yang direncanakan
I.6 Kontribusi dan Kebaruan Kontribusi dan kebaruan yang diperoleh pada tahapan-tahapan penelitian yang telah dilakukan adalah: • Teknik Non-Exhaustive Search • Teknik Tail-Scan (uniform dan random) • Algoritma baru untuk rekonstruksi CS : metode Iterative Weight Point
7
BAB II Landasan Teori
II.1 Model matematis sistem Untuk keperluan simulasi, maka model matematis dari sistem yang ditinjau perlu dijabarkan terlebih dahulu. Tinjau susunan antena (antenna array) yang terdiri dari M buah elemen antena. Elemen antena ini disusun sehingga terletak pada satu garis, dengan jarak antar antena konstan. Susunan ini disebut sebagai uniform linear array / ULA. Misalkan bahwa sumber sinyal datang pada jarak yang jauh dengan sudut kedatangan sebesar θ relatif terhadap garis normal susunan antena (Gbr. II.1). Jika jarak sistem antena ke sumber jauh lebih besar dari pada dimensi susunan antena, maka berkas yang sampai ke masing-masing antena dapat dianggap sejajar. l1 θ
x1 (t) x2 (t)
d d
x3 (t)
∆
R
2∆
l2 l3
lM
(M − 1)∆
xM (t)
Gambar II.1. Antennas arrangement in ULA with distance d between element Dengan menggunakan antena paling atas sebagai referensi, serta jarak antar elemen antena adalah d, maka perbedaan jarak tempuh pada masing-masing antena (∆) dapat ditulis sebagai ∆ = d · sin(θ).
(II.1)
Perbedaan jarak ini berkorespondensi dengan delay fasa sebesar : 2π · d · sin(θ) (II.2) λ Dengan mengumpulkan sinyal yang diterima oleh masing-masing antena pada suatu vektor x, maka persamaan sinyal terima pada keluaran array adalah : φ=
8
x = a·s+n
(II.3)
Pada pers.II.3, s adalah sinyal pada masukan antena (dengan dimensi p kali N snaps; p adalah jumlah objek), x menotasikan sinyal pada keluaran antena (dengan dimensi M kali N snaps), n dalah white gaussian noise, dan a adalah array steering vector atau array manifold. Steering vector a dapat dinyatakan sebagai : h
a = 1 e−jψ e−j(M −1)ψ
iT
(II.4)
Sebagai penerima, steering vector menyatakan bobot pada antena yang berkorespondensi dengan arah penerimaan maksimum dari sinyal datang (main beam).
II.2 Compressive Sensing Compressive Sampling/Sensing (CS), adalah pendekatan baru yang menyatukan antara proses sampling dan kompresi. Dengan kekhususan bahwa sinyal yang disampling bersifat sparse (mayoritas sinyal adalah nol dan sedikit sisanya tak nol). Dengan asumsi ini, maka teknik CS dapat digunakan untuk mensampling sinyal dengan rate yang jauh lebih kecil dari pada sampling rate klasik Nyquist. Pada sampling rate yang rendah ini, CS tetap masih mampu untuk merekonstruksi sinyal semula. Kemampuan ini membuka peluang CS dapat menggantikan peralatan yang ada saat ini dengan peralatan yang bekerja berdasarkan prinsip CS yang efisien. Secara prinsip, pensamplingan dengan CS dilakukan dengan mengumpulkan secara random dari sampel lengkap. Pada teknik sampling klasik Nyquist, proses sampling dan rekonstruksi secara prinsip adalah sederhana dibandingkan dengan sampling dan rekonstruksi pada CS. Proses sampling pada teknik sampling klasik dilakukan dengan melakukan pencuplikan pada sinyal analog dengan jarak antar sampel yang sama/konstan. Pada bagian rekonstruksi, sinyal hasil sampling difilter dengan filter Nyquist untuk memperoleh kembali sinyal semula. Pada teknik CS, sebelum proses sampling dapat dilaksanakan, pertama harus ditentukan terlebih dahulu basis dua basis, yaitu basis sparsitas Ψ dan basis projeksi Φ. Keberhasilan teknik CS tergantung pada keberhasilan menentukan kedua basis tersebut. Dengan demikian proses modifikasi dari sinyal pada sisi penerima perlu dilakukan. Ini berarti bahwa perangkat CS akan lebih kompleks dibandingkan dengan peralatan sampling klasik. Pada sisi rekonstruksi, solusi dari teknik CS tidaklah unik/tunggal. Dengan kata lain, setelah set solusi ditemukan, maka diperlukan optimasi dengan suatu kriteria (biasanya adalah norm orde-n) dari set solusi yang ada untuk memperoleh satu solusi terbaik sesuai kriteria tersebut. Solusi terbaik
9
diharapkan (secara statistik) sama atau mendekati sinyal asal. Beberapa peralatan telah dikembangkan dengan prinsip CS ini. Antara lain adalah kamera-satu-piksel (Baraniuk (2007)), sparse MRI (Swastika dan Haneishi (2012)), spectra-denoising (Mingxia dkk. (2013)) dan sebagainya. Formulasi matematika dari compressive sensing. Ada banyak cara untuk menjelaskan prinsip kerja dari compressive sensing. Tapi yang akan dibahas di sini adalah dengan menggunakan prinsip ketidakpastian (uncertainty principle atau UP). Prinsip ini menyatakan bahwa suatu sinyal tidak mungkin secara bersamaan dapat dilokalisasi dengan baik pada ranah waktu dan frekuensi. Dengan kata lain, jika suatu sinyal terlokalisasi pada ranah waktu, maka sinyal tersebut tidak terlokalisasi pada ranah frekuensi. Sebaliknya jika suatu sinyal terlokalisasi pada ranah frekuensi, maka ia tidak terlokalisasi pada ranah waktu. Jika suatu sinyal f tidak terlokalisasi pada suatu ranah, maka akan selalu dapat dicari suatu transformasi Ψ pada f untuk menghasilkan suatu sinyal textbfF yang bersifat sparse. Dengan kata lain: F = Ψf
(II.5)
Pada sinyal sparse F tersebut, CS dapat dilakukan dengan mengalikan di awal (pre-multiplying) dengan suatu pencuplik Φ yang merupakan suatu matrik CS. g = ΦF = ΦΨf
(II.6)
Jika sinyal asal, f dan hasil transformasinya, F memiliki panjang N , maka sinyal f, dapat direkonstruksi kembali dari sinyal g dengan panjang M (M<
(II.7)
dimana K menyatakan tingkat sparsitas dari sinyal f, C adalah suatu konstanta (sekitar 2), dan µ(Φ, P si) menyatakan fungsi pengukur tingkat koherensi dari Φ dan Ψ. Tingkat koherensi ini diberikan oleh µ(Φ, Ψ) = max |hφ, ψi| φ3Φ,ψ3Ψ
(II.8)
Perkalian antara fungsi sparsitas Ψ dan fungsi sampling Φ dalam bentuk matrik tersebut dapat dinyatakan sebagai matrik sensing A : A = ΨΦ
10
(II.9)
Dengan demikian g = ΨΦf = Af
(II.10)
Proses rekonstruksi secara matematis dilakukan menyelesaikan II.10 dalam f. Namun, oleh karena f memiliki N nilai yang tidak diketahui, sedangkan II.10 memiliki M buah persamaan (M << N ), maka penyelesaian II.10 membelikan banyak alternatif solusi bagi f. Kondisi ini disebut sebagai ill-posed problem. Agar solusi menjadi unik dan sama atau mendekati dari sinyal semula, maka dilakukan optimasi dari solusi yang diperoleh. Optimasi yang umum dilakukan adalah dengan menggunakan optimisasi norm orde-n. Orde yang lazim dipakai dengan asumsi sinyal f bersifat sparse adalah norm- orde 1. Proses rekonstruksi CS ini secara umum dapat dituliskan sebagai min |f |1 s.t. A · f = g
(II.11)
Minimisasi |f |1 berarti mencari solusi f yang paling sparse. Pada lingkungan yang memiliki derau atau noise, maka sinyal terima akan memasukkan faktor derau ini, sehingga permasalahan CS seperti pada II.10 menjadi : g = Af + n
(II.12)
Proses rekonstruksi CS dengan demikian dimodifikasi menjadi: min |f |1 s.t. A · f − g ≤
(II.13)
Dengan adalah suatu bilangan kecil.
II.3 Compressive sensing pada estimasi DoA Pada bidang radar yang ditinjau, khususnya pada algoritma estimasi arah kedatangan sinyal (Direction of Arrival Estimation - DoA), terdapat beberapa skema CS yang telah dilakukan pada penelitian terdahulu. Penerapan CS pada estimasi DoA secara umum terbagi ke dalam tiga skema : sparsitas waktu (Gurbuz dan McClellan (2008), Kim dkk. (2012)), sparsitas ruang (Wang dkk. (2009), Wang dkk. (2010)), and sparsitas sudut (Gorodnitsky dan Rao (1997), Stoica dkk. (2011), Usman dkk. (2014)). Sparsitas waktu mengambil asumsi bahwa sinyal yang dikirim adalah sinusoidal, oleh karena itu, sinyal terima bersifat sparse dalam waktu (atau frekuensi). Sinyal terima x yang dikumpulkan oleh M buah antena N dilakukan sampling pada ranah waktu dengan teknik sampling klasik sebanyak N buah sampel untuk menghasilkan blok sinyal terima sebesar M kali N sinyal masukan. Dengan menggunakan pemrosesan blok,
11
setial blok sinyal terima ini dikalikan-sebelum (pre-multiplied) dengan sensing matrix A (berukuran M kali k, dengan k << N) untuk memperoleh sinyal keluaran y yang berdimensi M kali k, jauh lebih kecil dari pada ukuran sinyal masukkan semula x. Untuk proses estimasi arah kedatangan, sinyal yang telah dikompres ini kemudian dikembalikan ke sinyal semula sebelum algoritma DoA diterapkan. Sparsitas ruang memiliki prinsip kerja yang mirip dengan sparsitas waktu. Jika sparsitas waktu mengasumsikan bahwa sinyal tersebut sparse dalam waktu, maka sparsitas ruang mengasumsikan bahwa masing-masing antena pada susunan antena penerima sebenarnya menerima sinyal yang sama dengan perbedaan hanya pada waktu kedatangan (delay). Dengan demikian, sinyal terima diasumsikan bersifat sparse pada arah antena, atau ruang. Sinyal yang dikumpulkan oleh M buah antena, seperti halnya pada sparsitas waktu, memiliki dimensi M kali N . Proses sensing dilakukan dengan dengan mengalikan sinyal terima dengan sensing matrix A yang berdimensi k kali N . Seperti halnya sparsitas waktu, sinyal semula perlu direkonstruksi ulang dengan sebelum estimasi arah kedatangan dapat dilakukan. Dibandingkan dengan sparsitas waktu, skema sparsitas ruang memiliki kekurangan yaitu tingkat kompresi yang rendah, sedangkan kelebihannya adalah ketahanan sinyal terhadap derau lebih baik, serta lebih mudah direalisasikan dalam bentuk perangkat keras, karena matrik sensing A telah secara langsung memberikan arah panduan pada pembuatan perangkat kerasnya. Skema sistem penerima dengan sparsitas ruang dapat dilihat pada Wang dkk. (2009) dan Wang dkk. (2010). Sparsitas sudut memiliki pendekatan yang berbeda dibandingkan dengan sparsitas waktu dan sparsitas ruang sebelumnya. Skema sparsitas sudut tidak melakukan kompresi pada arah waktu dan ruang. Skema ini mengasumsikan bahwa sinyal yang diterima berasal dari sejumlah sumber sinyal yang terbatas. Beberapa sumber sinyal ini datang pada sudut-sudut yang berbeda. Berdasarkan pada anggapan ini, maka konstruksi permasalahan CS dilakukan dengan menggunakan sensing matrik A yang tersusun atas steering vector dari sinyal datang. Deskripsi matematis yang lebih rinci diberikan pada sub-bab berikutnya. CS formulasi dilakukan dengan menggabungkan sensing matrix A, sparse vektor s, dan snapshot dari sinyal terima x. Rekonstruksi CS tersebut dituliskan sebagai A·s = x (II.14) Jika terdapat derau AWGN, maka Rekonstruksi CS tersebut dimodifikasi menjadi (analogi dengan Persamaan II.12): A · s = x + n.
(II.15)
Dengan menggunakan pendekatan ini, maka sparsitas sudut memiliki keuntungan
12
signifikan dibandingkan dengan skema sparsitas waktu dan sparsitas ruang, karena skema ini memerlukan sangat sedikit sinyal terima, serta proses estimasi DoA dilakukan bersamaan dengan rekonstruksi CS. Dengan kata lain, penyelesaian CS pada sparse matrik s sekaligus juga adalah penyelesaian masalah estimasi arah kedatangan. Estimasi arah kedatangan sinyal diperoleh berdasarkan posisi element tak nol dari dari matrik solusi sparse s (Gorodnitsky dan Rao (1997)). Gambar II.2 mengilustrasikan proses penyusunan konstruksi CS teknik sparsitas sudut.
A a11
a12
a1p
a21
a22
a2p
aM 1
aM 2
aM p
a(θ1 ) a(θ2 )
s s1
x x1i
s2
x2i
s3
x3i
sp
xM i
a(θM )
steering vector at angle θi Gambar II.2. Ilustrasi skema sparsitas sudut. Sensing matrix A disusun dari steering vector sudut-sudut yang dipindai Meski pun memiliki keuntungan ini, skema sparsitas sudut memiliki kelemahan, yaitu kurang tahan terhadap derau lingkungan. Hal ini diverifikasi oleh Usman dkk. (2014). Pada penelitian tersebut, Usman dkk. (2014) mengusulkan peningkatan performa sinyal dengan menggunakan teknik multi-snaps CS. Skema multi-snaps CS ini dilakukan dengan memperluas vektor sinyal terima x menjadi beberapa snap-shots. Solusi sparse s dengan demikian akan mengikuti perluasan ini. Dengan kata lain, vektor s terdiri dari beberapa kolom, yang masing-masing kolom berkorespondensi dengan hasil estimasi arah kedatangan pada setiap snap-shots. Estimasi DoA dilakukan dengan merata-ratakan nilai estimasi pada setiap snap-shots. Dengan demikian estimasi yang diperoleh menjadi lebih robust dibandingkan dengan hanya menggunakan satu snap-shot. Upaya untuk melakukan perbaikan skema sparsitas sudut dilakukan pula oleh Stoica dkk. (2011) secara terpisah. Skema yang diusulkan oleh Stoica dkk. (2011) diistilahkan dengan independently covariance-based estimation technique (SPICE). Skema Stoica dkk. (2011) juga mengakomodasi kemampuan multi-snaps untuk meningkatkan ketahanan terhadap noise.
13
Permasalahan lainnya dari sparsitas sudut adalah besarnya sensing matrix A. Sebagaimana yang telah dibahas sebelumnya, sensing matrix A disusun berdasarkan steering vector dari arah kedatangan yang dipindai. Pemindaian yang dilakukan pada semua arah kedatangan sinyal (dari −900 sampai 900 ) disebut dengan exhaustive search. Bab selanjutnya membahas dengan terperinci tentang exhaustive search tersebut serta skema peningkatan yang diusulkan.
II.4 CS solver dengan CVX Programming Ada beberapa CS solver yang dapat digunakan untuk menyelesaikan permasalahan estimasi sudut dengan rekonstruksi sparse. Dua solver yang umum dipakai adalah CVX-programming dan l1 -magic. CVX-programming dikembangkan oleh Boyd (2014), sedangkan l1 -magic dikembangkan oleh oleh Candes dan Romberg (2005). CVX-programming bersifat umum dengan kemampuan melakukan optimasi pada berbagai permasalahan pemrograman linier (Linear Programming - LP). CVX-programming juga dapat mengoptimasi pilihan solusi dengan konstrain norm. Dengan demikian, CVX-programming bersifat sangat fleksibel. Engine solver yang digunakan pada CVX-programming antara lain adalah SDPT3 and SeDumi. Terdapat pula solver lain yang berlisensi yang dapat digunakan pada cvx seperti Gurobi dan MOSEK (Boyd (2014)). Untuk menyelesaikan persamaan CS seperti yang terdapat pada persamaan ??, pada CVX-programming, dapat kita tuliskan seperti contoh berikut: begin cvx variable s(n) complex; minimize(norm(s,1)); subject to norm(A*s-x,2) < epsilon; end cvx.
14
BAB III Metode yang diusulkan
III.1 Teknik Non-Exhaustive Search Sebelum dibahas tentang teknik non-exhaustive search, terlebih dahulu akan dibahas tentang metode Exhaustive search. Exhaustive search adalah upaya untuk menemukan arah kedatangan sinyal dengan melakukan pemindaian pada semua arah kedatangan sinyal yang mungkin. Peneliti sebelumnya melakukan pemindaian secara exhaustive objek ini. Pada makalahnya, Gorodnitsky dan Rao (1997) melakukan pemindaian pada semua sudut antara −900 sampai 900 . Stoica dkk. (2011) melakukan pemindaian dari −900 sampai 900 dengan resolusi 0.10 , dengan demikian terdapat 1800 arah pindai yang berkorespondensi dengan matriks sensing A yang berdimensi M kali 1800. Hal yang sama dilakukan oleh Usman dkk. (2014). Gambar III.1 menunjukkan ilustrasi pemindaian dengan teknik exhaustive search. 00
objek
arah pemindaian -900
900
Gambar III.1. Ilustrasi exhaustive search. Algoritma memindai pada semua arah untuk memperoleh arah sumber sinyal Permasalahan yang dihadapi oleh teknik exhaustive search, seperti yang telah dikemukakan sebelumnya, adalah besarnya sensing matrix A. Sensing matriks yang besar memerlukan proses komputasi rekonstruksi CS yang besar, sumber daya yang tinggi, serta waktu yang lama. Penyelesaian permasalahan ini diusulkan pada sub-bab berikutnya yang membahas tentang pemindaian non-exhaustive search. Kemajuan yang dicapai pada penelitian ini berkisar pada eksplorasi teknik non-exhaustive search. Teknik ini adalah perbaikan dari teknik exhaustive search berupa pengurangan rentang pemindaian dari semua sudut yang mungkin (tipikal pada −900 sampai 900 ), ke dalam rentang yang lebih sempit. Tentu pemindaian pada
15
rentang yang lebih sempit ini dimungkinkan jika telah ada gambaran tentang arah sumber sinyal. Untuk keperluan memperoleh gambaran tentang arah sumber sinyal tersebut, maka diperlukan suatu pemindaian kasar, misalnya dengan menggunakan estimasi DoA klasik (DAS, MVDR, MUSIC, atau ESPRIT). Setelah gambaran kasar arah kedatangan sinyal ini diperoleh, maka proses DoA selanjutnya dilanjutkan dengan teknik CS dengan rentang sudut sempit, yang diperbarui setiap saat, sesuai dengan arah gerakan objek. Skema pemindaian kasar sebelum teknik CS disebut dengan istilah pra-pemindaian. Skema non-exhaustive search dengan pra-pemindaian selengkapnya diberikan pada Gambar III.2.
Pengaturan Jendela Pemindaian
Pemindaian Kasar
Sinyal terima
Akuisisi
Snapshot
Konstruksi CS
DoA
CS Solver
Gambar III.2. Blok diagram skema non-exhaustive search dengan fungsi pemindaian kasar Pada Gambar III.2 tersebut, sinyal mula-mula diakuisisi oleh sistem antena penerima. Pada awal operasi, sinyal dimasukkan ke blok pemindaian kasar. Proses pada blok pemindaian kasar ini bertujuan untuk memperoleh gambaran umum tentang posisi sinyal. Blok pemindaian kasar ini dapat menggunakan salah satu algoritma klasik, seperti DAS, MVDR, MUSIC, dan ESPRIT. Pada proses kemajuan ini II ini, digunakan teknik MVDR. Teknik ini sederhana serta memiliki resolusi yang tinggi. Skema MUSIC dan ESPRIT memerlukan komputasi yang lebih tinggi, sedangkan DAS memiliki resolusi yang rendah. Gambar III.3 menunjukkan ilustrasi skema non-exhaustive search. Pada gambar tersebut, rentang sudut pemindaian dinyatakan sebagai jendela pindai (scanning window). Tracking objek pada skema CS-DoA. Keuntungan utama pada skema yang ditawarkan ini adalah penambahan kemampuan tracking terhadap gerakan objek mudah untuk dilaksanakan. Hal ini dikarenakan sampling objek dapat dilakukan
16
objek Objek Scanning Window θ2
θ1
θ
Scanning Window
(b)
(a)
Gambar III.3. Ilustrasi non-exhaustive search. (a) Skema dalam diagram arah/sudut dalam koordinat polar (b). dalam koordinat kartesian pada interval tertentu, dan pengambilan sampel sinyal yang sedikit setiap kali pengambilan. Jendela pemindaian (scanning window) dapat digeser-geser pada setiap iterasi menyesuaikan dengan dengan posisi objek. Untuk melakukan update scanning window ini, maka diperlukan suatu skema update. Pada penelitian ini, skema update dilakukan dengan terlebih dahulu menetapkan lebar scanning window (konstan). Pada setiap scanning, titik tengah dari scanning window diupdate sehingga berimpit atau mendekati lokasi dari posisi objek (Gbr III.5). Proses update dengan menjadikan lokasi objek sebagai median dari jendela pindai dapat dinyatakan dengan : θPmax = med([θmin , θmax ])
(III.1)
Pada Pers.III.1, θPmax menyatakan sudut estimasi objek, θmin dan θmax berturut-turut menyatakan batas kiri dan batas kanan dari jendela pindai.
III.2 Teknik Tail-scan Skema non-exhaustive search dilakukan dengan pembatasan wilayah sudut pindai hanya pada arah-arah tertentu saja. Namun pembatasan ini ternyata memberikan masalah baru pada proses rekonstruksi CS, yaitu CS Solver yang dalam hal ini adalah cvx-programming, tidak berhasil memperoleh solusi yang konvergen. Fenomena ini tidak diperkirakan sebelumnya, karena dengan asumsi bahwa titik optimal dari CS solver terletak pada lokasi sudut keberadaan sinyal, sedangkan sudut ini sendiri berada pada cakupan sudut yang dipindai. Namun ternyata, cvx-programming tidak berhasil memperoleh solusi yang konvergen. Gambar III.6 mengilustrasikan permasalahan ini.
17
objek objek objek
(a)
(b)
P
t1
t2
objek
objek
(c)
t3 objek
W1
θ
W2 W3
(d)
Gambar III.4. Ilustrasi tracking object dengan teknik non-exhaustive search serta update scanning window pada setiap waktu. (a),(b), dan (c) pergerakan objek beserta update scanning window yang bersesuaian. (d). ilustrasi pergeseran scanning window pada setiap waktu; W1, W2, W3 adalah scanning window berturut-turut pada t1, t2 dan t3 Pada gambar III.6 tersebut, terdapat tiga macam skema yang digunakan. Skema tersebut adalah skema exhaustive search (lebar jendela pindai adalah −900 sampai 900 ), skema non-exhaustive search dengan lebar jendela −300 sampai dengan 900 , dan skema terakhir adalah non-exhaustive search dengan lebar jendela 00 sampai dengan 900 . Sebagai pembanding, posisi aktual dari objek diberikan. Objek tersebut bergerak dari sudut 300 sampai dengan 900 dengan kecepatan 1, 40 per detik. Sumbu datar adalah waktu (dalam detik), dan sumbu tegak adalah sudut (dalam derajat). Pada gambar III.6 tersebut skema exhaustive search dan skema non-exhaustive search dengan sudut pindai lebar (−300 sampai dengan 900 ) berhasil mengikuti pergerakan objek dengan baik. Namun untuk lebar jendela pindai yang terlalu kecil (00 sampai dengan 900 ), cvx-programming gagal memberikan hasil konvergen. Hasil yang diperoleh, iterasi cvx-programming terjebak pada solusi semu di 50 dan 650 . Untuk mengatasi permasalahan ini, maka area pemindaian diperluas mencakup pada arah selain dari arah utama. Arah tambahan ini disebut dengan tail scanning. Gambar III.7 memperlihatkan ilustrasi tail-scanning. Sifat dari tail scan adalah : 1. jumlahnya lebih sedikit dibandingkan dengan pemindaian pada arah utama
18
P
θx1
(a)
θ
P
θx1
θ
(b) P
θx2
θ
(c) P
θx2
(d)
θ
Gambar III.5. Ilustrasi detail tentang proses update scanning window dengan menggunakan median dari posisi objek. (a) hasil scanning kasar dengan algoritma klasik pada semua sudut,(b) penerapan scanning window pada sudut yang dianggap memiliki objek, (c) objek bergerak sehingga puncak scanning bergeser menuju batas window. (d). update scanning window, sehingga puncak scanning berada di tengah scanning window (main-scan) 2. mengarah pada sudut yang tidak terdapat objek 3. berfungsi mencegah algoritma cvx-programming tidak konvergen atau terjebak pada solusi semu Pada penelitian ini, diusulkan dua macam tipe tail scan yaitu uniform tail scan dan random tail scan. Uniform tail scan adalah tail scan yang terpisah pada jarak yang seragam, sedangkan random tail scan adalah tail scan yang jarak antar pemindaian satu dan lainnya terpisah. Gambar III.8 menunjukkan ilustrasi uniform tail scan dan random tail scan.
19
70
60
angle (degree)
50
40 w 0 to 90 w -30 to 90 30
w -90 to 90 Actual
20
10
0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 time(second)
Gambar III.6. Hasil simulasi: perbandingan skema exhaustive search terhadap 00
objek
-900
900
Tail scan
Gambar III.7. Non-exhaustive search dengan tail-scan
III.3 Metode Titik Berat Metode titik berat dikembangkan pada tahap Kemajuan III ini sebagai jawaban atas permasalahan konvergensi yang dialami oleh metode convex programming yang dikembangkan oleh Boyd (Boyd dan Vandenberghe (2004); Boyd (2014)). Metode titik berat didasarkan pada fakta geometri bahwa rekonstruksi CS dapat diselesaikan dengan membesarkan atau mengecilkan norm L1 sehingga norm tersebut bersinggungan dengan fungsi objektif rekonstruksi. Sebagai ilustrasi, kita tinjau kasus dua dan tiga T dimensi berikut. Pada kasus dua dimensi, misalkan vektor asal adalah x = x1 x2 dan
T
A = A11 A12 , sehingga y = A·x = y1 . Permasalahan rekonstruksi adalah : diberikan A dan y, kita perlu mencari x sedekat mungkin dengan nilai asal. Kriteria sedekat mungkin dengan nilai asal dapat diukur misalnya dengan nilai kesalahan absolut rata-rata. Karena permasalahan ini bersifat underdetermined, kita dapat memiliki norm L1 sebagai kriteria rekonstruksi. Dengan kriteria ini, maka permasalahan rekonstruksi dapat didefinisikan kembali menjadi : diberikan A dan y, selesaikan
20
00
00
objek
-900
900
objek
-900
900
Tail scan
Tail scan (b)
(a)
Gambar III.8. Non exhaustive search dengan tail scan. (a) uniform tail scan, (b) random tail scan A · x = y untuk x sehingga kx|1 minimum. Oleh karena A adalah matrik dengan ukuran 1x2, maka solusi A · x = y adalah garis yang berada pada diagram kartesian x1 -x2 seperti yang ditunjukkan pada Gbr III.9.
x2
x2 A·x=y
xs
A·x=y
x1
x1
(A)
(B)
Gambar III.9. Solusi persamaan Ax=y terletak pada garis (A). Solusi dari Norm-L1 (B)
Norm orde p (p-norm) dari vektor x = x1 x2 · · · xN persamaan: kxkp =
T
diberikan oleh
q p
xp1 + xp2 + · · · + xpN
(III.2)
Sebagai contoh, 0-norm (L0 ),q1-norm (L1 ), dan 2-norm (L2 ) berturut-turut adalah m, |x1 | + |x2 | + · · · + |xN |, and 2 x21 + x22 + · · · + x2N . Dengan, m adalah jumlah elemen tak nol dari x. T Misalkan vektor x adalah x = 2 3 . Misalkan pula x = 0.6 0.4 . Oleh karena
itu y = Ax menghasilkan y = 1.2 . Dengan demikian permasalah rekkonstruksi
adalah : diberikan y = 1.2 dan x = 0.6 0.4 , perlu dicari x, sedemikian sehingga kxk1 minimum. Oleh karena x tidak diketahui, maka misalkan x = x1 x2 . Oleh karena itu Ax = y
menghasilkan 0.6x1 + 0.4x2 = 1.2. Ada tak hingga banyak solusi dari x1 x2 yang memenuhi 0.6x1 + 0.4x2 = 1.2. Oleh karena kita ingin mencari pasangan x1 x2 yang meminimalkan kxk1 . Maka sebagai langkah awalkita pilih kxk1 = k0 , dengan k0 adalah
21
nilai awal yang cukup besar sehingga kxk1 = k0 dan 0.6x1 + 0.4x2 = 1.2 berpotongan di P1 dan P2 (Gbr.III.10). Potongan garis kxk1 = k0 yang dibatasi oleh P1 dan P2 adalah konveks. Oleh karena itu, setiap titik M yang merupakan kombinasi konveks dari P1 dan P 2 M = t · P1 + (1 − t) · P2 ,
(III.3)
(0 ≤ t ≤ 1), akan terletak di dalam interval P1 dan P2 tersebut. x2
x2
kxk1 = k0
P1
P1
M1
kxk1 = k0
P3 M 2
M1
P2
P2
x1
x1
kxk1 = k1 (a)
(b)
Gambar III.10. (a). Iterasi awal dengan k0 yang cukup besar sehingga kurva Ax = y dan kxk1 = k0 berpotongan di P1 dan P2 . Titik tengah M1 dipilih sebagai iterasi berikutnya. (b). Norm di M1 dipilih sebagai nilai k berikutnya. Proses ini diulangi sehingga diperoleh titik yang konvergen. Dari Gbr III.10 juga terlihat bahwa setiap titik M yang berasal dari kombinasi konveks dari P1 dan P2 juga memiliki norm L1 yang lebih kecil dibandingkan dengan nilai awal. Selanjutnya kita akan turunkan kasus yang lebih rumit pada dimensi 3 yang kemudian kita generalisasi untuk kasus dimensi n. T Misalkan sinyal sparse x adalah x = 0 2 0 . Maka sensing matriks A memiliki dua kemungkinan yaitu matriks 1x3 atau matriks 2x3. Pada kondisi matriks 1x3, sinyal kompresi y adalah vektor 1x1 dan untuk kondisi matrik A 2x3, maka vektor y adalah berdimensi 2x1. Permasalahan rekonstruksi CS adalah sama dengan kasus dua dimensi: diberikan vektor y dan matrik A, tentukan x dengan kxk1 minimum. Solusi dari Ax = y pada kasus matriks A 1x3 adalah suatu bidang, sedangkan untuk matriks A 2x3 adalah suatu garis. Kita tinjau kasus matriks A 1x3 terlebih dahulu. Pada iterasi awal, kita ambil k0 cukup besar sehingga bidang Ax = y berpotongan dengan oktahedron kxk1 = k0 (Gbr.III.11). Bentuk dari bidang perpotongan dari kxk1 = k0 dan Ax = y dapat berupa politop 4-sisi atau politop 5-sisi seperti pada Gbr.III.11b. Pada algoritma titik berat, maka adalah penting untuk menentukan bidang perpotongan ini, khususnya titik sudut dari
22
solution of Ax = y
P5
M1
P1
P4 P3
P2 (b)
kxk1 = k0 (a)
Gambar III.11. (a). Kasus dimensi 3, kxk1 = k0 membentuk oktahedron. Solusi dari Ax = y dengan matrik A 1x3 adalah suatu bidang. Jika k0 cukup besar, kxk1 = k0 akan memotong Ax = y. (b). Bidang perpotongan dengan titik sudut P1 sampai P5 . Titik M1 dipilih sebagai kombinasi konveks dari titik-titik P1 sampai P5 . politof, sehingga kita dapat mencari titik berat M1 yang memiliki norm L1 yang lebih kecil dari nilai sebelumnya. Menemukan tiap sisi dari politop dapat dilakukan dengan menyelesaikan persamaan kxk1 = k0 dan Ax = y. Akan tetapi, karena sistem persamaan ini bersifat underdetermined, maka mencari titik sudut politop menjadi sulit. Di sini diusulkan suaatu teknik langsung untuk menyelesaikan permasalahan ini dengan menggunakan faktorisasi QR dari Householder (detail teori diberikan di Lampiran A). Penyelesaian dengan teknik ini disebut juga dengan istilah QR-factorization dengan pivot kolom Golub dan Loan (1996)). Pada teknik ini, proses permutasi kolom dari matrik A dilakukan sehingga suatu kriteria terpenuhi. Kriteria yang umum dipakai adalah pengurutan kolom dari kolom dengan norm L2 terbesar sampai dengan yang terkecil. Kolom dengan nilai norm tidak signifikan diabaikan. Dengan demikian, solusi dari metode ini menghasilkan nilai yang banyak memiliki nol. Transformasi Householder dengan pivot kolom dijelaskan pada Golub dan Loan (1996), dengan algoritma adalah sebagai berikut. Householder QR dengan pivot kolom. Given A 3 Rmxn . l1 for j=1:n l2 c(j) = A(1 : m, j)T A(1 : m, j) l3 end l4 r = 0 ; τ =max{c(1), · · · , c(n)} l5 cari k terkecil dengan 1 ≤ k ≤ n sehingga c(k) = τ l6 while τ ≥ 0 l7 r = r+1 l8 piv(r) = k ; A(1 : m, r) ↔ A(1 : m, k) ; c(r) ↔ c(k)
23
l9 l10 l11 l12 l13 l14 l15 l16 l17 l18 l19 l20 l21
[v, β] = house(A(r; m, r)) A(r : m, r : n) = (Im−r+1 − βvvT )A(r : m, r : n) A(r + 1 : m, r) = v(2 : m − r + 1) for i = r + l : n c(i) = c(i) − A(r, i)2 end if r ≤ n τ = max{c(r + 1), ..., c(n)} Find smallest k with r + 1 ≤ k ≤ n so c(k) = τ else τ =0 end end
Proses pivot kolom terjadi pada baris l8 pada algoritma di atas. Pivot dilakukan berdasarkan nilai tertinggi (baris l4 dan l5 ). Namun kriteria ini dapat diganti dengan nilai terendah dari L2 -norm dengan mengganti max menjadi min pada baris l4. Proses faktorisasi QR Householder adalah pada baris l9. Setiap matriks A dapat difaktorkan atas matrik orthonormal Q dan matrik segitiga atas R sedemikian rupa sehingga A = QR. . Proses transformasi Householder itu sendiri adalah: Householder transformation. Given x 3 Rn . l1 n = length(x) T l2 σ = x(2 : n) x(2 : n) 1 l3 v= x(2 : n) l4 if σ = 0 l5 β=0 l6 else q l7 µ = x(1)2 + σ l8 if x(1) ≤ 0 l9 v(1) = x(l) − µ l10 else l11 v(1) = −σ/(x(1) + µ) l12 end
24
(III.4)
l13 l14 l15
β = 2v(1)2 /(σ + v(1)2 ) v = v/v(1) end
Dengan menerapkan faktorisasi QR Householder serta pivot kolom akan menyelesaikan sistem persamaan linier dengan pada solusi di titik sudut dari bidang datar perpotongan norm orde 1 dan fungsi objektif. Akan tetapi, jika terdapat N titik sudut, teknik ini akan mendeteksi N − 1 titik sudut. Titik sudut dengan L2 -norm terkecil tidak dapat terpilih oleh algoritma ini. Untuk mengatasi permasalahan ini, ditambahkan langkah khusus setelah faktorisasi QR Householder dengan pivot kolom. Pivot kolom pada langkah tambahan ini dilakukan dengan urutan nilai norm L2 yang terkecil, yang berkebalikan dengan kolom pivoting sebelumnya yang didasarkan pada nilai terbesar. Langkah ini disebut dengan backward column pivoting. Kombinasi dari kedua langkah pivot kolom ini menghasilkan solusi lengkap dari semua titik sudut perpotongan (Gbr.III.12). P5
P5 P4
P1 O
P4
P1
P3
O
P2 (a)
P3 P2 (b)
Gambar III.12. Faktorisasi QR Householder dengan pivot kolom (a). Pivot kolom dengan urutan L2 -norm dari yang terbesar ke yang terkecil (b). Pivot kolom dengan urutan L2 -norm dari yang terkecil ke yang terbesar Sama dengan kasus dua variabel sebelumnya, setiap titik M yang berasal dari kombinasi konveks dari titik-titik sudut pada bidang solusi memberikan nilai k baru yang lebih kecil dari nilai sebelumnya. M = α 1 · P1 + α 2 · P2 + · · · + α N · PN
(III.5)
α1 + α2 + · · · + αN = 1
(III.6)
dengan
dan 0 ≤ αi ≤ 1 untuk semua i. Untuk kesederhanaan, pada metode yang diusulkan ini, dipilih setiap nilai αi yang sama. Dengan demikian, 1 (III.7) α1 = α2 = · · · = αN = . N
25
Secara geometri, pemilihan nilai αi yang sama maka akan dihasilkan titik M yang merupakan titik berat dari politop. Pada umumnya, metode titik berat ini tidak menjamin konvergensi pada arah yang tercepat, namun ia menjamin konvergensi pada solusi optimal. Setelah kita tinjau matrik A dengan dimensi 1x3, maka sekarang akan ditinjau kondisi ketika matrik A berdimensi. Solusi dari permasalahan rekonstruksi Ax = y adalah berupa irisan dari dua buah bidang yang menghasilkan suatu garis. Setiap bidang dinyatakan pada setiap baris dari persamaan linier. Seperti halnya kondisi terdahulu, untuk nilai awal, dipilih k cukup besar sehingga oktagon kxk1 = k0 berpotongan dengan garis solusi fungsi objektif (Gbr.III.13). Misalkan titik potong tersebut adalah P1 dan P2 . Kondisi ini dengan demikian sama dengan kondisi pada dua variabel. Oleh karena itu, setiap titik M1 yang berasal dari kombinasi konveks dari P1 dan P2 akan memberikan nilai k yang lebih kecil. Nilai k ini selanjutnya digunakan untuk iterasi berikutnya.
Solution of Ax = y P2
P2
M1
P1
P1
kxk1 = k0
Gambar III.13. Perpotongan antara oktahedron norm L1 dengan solusi dari fungsi objektif yang berupa garis. Titik potong bidang dan garis dinotasikan dengan P1 dan P 2. Titik M1 yang merupakan kombinasi konveks dari P1 dan P 2 diilustrasikan pada gambar kanan Generalisasi untuk dimensi n Setelah pembahasan pada dimensi 2 dan dimensi 3, maka langkah-langkah yang dilakukan pada kedua dimensi tersebut dapat digeneralisasi menjadi suatu algoritma untuk dimensi n. Algoritma ini disebut dengan metode titik berat weight point. Sebelum algoritma tersebut dikemukakan, berikut ini adalah dua teorema fundamental yang menjadi dasar dari algoritma titik berat ini. Teorema 1 Jika suatu bidang dibatasi oleh kxk1 = k dan solusi dari persamaaan linier Ax = y saling berpotongan, maka bentuk dari perpotongan tersebut adalah berupa suatu politop. Bukti : - . Teorema 2 Jika P1 , P2 , · · · , PN adalah titik-titik sudut dari politop yang dideskripsikan
26
pada Teorema 1, maka setiap kombinasi konveks dari P1 , P2 , · · · , PN akan menghasilkan titik yang memiliki norm orde 1 kM yang lebih kecil dari norm orde 1 semula yang melalui Pi . Bukti : - . Setelah kedua teorema di atas, berikut ini adalah algoritma weight point untuk dimensi n. Algoritma titik berat.
1. pilih nilai awal k yang cukup besar. 2. susun persamaan kxk1 = k untuk setiap kombinasi dari x 3. susun set persamaan linier [A; xhi ] = [y; k] 4. selesaikan set persamaan linier [A; xhi ] = [y; k] dengan faktorisasi QR Householder dengan pivot kolom pada pengurutan prioritas maksimum 5. selesaikan set persamaan linier [A; xhi ] = [y; k] dengan faktorisasi QR Householder dengan pivot kolom pada pengurutan prioritas minimum 6. kombinasikan solusi langkah 3 dan 4 untuk memperoleh semua titik sudut dari politop (P1 , P2 , · · · , PN ). 7. hitung titik berat Mi = (P1 + P2 + · · · + PN )/N 8. hitung norm L1 dari titik berat Mi dan gunakan nilai norm ini untuk iterasi berikutnya 9. ulangi langkah 2 sampai dengan 8 sampai abs(ki+1 − ki )≤ epsilon, dengan < adalah suatu bilangan positif kecil.
27
BAB IV Hasil kemajuan
IV.1 Hal yang telah dilakukan pada semester berjalan Pada Kemajuan III ini, hal-hal yang telah dilakukan adalah: 1. Mensimulasikan teknik non-exhaustive search dengan tail scan 2. Menurunkan algoritma rekonstruksi CS berdasarkan metode titik berat. 3. Mendraft jurnal untuk publikasi dari hasil-hasil yang diperoleh
IV.1.1 Hasil simulasi teknik non-exhaustive search dengan tail scan Simulasi komputer dilakukan untuk memverifikasi efektifitas skema non-exhaustive search dengan tail scan yang diusulkan. Lingkungan simulasi diberikan pada Tabel IV.1 Tabel IV.1. Parameter simulasi exhaustive dan non exhaustive search No Skema Parameter Nilai 1 Exhaustive Search Susunan Antena ULA 12 element SNR 10 dB Kecepatan Objek 1,40 /s 0 Sudut jelajah objek 30 sampai 600 Resolusi pindai 10 Jumlah objek 1 2 Non Exhaustive Search Parameter dasar sama dengan (Jumlah antena, dll.) exhaustive search Skema pra-pemindaian MVDR 0 Lebar jendela pindai −30 sampai 900 dan 00 sampai 900 CS Solver CVX-programming Hasil simulasi diperlihatkan pada Gambar III.6. Pada gambar tersebut, terlihat bahwa skema non-exhaustive search dengan lebar jendela pindai yang cukup lebar (-300 sampai dengan 900 ) memiliki performa yang baik dalam melakukan tracking pada gerakan objek. Performanya tidak jauh berbeda dengan performa exhaustive search. Permasalahan muncul ketika lebar jendela pindai dipersempit pada sudut 00
28
sampai 900 . Pada rentang sudut pindai ini, rekonstruksi dengan cvx-programming tidak berhasil memperoleh solusi yang konvergen. Iterasi cvx-programming terjebak pada dua nilai sudut estimasi salah yaitu 50 dan 650 . Oleh karena skema exhaustive search berhasil sedangkan teknik non-exhaustive search gagal untuk rentang sudut pindai yang sempit, maka kenyataan ini memberikan inspirasi untuk menambahkan pemindaian pada sudut-sudut tambahan di luar dari arah pindai utama. Pemindaian pada sudut-sudut tambahan ini diistilahkan dengan tail scan.
IV.2 Perbandingan akurasi regular dan random tail-scan tanpa interpolasi
29
IV.3 Perbandingan akurasi regular dan random tail-scan dengan interpolasi
IV.4 Perbandingan kegagalan konvergensi pada tail-scan
30
IV.5 Perbandingan waktu komputasi pada skema tail-scan
31
BAB V Penutup
Pada Kemajuan III ini, telah dilaporkan mengenai penjelasan tentang topik penelitian serta hasil-hasil yang dicapai sampai sejauh ini. Beberapa hasil simulasi dan ide baru yang dicapai pada Kemajuan II yaitu tentang teknik tail-scan, disimulasikan secara lebih mendalam pada Kemajuan III ini. Pada kemajuan III ini juga dilaporkan tentang metode baru yaitu algoritma rekonstruksi CS dengan metode titik berat. Teknik tail-scan serta metode titik berat ini sejauh yang telah diteliti pada literatur, belum pernah dilakukan oleh peneliti lain sebelumnya. Rencana ke depan adalah pematangan dari kedua teknik yang diusulkan ini beserta publikasinya pada jurnal internasional.
32
Daftar Pustaka
Baraniuk, R. (2007): Compressive Sensing, IEEE Signal Processing Magazine, 24(4), 118–121. Boyd, S. (2014): CVX: Matlab Software for Disciplined Convex Programming, URL http://cvxr.com/cvx/. Boyd, S. dan Vandenberghe, L. (2004): Convex Optimization, Cambridge University Press. Candes, E. dan Romberg, J. (2005): l1-Magic : Recovery of Sparse Signals via Convex Programming, URL http://users.ece.gatech.edu/ justin/l1magic/. Candes, E. dan Wakin, M. B. (2008): Compressive Sampling, Proceedings of the International Congress of Mathematicians, Madrid, Spain, 25(2), 21 – 30. Chen, S. S., Donoho, D. L., dan Saunders, M. A. (2001): Atomic Decomposition by Basis Pursuit, SIAM Review, Society for Industrial and Applied Mathematics, 43(1), 129–159. Dai, J., Xu, X., dan Zhao, D. (2013): Direction-of-Arrival Estimation Via Real-Valued Sparse Representation, Antennas and Wireless Propagation Letters, IEEE, 12, 376–379. Dmochowski, J., Benesty, J., dan Affes, S. (2007): Direction of Arrival Estimation Using the Parameterized Spatial Correlation Matrix, Audio, Speech, and Language Processing, IEEE Transactions on, 15(4), 1327–1339. Donoho, D. L. (2006): Compressed Sensing, IEEE Transactions on Information Theory, 52(4). Golub, G. H. dan Loan, C. V. (1996): Matrix Computation, Johns Hopkins University Press; 3rd edition (October 15, 1996). Gorodnitsky, I. F. dan Rao, B. D. (1997): Sparse Signal Reconstruction from Limited Data Using FOCUSS: A Re-weighted Minimum Norm Algorithm, IEEE Transactions on Signal Processing, 45(3).
33
Gurbuz, A. C. dan McClellan, J. H. (2008): A Compressive Beamforming Method, Proceeding of the IEEE International Conference on Acoustics, Speech and Signal Processing. Hayasi, K., Nagahara, M., dan Tanaka, T. (2013): A UserŠs Guide to Compressive Sensing for Communications Systems, In IEICE Transaction on Communication, E96-B(3), 685–712. Jouny, I. (2011): Music DOA estimation with compressive sensing and/or compressive arrays, Antennas and Propagation (APSURSI), 2011 IEEE International Symposium on, 2016–2019. Kim, J. M., Lee, O. K., dan Ye, J. C. (2012): Compressive MUSIC: Revisiting the Link Between Compressive Sensing and Array Signal Processing, IEEE Transctions on Information Theory, Vol. 58, No. 1, January 2012. Mallat, S. dan Zhang, Z. (1993): Matching Pursuits With Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, 41(12), 3397–3415. Mingxia, X., Changhua, L., Xing, M., dan Weiwei, J. (2013): The Application of Compressive Sensing on Spectra De-noising, TELKOMNIKA, 11(10), 6151–6157. Telkomnika Ahmad Dahlan. Roy, R., Paulraj, A., dan Kailath, T. (1986): Estimation of Signal Parameters via Rotational Invariance Techniques Ű ESPRIT., Proceeding of IEEE Military Communications (MILCOM) Conference - Communications, 3. Schmidt, R. (1986): Multiple Emitter Location and Signal Parameter Estimation, IEEE Transactions on Antennas and Propagation, 34(3), 276–280. Stoica, P., Babu, P., dan Li, J. (2011): SPICE: A Sparse Covariance-Based Estimation Method for Array Processing, Signal Processing, IEEE Transactions on, 59(2), 629–638. Swastika, W. dan Haneishi, H. (2012): Compressed Sensing for Thoracic MRI with Partial Random Circulant Matrices, Telkomnika, 10(1), 147–154. Tropp, J. A. (2004): Greed is Good : Algorithmic Results for Sparse Approximation, IEEE Transactions on Information Theory, 50(10). Usman, K., Suksmono, A. B., dan Gunawan, H. (2014): Peningkatan Kinerja Skema Estimasi Arah Kedatangan Sinyal dengan Compressive Sensing Sparsitas Sudut dan Sampel Multisnap, Inkom Journal, 8(1), 21–27.
34
Veen, B. V. dan Buckley, K. M. (1988): Beamforming: A Versatile Approach to Spatial Filtering, IEEE ASSP Magazine. Wahidah, I. dan Suksmono, A. B. (2010): Recontruction Algorithms for Compressive Video Sensing Using Basis Pursuit, Proceeding of the 6th International Conference on Information & Communication Technology and Systems. Wang, Y., Leus, G., dan Pandharipande, A. (2009): Direction Estimation Using Compressive Sampling Array Processing, Proceeding of IEEE SSP. Wang, Y., Pandharipande, A., dan Leus, G. (2010): Compressive sampling based MVDR spectrum sensing, Proceeding of IAPR.
35
Lampiran A : Faktorisasi QR
Sebelum kita membahas tentang faktorisasi, mari terlebih dahulu kita lihat suatu contoh penguraian suatu matrik A 2x2 yang sederhana menjadi perkalian dua matrik sederhana. Tahapan penguraiannya adalah sebagai berikut. Misalkan
2 5 A= 2 4 .
2 Kita dapat memandang bahwa matrik A tersusun dari dua vektor kolom yaitu 2
5 dan kolom kedua yaitu . Katakanlah bahwa vektor kolom pertama adalah a1, dan 4 vektor kolom kedua adalah a2. 1 1 Sekarang mari kita ambil dua buah vektor referensi, yaitu v1 = dan v2 = . 0 1 Sekarang tugas kita yang pertama adalah menyatakan kolom vektor a1 sebagai kombinasi linier dari referensi v1 dan v2. Tugas pertama ini gampang, karena :
1 2 a1 = = 2 · = 2v1 = 2v1 + 0v2 1 2 Berikutnya adalah menyatakan kolom vektor a2 sebagai kombinasi linier dari referensi v1 dan v2. Dengan mencoba-coba, kita peroleh salah satu solusi adalah :
5 1 1 a2 = = 4 · + 1 · = 4v1 + 1v2 4 1 0 Sekarang kita susun kolom vektor a1 dan a2 untuk menghasilkan matrik A. Kita peroleh :
A = a1 a2 = 2v1 + 0v2 4v1 + v2
= v1 v2
2 4 1 1 2 4 · = · = D·E 0 1 1 0 0 1
36
Dengan kata lain, kita berhasil menguraikan matrik A menjadi perkalian dua matrik D dan E seperti pada persamaan terakhir di atas. Matrik D, karena tersusun atas vektor referensi, disebut sebagai matrik referensi atau BASIS, dan matrik E, karena tersusun sebagai informasi kombinasi dari tiap basis tadi disebut sebagai matrik BOBOT. Faktorisasi QR bekerja dengan cara yang sama. Faktorisasi QR ini mendekomposisi suatu matrik A menjadi komponen BASISnya atau matrik Q, dan komponen bobotnya atau matrik R. Keistimewaan dari Basis Q yang dipilih ini adalah bahwa ia bersifat ortonormal (i.e. setiap kolomnya tegak lurus dengan kolom lain, dan panjang norm orde 2 nya adalah 1). Dengan sifat seperti ini, maka inverse dari matrik Q adalah transposenya. Q−1 = QT . Matrik Bobot Q, di sisi lain adalah matrik yang berbentuk segitiga atas. Ada pun proses untuk memperoleh Q dan R adalah cara Ortogonalisasi Gramm-Schmidt. Mari kita lihat lagi contoh sebelumnya.
2 5 A= 2 4 . Pertama kita buat dulu vektor referensi atau basis pertama yang berasal dari normalisasi kolom pertama dari A. Dengan demikian:
1 1 1 1 v1 = √ · = √ · 2 2 2 1 1 +1 1 Dengan demikian, kolom pertama matrix A dapat ditulis sebagai
√ √ √ 2 1 1 a1 = = 2 · 2 · √ = 2 2·v1 = 2 2·v1 2 1 2 Dengan kata lain √ √ √ 2 1 1 a1 = = 2 · 2 · √ = 2 2·v1 = 2 2·v1 2 1 2 Selanjutnya, untuk mencari basis v2 , kita reduksi dulu kolom kedua dari A dengan basis v1 , sisanya baru kita normalisasi untuk menghasilkan v2
5 5 1 1 1 1 9 1 a2 = =< , √ > · √ + r = + r 2 1 2 1 2 1 4 4
37
Dengan demikian sisanya r adalah
5 0.5 9 1 r = − = 2 1 4 −0.5 Basis v2 diambil dari normalisasi sisa r.
1 0.5 √ 0.5 1 =√ = 2 v2 = q 2 −1 −0.5 0.52 + (−0.5)2 −0.5 1
Dengan demikian, kolom kedua dari matrik A sekarang dapat kita nyatakan sebagai kombinasi linier dari v1 dan v2 sebagai: √ √ 5 1 0.5 1 9 9 2 1 2 1 = √ + 0.5 √ a2 = = + 2 1 2 2 1 2 −1 4 −0.5
Atau √ 9 a2 = √ · v1 + 0.5 2 · v2 2 Kita kumpulkan dalam satu sistem persamaan untuk a1 dan a2: √ A = a1 a2 = 2 2·v1 + 0 · v2
√ 2 2
= v1 v2 ·
0
√9 2
√ · v1 + 0.5 2 · v2
√ √9 1 1 1 2 2 2 = Q·R √ · √ 2 1 −1 0 0.5 2
√9 2 = √
0.5 2
Dengan
1 1 1 Q= √ 2 1 −1 dan √ 2 2
R=
0
√9 2 √
0.5 2
Di sini: Matrik Q adalah matrik orthonormal; dan matrik R adalah matrik segitiga atas.
1 Faktorisasi QR untuk Over determined system Overdetermined system adalah sistem persamaan linier yang mana jumlah persamaan lebih banyak dari pada jumlah variabel yang tidak diketahui.
38
Sebagai contoh: x + y = 10 2x + y = 15 x + 2y = 30 Overdetermined system dapat terdiri dari set persamaan yang konsisten, sebagai contoh : x + y = 10 2x + y = 15 2x + 2y = 20 Atau set persamaan tidak konsisten x + y = 10 x + y = 11 2x + 2y = 19 Untuk set persamaan yang konsisten, hanya terdapat satu pasangan solusi yang memenuhi semua persamaan. Untuk set persamaan yang tidak konsisten, justru tidak ada nilai yang memenuhi semua persamaan. Solusi terbaik diperoleh dengan mencari nilai ’terbaik’ yang mendekati pemenuhan semua persamaan. Mari kita tinjau set persamaan overdetermined yang tidak konsisten di atas. Atau set persamaan tidak konsisten x + y = 10 x + y = 11 2x + 2y = 19 Secara matrik, dapat kita tulis sebagai:
1 1 10 x 1 1 · = 11 y 2 2 19
39
Penyelesaian Persamaan Underdetermined dengan faktorisai QR
Sekarang mari kita coba menyelesaikan persamaan underdetermined dengan faktorisasi QR. Untuk sederhananya, mari kita lihat contoh sistem persamaan linier berikut. x+y+z = 1 x + y + 2z = 3 Kita susun dalam persamaan matrik
x 1 1 1 1 · y = 1 1 2 3 z
Misalkan
1 1 1 A= 1 1 2 dan
1 p= 3 Maka :
1 1 1 1
x 1 1 · y = 2 3
z
dapat ditulis sebagai
x
A · y = p
z
Ada banyak pilihan solusi untuk sistem persamaan underdetermined tersebut. Salah satunya adalah dengan faktorisasi QR.
40
Kita akan dekomposisi matrik AT , (alih-alih matrik A). Dengan demikian:
1 1 T A = 1 1 1 2 Dengan teknik dekomposisi QR yang telah dibahas sebelumnya, AT dapat dituliskan sebagai :
−0.5774 −0.4082 −0.7071 −1.7321 −2.3094 1 1 T · A = 1 1 = Q · R = 0.5774 −0.4082 0.7071 0 −0.4082 0 0 −0.5774 0.8165 0 1 2
−1.7321 −2.3094 Jika kita pandang matrik R = , maka dapat kita pandang ia 0 −0.4082 0 0 sebagai :
R1 R= O Dengan
−1.7321 −2.3094 R1 = 0 −0.4082 Dan
O= 0 0
Dengan demikian persamaan semula :
x
A · y = p
z
menjadi :
x
· y = p
T T
(A )
z
atau
41
x
· y = p
T
(Q · R)
z
atau
x
T
· y = p
T
R ·Q
z
atau
x
y = (RT
· QT )−1 · p
z
x
y = (QT )−1 · (RT )−1 · p
z
Oleh karena Q adalah matrik orthonormal, maka (QT )−1 = Q, serta
T
R1 (RT )−1 = ( )−1 = ( R1T OT )−1 O
Sebetulnya lebih tepat menyebut (RT )−1 sebagai (RT )+ oleh karena R bukanlah matrik persegi.
2 QR Faktorisasi dengan Transformasi Householder
2.1 Prinsip: Membuat elemen nol pada vektor Jika kita memiliki vektor
x1 X = x2 Maka selalu mungkin untuk mentransformasi X dengan matrik transformasi P sehingga menjadi matrik XB yang memiliki banyak elemen 0.
x0 XB = 0 Dengan kata lain
42
x0 XB = P · X = 0 . Matrik P dapat dipandang sebagai matrik perotasi atau matrik pencerminan. Teknik mencari matrik perotasi diteliti oleh Givens, sedangkan teknik mencari matrik pencerminan diteliti oleh Householder (Alston Householder, 1965). Gambar berikut memperlihatkan teknik pencerminan oleh matrik P. X
Garis cermin g
XB Pencerminan Vektor B dengan garis g, menghasilkan vektor XB yang memiliki beberapa elemen bernilai 0. Pada Pencerminan, panjang vektor XB adalah sama dengan panjang vektor X semula. Operasi pencerminan dapat diwakili matrik P XB =P · X
Householder menurunkan bahwa, jika diberikan suatu vektor X dengan dimensi n,
x 1 x2 X = .. . xn
maka dapat dicari matrik V yaitu
x − |X| 1 x2 V = .. .
xn
yang mana P = In − 2 · V · V T /(V T · V ) Sedemikian sehingga
43
XB = P · X adalah vektor dengan semua elemen 0 kecuali elemen pertama. Dengan kata lain : q XB =
x21 + x22 + ... + x2n 0 .. .
0
Mari kita lihat contoh berikut ini: Misalkan
2
X
2 = 1
4
Dengan demikian : |X| =
q
22 + 22 + 12 + 42 =
√ 25 = 5
Dengan demikian
x − |X| 2 − 5 −3 1 x2 2 2 V = .. = = 1 1 .
xn
4
4
Dengan demikian, Matrik Pencerminan Householder dapat dihitung dengan :
1 0 P = In − 2 · V · V T /(V T · V ) = 0 0
0 1 0 0
44
0 0 1 0
−3 2 · −3 2 1 4 1 4
0 0 −2· 0 1
−3 2 −3 2 1 4 · 1 4
1 0 = 0 0
0 1 0 0
0 0 1 0
−3 2 · −3 2 1 4 1 4
0 0 −2· 0 1
−3 2 −3 2 1 4 · 1 4
9 −6 −3 −12 −6 4 2 8 −3 2 1 4 −12 8 4 16
1 0 = 0 0
0 1 0 0
0 0 1 0
0 0 −2· 0 1
0 1 0 0
0 0 1 0
9 −6 −3 −12 0 −6 4 2 8 0 1 − · 15 −3 2 1 4 0 −12 8 4 16 1
1 0 = 0 0
(−3)2 + 22 + 12 + 42
0.4 0.4 0.2 0.8 0.4 0.7333 −0.1333 −0.5333 = 0.2 −0.1333 0.9333 −0.2667 0.8 −0.5333 −0.2667 −0.0667 Sekarang kita test matriks P ini dengan mengalikannya dengan X semula. Kita peroleh :
0.4 0.4 0.2 0.8 2 0.4 0.7333 −0.1333 −0.5333 2 · PX = 0.2 −0.1333 0.9333 −0.2667 1 0.8 −0.5333 −0.2667 −0.0667 3 0.4 0.4 0.2 0.8 2 0.4 0.7333 −0.1333 −0.5333 2 · PX = 0.2 −0.1333 0.9333 −0.2667 1 0.8 −0.5333 −0.2667 −0.0667 3
45
5
0 = 0
0
Seperti yang diharapkan yaitu: √
PX
=
22 + 22 + 12 + 42 0 0 0
2.2 Pemaktoran Matrik ke komponen Q dan R Sebelum kita lanjutkan dekomposisi matrik atau pemaktoran matrik. Kita bahas dulu cara bagaimana menjadikan matrik sebarang A, menjadi matrik segitiga atas AS . Ilustrasi sederhana diberikan pada gambar berikut.
X 2
5
1
5
2
2 2
4
P1
5
y1
0 0
y2 y3
0
y4
P2
5
y1
0 0
z2 0
0
0
Gambar 1. Tahap pengubahan suatu matrik X sebarang ke matrik segitiga atas Mula-mula kita memiliki suatu matrik X seperti gambar matrik paling kiri dari 2 1 Gambar 1 tersebut. Pandang kolom paling kiri yang berisi , dengan prinsip 2 4 sebelumnya, kita dapat mencari matrik V, kemudian matrik P1 sehingga P1 dikalikan 5 0 dengan matriks X kita peroleh kolom pertama matrik tengah pada gambar yaitu . 0 0
46
y 1 y2 Kolom kedua dari matrik tengah pada gambar adalah yang merupakan hasil y3 y4
5
perkalian P1 dengan kolom kedua dari matrik X yaitu
5 . 2
2
y 2 Tugas kita selanjutnya adalah mentransformasi bagian kolom kedua yaitu y3 y4
z 2 menjadi bentuk 0 . 0
y z 2 2 Proses mengubah y3 menjadi bentuk 0 tentu saja mudah, karena kita y4 0
q
y − (y22 + y32 + y42 ) 2 tinggal mencari matrik V2 = kemudian mencari PH2 = I − y3 y4
y z 2 2 T T 2V2 V2 /(V2 V2 ) . Terakhir, kita kalikan PH2 dengan y3 untuk memperoleh 0 . y4 0 Bisakah proses ini kita modifikasi sehingga proses ini menjadi mengalikan suatu 5 y 1 0 y2 . matrik P2 dengan matrik tengah yaitu 0 y3 0 y4
5 0 Dengan kata lain, mengalikan P2 dengan 0 0
y1 y2 tidak mengubah kolom pertama y3 y4
5 y1 0 y2 . dan baris pertama dari 0 y3 0 y4 Jawaban atas permasalahan ini adalah dengan menyusun matrik P2 dari PH2 dengan cara :
47
1 0 P2 = 0 PH2 Sebagai contoh, jika
1 0 0 0 1 2 P2 = 0 −1 1 0 5 3
0 2 1 2
1 2 2 PH2 = −1 1 1 5 3 2 Maka
Dengan teknik sederhana ini, maka perkalian dengan P2 tidak mengganggu baris pertama dan kolom pertama dari matriks tengah.
2.3 Contoh Ilustrasi Mari kita diagonal ataskan matrik pada contoh pada Gambar 1 sebelumnya:
2 5 2 5 X = 1 −2 4 2 . Kita tahu bahwa untuk menciptakan banyak 0 pada kolom pertama, kita gunakan matrik Householder sebelumnya yaitu :
0.4 0.4 0.2 0.8 0.4 0.7333 −0.1333 −0.5333 P1 = 0.2 −0.1333 0.9333 −0.2667 0.8 −0.5333 −0.2667 −0.0667 Kita kalikan dengan X, kita perloleh:
0.4
P1 X
0.4 0.2 0.8 2 5 2 5 0.7333 −0.1333 −0.5333 · 1 −2 −0.1333 0.9333 −0.2667 0.8 −0.5333 −0.2667 −0.0667 4 2
0.4 = 0.2
48
5 6 0 4.3 = 0 1.67 0 0.67
4.3 . Kita pilih V2 = Selanjutnya kita nol-kan kolom kedua. Kita punya : 1.67 0.67 √ 2 + 1.672 + 0.672 4.3 − −0.357 4.3 = 1.67 1.67 0.67 0.67 Selanjutnya kita hitung PH2 :
−0.357 1.67 · −0.357 1.67 0.67 0.67
1 0 0 T T PH2 = I − 2V2 V2 /(V2 V2 ) = 0 1 0 −2· 0 0 1
−0.357 −0.357 1.67 0.67 · 1.67 0.67
0.923 0.355 0.0.142 = 0.355 −0.659 −0.663 0.142 −0.663 0.735
1 0 Sekarang kita terapkan trik sebelumnya : P2 = , kita peroleh : 0 PH2
1 0 0 0 0 0.923 0.355 0.0.142 P2 = 0 0.355 −0.659 −0.663 0 0.142 −0.663 0.735 Dengan demikian :
1 0 0 0 5 6 5 6 5 6 0 0.923 0.355 0.0.142 0 4.3 0 4.3 0 4.69 · = = P2 (P1 X) = 0 0.355 −0.659 −0.663 0 1.67 0 1.67 0 0 0 0.142 −0.663 0.735 0 0.67 0 0.67 0 0 Dengan demikian hasil akhir adalah:
49
5 6 0 4.69 P2 (P1 X) = QX = R = 0 0 0 0 Dengan Q = P2 P1 . Oleh karena Q adalah ortogonal, maka Q− 1=QT . Dengan demikian : QX = R memberikan X = QT R Dengan kata lain, X bisa direpresentasikan sebagai perkalian antara matrik orthonormal Q dan matrik segitiga atas R.
2.4 QR dekomposisi dengan Column Pivoting Suatu matrik A yang dapat dipandang sebagai kumpulan kolom-kolom (vektor a1 , a2 , ... , aN ): a1 a2
A=
aN
···
Kita dapat menghitung panjang euclidean (norm l2) dari setiap vektor (a1 , a2 , ... , aN ) tersebut, dan mengambil vektor dengan panjang euclidean terbesar, dan meletakkan pada kolom pertama. Sebagai contoh: −1 1 1 Misalkan A=−0.5 0.6 0.4 .
−1 1 1.02 Panjang dari setiap kolom adalah : Kolom 1:
−1 q
−0.5 = (−1)2 + (−0.5)2 + (−1)2 = 1.5.
−1 2
50
Kolom
1
0.6
1
2: =
q
12 + (0.6)2 + 12 = 1.536.
2
Kolom 3:
1 q
0.4 = 12 + (0.4)2 + 12
1.02
= 1.4698.
2
Di sini kita melihat bahwa kolom kedua memiliki panjang euclidean terbesar yaitu 1.536, dengan demikian kita pindahkan kolom kedua ini ke kolom pertama, menjadi, katakanA2 . 1 −1 1 A2 =0.6 −0.5 0.4 .
1 −1 1.02 Selanjutnya, dekomposisi QR dilakukan pada A2 . 1 −1 1 −0.65 0.27 −0.70 −1.536 1.497 −1.471 0.6 −0.5 0.4 = −0.39 −0.92 · = QR 0.0 0 −0.092 0.189 1 −1 1.02 −0.65 0.27 0.70 0 0 0.014 Setelah tadi kita melihat bahwa kolom kedua adalah yang memiliki panjang euclidean terbesar, kita akan ambil kolom berikutnya yang terbesar. Untuk keperluan ini, kita lihat Matrik Hasil R yaitu :
−1.536 1.497 −1.471 R= 0 −0.092 0.189 0 0 0.014 Kolom pertama berasal dari kolom dengan norm terbesar sebelumnya, jadi kita tidak tinjau lagi kolom pertama ini. Kita perhatikan kolom kedua dan ketiga. Baris pertama juga kita abaikan, karena proses diagonalisasi tidak mengubah nilai dari matrik ini. Jadi kita tinjau sisanya yaitu R22 yang tersusun dari baris 2 dan 3 serta kolom 2 dan 3 dari matrik R.
−0.092 0.189 R22 = 0 0.014 Kita hitung panjang euclidean masing-masing kolom dari R22 kita peroleh : Kolom pertama :
−0.092
= 0.092
0 2
51
Kolom kedua :
0.189
0.014
= 0.1895
2
Dengan demikian kolom kedua harus kita pindahkan ke kolom pertama dari R22 . Tapi jika kita kembalikan ke asalnya, kolom kedua dari R22 berasal dari kolom 1 dari Matrik A, sedangkan kolom 2 dari R22 berasal dari kolom ke 3 dari matrik A. Jika kita pandang matrik A sekali lagi yang terdiri dari tiga kolom, maka KOLOM 2 adalah yang paling signifikan panjang euclideannya, setelah itu KOLOM 3 (setelah kita lakukan analisis pada R22 ) dan terakhir KOLOM 1. Jika matrik A kita ubah urutannya dengan cara ini maka kita peroleh : -1
1
-0.5 0.6
A=
-1
1
1 0.4
permutasi kolom 2, 3, 1
1.02
1
1
-1
0.6
0.4
-0.5
1
1.02
-1
= AB
Matrik yang telahdipermutasi (AB ) yang kemudian dilakukan dekomposisi QR: 1 1 −1 −0.6509 0.2228 −0.7257 0.6 0.4 −0.5 = −0.3906 −0.9180 0.0685 · 1 1.02 −1 −0.6509 0.3280 0.6846
−1.5362 −1.4711 1.4972 = QB · R B 0 0.1902 −0.0918 0 0 0.0068 Teknik mempermutasikan kolom dari A sebelum QR dekomposisi ini disebut dengan dekomposisi QR dengan column pivoting. Penyelesaian persamaan linier A · x = y dilakukan dengan mendekomposisi AB = QB · RB . Solusi akhir disusun kembali sesuai dengan permutasi yang dilakukan.
2.5 Penyelesaian masalah sistem persamaan linier Underdetermined Tinjau sistem persamaan berikut: −0.5x1 + 0.6x2 + 0.4x3 = 1.2 dan x1 + x2 + x3 = 3 Sistem persamaan tersebut memiliki dua persamaan dengan tiga variabel tidak diketahui. Akan ada banyak solusi dari persamaan tersebut.
52
Dua solusi akan kita hitung dengan QR dekomposisi. Solusi pertama adalah QR langsung. Solusi kedua dengan QR dan pivot kolom. Sistem persamaan tersebut dalam matrik dapat dituliskan sebagai:
x 1 1.2 −0.5 0.6 0.4 · x2 = 3 1 1 1 x3
x 1 1.2 −0.5 0.6 0.4 =y = A; x2 = x Misalkan 3 1 1 1 x3 Maka :
Ax = y Kita dekomposisi A dengan melakukan column pivoting, kita peroleh urutan permutasi adalah : 2, 1, 3. Setelah kita permutasikan, kita peroleh matrik AB :
0.6 −0.5 0.4 AB = 1 1 1 Dekomposisi QR pada AB diperoleh:
0.6 −0.5 0.4 −0.5145 −0.8575 −1.1662 −0.6002 −1.0633 = · = QB ·RB AB = −0.8575 0.5145 0 0.9432 0.1715 1 1 1 Kembalikan ke persamaan semula (Ax=y −− > QRx=y):
x 2 −0.5145 −0.8575 −1.1662 −0.6002 −1.0633 1.2 · · x1 = 3 −0.8575 0.5145 0 0.9432 0.1715 x3
−1 x 2 −1.1662 −0.6002 −1.0633 −0.5145 −0.8575 1.2 · x1 = · 0 0.9432 0.1715 −0.8575 0.5145 3 x3
.
x 2 Di sini urutan x adalah x1 untuk menyesuaikan permutasi 2, 1, 3 pada A x3 sebelumnya.
53
−1
T
−0.5145 −0.8575 −0.5145 −0.8575 Karena orthonormal, maka = −0.8575 0.5145 −0.8575 0.5145 Setelah ruas kanan dihitung dan disederhanakan, kita peroleh:
x 2 −3.1899 −1.1662 −0.6002 −1.0633 · x1 = 0.5145 0 0.9432 0.1715 x3
Oleh karena kolom R telah diurutkan dari norm euclidean terbesar ke terkecil, maka dampak dari kolom ke-3 adalah paling minimal. Oleh karena itu kita abaikan kolom ini, yang berkorespondensi dengan membuat x3 = 0, kita peroleh penyederhanaan menjadi:
−1.1662 −0.6002 x2 −3.1899 · = 0 0.9432 x1 0.5145 Atau Tinjau sistem persamaan berikut: −1.1662x2 − 0.6002x1 = −3.1899 dan 0x2 − 0.9432x1 = 0.5145 Selesaikan dari baris paling bawah: diperoleh : 0.5145 = 0.545 0.9432 Substitusikan pada persamaan baris pertama diperoleh : x1 =
−1.1662x2 − 0.6002 · 0.545 = −3.1899 atau −1.1662x2 = −2.862791 atau x2 = −2.4548 Dengan demikian, solusi dari : −0.5x1 + 0.6x2 + 0.4x3 = 1.2 dan
54
x1 + x2 + x 3 = 3 adalah
0.545 x 1 x2 = 2.4548 0 x3 Dengan sudut pandang variabel dari yang memberikan kontribusi besar sampai variabel yang memberikan kontribusi kecil. Solusi ini sesuai dengan operator backslash (\) dari Matlab.
55
