Open this publication in new window or tab >>2016 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]
Many scientific and engineering problems require us to process measurements and data in order to extract information. Since we base decisions on information,it is important to design accurate and efficient processing algorithms. This is often done by modeling the signal of interest and the noise in the problem. One type ofmodeling is Compressed Sensing, where the signal has a sparse or low-rank representation. In this thesis we study different approaches to designing algorithms for sparse and low-rank problems.
Greedy methods are fast methods for sparse problems which iteratively detects and estimates the non-zero components. By modeling the detection problem as an array processing problem and a Bayesian filtering problem, we improve the detection accuracy. Bayesian methods approximate the sparsity by probability distributions which are iteratively modified. We show one approach to making the Bayesian method the Relevance Vector Machine robust against sparse noise.
Bayesian methods for low-rank matrix estimation typically use probability distributions which only depends on the singular values or a factorization approach. Here we introduce a new method, the Relevance Singular Vector Machine, which uses precision matrices with prior distributions to promote low-rank. The method is also applied to the robust Principal Component Analysis (PCA) problem, where a low-rank matrix is contaminated by sparse noise.
In many estimation problems, there exists theoretical lower bounds on how well an algorithm can perform. When the performance of an algorithm matches a lowerbound, we know that the algorithm has optimal performance and that the lower bound is tight. When no algorithm matches a lower bound, there exists room for better algorithms and/or tighter bounds. In this thesis we derive lower bounds for three different Bayesian low-rank matrix models.
In some problems, only the amplitudes of the measurements are recorded. Despitebeing non-linear, some problems can be transformed to linear problems. Earlier works have shown how sparsity can be utilized in the problem, here we show how the low-rank can be used.
In some situations, the number of measurements and/or the number of parametersis very large. Such Big Data problems require us to design new algorithms. We show how the Basis Pursuit algorithm can be modified for problems with a very large number of parameters.
Abstract [sv]
Många vetenskapliga och ingenjörsproblem kräver att vi behandlar mätningar och data för att finna information. Eftersom vi grundar beslut på information är det viktigt att designa noggranna och effektiva behandlingsalgoritmer. Detta görs ofta genom att modellera signalen vi söker och bruset i problemet. En typ av modellering är Compressed Sensing där signalen har en gles eller lågrangs-representation.I denna avhandling studerar vi olika sätt att designa algoritmer för glesa och lågrangsproblem.
Giriga metoder är snabba metoder för glesa problem som iterativt detekterar och skattar de nollskilda komponenterna. Genom att modellera detektionsproblemet som ett gruppantennproblem och ett Bayesianskt filtreringsproblem förbättrar vi prestandan hos algoritmerna. Bayesianska metoder approximerar glesheten med sannolikhetsfördelningar som iterativt modifieras. Vi visar ett sätt att göra den Bayesianska metoden Relevance Vector Machine robust mot glest brus.
Bayesianska metoder för skattning av lågrangsmatriser använder typiskt sannolikhetsfördelningar som endast beror på matrisens singulärvärden eller en faktoriseringsmetod. Vi introducerar en ny metod, Relevance Singular Vector Machine, som använder precisionsmatriser med a-priori fördelningar för att införa låg rang. Metoden används också för robust Principal Komponent Analys (PCA), där en lågrangsmatris har störts av glest brus.
I många skattningsproblem existerar det teoretiska undre gränser för hur väl en algoritm kan prestera. När en algoritm möter en undre gräns vet vi att algoritmen är optimal och att den undre gränsen är den bästa möjliga. När ingen algoritm möter en undre gräns vet vi att det existerar utrymme för bättre algoritmer och/eller bättre undre gränser. I denna avhandling härleder vi undre gränser för tre olika Bayesianska lågrangsmodeller.
I vissa problem registreras endast amplituderna hos mätningarna. Några problem kan transformeras till linjära problem, trots att de är olinjära. Tidigare arbeten har visat hur gleshet kan användas i problemet, här visar vi hur låg rang kan användas.
I vissa situationer är antalet mätningar och/eller antalet parametrar mycket stort. Sådana Big Data-problem kräver att vi designar nya algoritmer. Vi visar hur algoritmen Basis Pursuit kan modifieras när antalet parametrar är mycket stort.
Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2016. p. 204
Series
TRITA-EE, ISSN 1653-5146 ; 2016:087
National Category
Signal Processing
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-191139 (URN)978-91-7729-044-5 (ISBN)
External cooperation:
Public defence
2016-09-14, F3, Lindstedtsvägen 26, Stockholm, 10:15 (English)
Opponent
Supervisors
Note
QC 20160825
2016-08-252016-08-242022-06-22Bibliographically approved