Sažeto uzorkovanje

master's thesis

• Author: Marco Hrlić
• Mentor: Damir Bakić (mentor)
• Committee member: Damir Bakić (predsjednik povjerenstva)
• Committee member: Boris Guljaš (član povjerenstva)
• Committee member: Tomislav Berić (član povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu upoznali smo se s matematičkim temeljima teorije sažetog uzorkovanja. Rješavali smo problem rekonstrukcije vektora $\vec{x} \in \mathbb{C}^N$ iz vektora mjerenja $\vec{y} = \vec{Ax}$ gdje je $\vec{A} \in \mathbb{C}^{m \times N}$. U slučaju da je $N = m$ za rekonstrukciju je dovoljno riješiti kvadratni sustav linearnih jednadžbi. Ako je $m < N$, klasična teorija linearne algebre kaže da ovakvi sustavi mogu imati beskonačno rješenja. No, uz dodatni uvjet rijetkosti... More vektora $\vec x$ pokazali smo da je rekonstrukcija moguća i štoviše postoje efikasni algoritmi za rješenje. Prvo poglavlje započinje uvodom u osnovne pojmove teorije rijetkih vektora. Dali smo definiciju rijetkih vektora, izveli smo ocjene za $\ell_p$-grešku najbolju $s$-rijetke aproksimacije vektora $\vec x$ i dali dva načina kako se mogu definirati kompresibilni vektori. To je od praktične koristi pošto u primjeni rijetko rukujemo pravim rijetkim vektorima, već su to uglavnom kompresibilni vektori. Zatim smo istražili koji je minimalni broj mjerenja $m$ potrebnih za rekonstrukciju, te pokazujemo kako $\ell_0$-minimizacija $(P_0)$ daje rješenje problema sažetog uzorkovanja. Nažalost minimizacija $\ell_0$-norme je nekonveksan, a uz to i NP-težak problem, što smo pokazali tako da smo poznati NP-težak problem pokrivača tročlanim skupovima reducirali na $(P_0)$. U drugom poglavlju dajemo pregled ostalih, efikasnih algoritama za rekonstrukciju. Ti algoritmi mogu se u grubo podijeliti na optimizacijske, greedy i granične metode. Kod optimizacijskih algoritama najvažniji je BP (eng. basis pursuit) algoritam ili $\ell_1$-minimizacija. Njega zapravo možemo shvatiti kao konveksnu relaksaciju problema $(P_0)$. Nadalje, opisujemo OMP i CoSaMP greedy algoritme, te BT, IHT, HTP granične metode. Treće poglavlje posvećeno je $\ell_1$-minimizaciji. Upoznajemo se sa svojstom nul-prostora matrice $\vec A$ te pokazujemo kako je ono dovoljan i nužan uvjet za uspješnu rekonstrukciju vektora $\vec x$ $\ell_1$-minimizacijom. Nadalje, uvodimo pojmove stabilnosti i robusnosti rekonstrukcijske metode. Neformalno, ta dva svojstva govore da se rekonstrukcijska metoda dobro ponaša s obzirom na defekte rijetkosti i na greške mjerenja. Uz ojačano svojstvo nul-prostora pokazujemo da je $\ell_1$-minimizacija stabilna i robusna. U četvrtom poglavlju uvodimo koherenciju, koju možemo shvatiti kao mjeru kvalitete matrice rekonstrukcije. Slijede rezultati i ocjene vezane uz koherenciju te dajemo eksplicitnu konstrukciju određenih matrica male koherencije. Zatim analiziramo uz koje uvjete na koherenciju algoritmi iz drugog poglavlja postižu egzaktnu rekonstrukciju. U petom poglavlju dajemo novu mjeru kvalitete matrice $\vec A$, svojstvo restriktivne izometričnosti. Ona rješava nedostatke koherencije, tj. omogućuje analizu algoritama za velike vrijednosti rijetkosti $s$. Isto kao kod koherencije provodimo analizu algoritama i pokazujemo uz koje uvjete ti algoritmi postižu stabilnu i robusnu rekonstrukciju. Valja napomenuti da ovaj rad nije iscrpni pregled teorije sažetog uzorkovanja. Naime, pokazuje se da je konstrukcija eksplicitnih matrica s dovoljno malim konstantama restriktivne izometričnosti težak problem, koji nije riješen. Veliki napredak napravili su Terence Tao i Emmanuel Candes u [2], gdje su pokazali da slučajne Gaussove matrice zadovoljavaju svojstvo restriktivne izometričnosti s velikom vjerojatnošću. To je otvorilo put stohastičkoj teoriji i slučajnim matricama u teoriju sažetog uzorkovanja. Less

Abstract (english)

In this thesis we cover the mathematical foundations of the theory of compressive sensing. The problem in focus is the reconstruction of the vector $\vec{x} \in \mathbb{C}^N$ from the measurement vector $\vec{y} = \vec{Ax}$, where $\vec{A} \in \mathbb{C}^{m \times N}$. Given that $N = m$, it is enough to solve a square system of linear equations. If $m < N$, the classical theory of linear algebra tells us that such systems can have a infinite number of solutions. However,... More if we assume that the vector $\vec x$ is sparse, we are able to show that the reconstruction is not only possible, but efficient reconstruction algorithms exist. First chapter gives an introduction to the theory of sparse vectors. We define the notion of sparsity, derive the $\ell_p$ bound for the best $s$-term sparse approximation of a vector $\vec x$ and give two ways of defining compressible vectors. Which is of practical use because compressible vectors are much more common than perfectly sparse vectors in real world applications. Next, we investigate the minimal number $m$ of measurements necessary for a perfect reconstruction and we see how the $\ell_0$-minimization $(P_0)$ naturally arises as a reconstruction strategy. Unfortunately, $\ell_0$-minimization is non-convex and additionally a NP-hard problem. We show this fact by reducing the well known NPhard problem of covering by 3-sets to the problem of $(P_0)$-minimization. In the second chapter we give a summary of efficient reconstruction algorithms, which can be divided into three categories: optimization methods, greedy methods and threshold-based methods. In the optimization methods category the most important is the basis pursuit algorithm or $\ell_1$-minimization. We can think of it as a convex relaxation of the $(P_0)$ problem. Furthermore, we give a description of the OMP and CoSaMP greedy algorithms, and BT, IHT, HTP thresholding-based methods. The third chapter is dedicated to the $\ell_1$-minimization. We study the null-space property of the matrix $\vec A$ and show how it ensures a successful reconstruction via the $\vec x$ $\ell_1$-minimization. We introduce the definition of stability and robustness of a reconstruction method and prove how with a stronger version of the null-space property, $\ell_1$-minimization is both stable and robust. In chapter number four, we give the definition of coherence, which can be thought of as a reconstruction matrix $\vec A$ quality. We derive some bounds and give an explicit construction of matrices with small coherence. Next, we analyse the conditions for coherence under which the reconstruction algorithms give a successful reconstruction. In the fifth chapter we introduce the notion of restricted isometry property, which is in fact a new quality measure for the matrix $\vec A$, and this enables us to study the reconstruction algorithms for large values of sparsity $s$. Same as with the coherence, we analyse the reconstruction algorithms with regard to the restricted isometry property. We should note that this thesis is not covering the whole theory of compressive sensing as it turns out that the explicit construction of matrices with a small restricted isometry constant is a hard problem which still hasn’t been resolved. A big step forward has been made by Terence Tao and Emmanuel Candes in [2], where they have shown that random Gauss matrices satisfy the restricted isometry property with a high probability and introduced stohastics into the theory of compressive sensing. Less

• Keywords: teorija sažetog uzorkovanja; rekonstrukcija vektora; rijetki vektori; kompresibilni vektori
• Keywords (english): theory of compressive sensing; vector reconstruction; sparse vectors; compressible vectors
• Language: croatian
• URN:NBN: urn:nbn:hr:217:865897
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-01-30 12:03:34