Sparse recovery algorithms for streaming and multidimensional signals

Abstract

<div lang="en" class="abs"><p class="abs_header">Abstract</p><p>As the world is moving toward the era of big data, when a system will accumulate and process an immense amount of information, the cost and complexity of the acquisition and processing of high dimensional data is a critical issue to be addressed. In this respect, compressive sensing (CS), with its capability of utilizing sub-Nyquist sampling to recover a signal of interest, may play a vital role in addressing this problem. In this thesis, we develop sparse recovery algorithms to reconstruct streaming signals and multi-dimensional signals from compressive measurements.</p><p>First, we address the problem of reconstructing a streaming signal from compressive, streaming measurements. We utilize a lapped transform (LT) for the sparse representation of the streaming signal to reduce the blocking artifacts. To reconstruct the signal, we develop a progressive reconstruction algorithm based on sliding window processing. The recovery algorithm, which is based on sparse Bayesian learning (SBL), utilizes the preliminary information from the preceding processing window to improve the performance of signal reconstruction. Furthermore, we derive fast update formulae and propose a warm-start procedure to reduce the computational cost of the novel SBL algorithm. Next, we extend the solution method for a 2-dimensional scenario, in which we reconstruct an image from block compressive sensing (BCS) measurements. The results show that the novel SBL based sliding window method provides a more visually pleasing image without using any post-processing techniques.</p><p>We then address the problem of recovering an image from compressive measurements. Unlike the traditional image recovery algorithms, we utilize the total variation (TV) minimization and the sparse representation of the image in a given transform to improve the reconstruction performance of the image recovery algorithm. Later, we extend this work to a multiple bases scenario, as many natural signals may have compressible representations in different transforms rather than having a single sparse representation. For these scenarios, we modify the TV minimization problem by introducing an <em>l</em>₁-norm penalty. To solve these <em>l</em>₁-regularized TV minimization problems we propose customized interior-point methods by efficiently solving the Newton systems.</p></div>

<div lang="fi" class="abs"><p class="abs_header">Tiivistelmä</p><p>Maailma on siirtymässä kohti aikakautta, jossa järjestelmät keräävät ja käsittelevät valtavan määrän tietoa. Tällöin tiedon hankkimisen kustannukset ja monimutkaisuus, sekä korkeaulotteisen datan käsittely tulevat kriittisiksi reunaehdoiksi. Yksi ratkaisun tarjoaja on pakattu havainta (compressed sensing, CS), joka mahdollistaa alinäytteistetyn signaalin rekonstruktion. Tässä työssä kehitetään algoritmeja jatkuva-aikaisten ja moniulotteisten harvojen signaalien rekonstruktioon pakatuista mittauksista.</p><p>Ensin käsitellään jatkuva-aikaisten signaalien rekonstruktiota pakatuista, jatkuva-aikaisista mittauksista. Ongelmassa hyödynnetään lapped transform -menetelmää jatkuva-aikaisen signaalin harvuuden esittämiseksi, joka vähentää signaalireunojen vääristymiä. Signaalin rekonstruktioon kehitetään progressiivinen, liukuvaan ikkunaan perustuva algoritmi. Algoritmi perustuu harvojen signaalien Bayes-menetelmään (sparse Bayesian learning, SBL), joka hyödyntää edeltävien ikkunoiden estimaatteja nykyisen signaalilohkon rekonstruktiossa. Lisäksi johdetaan menetelmä signaaliestimaatin nopealle päivitykselle edellisestä ratkaisusta SBL-algoritmin laskennallisten kustannusten vähentämiseksi. Menetelmä laajennetaan kaksiulotteiseen tapaukseen, jossa kuvien rekonstruktio tapahtuu lohkoittain otetuista pakatuista mittauksista. Tulokset osoittavat, että uusi SBL-pohjainen liukuvan ikkunan menetelmä tarjoaa visuaalisesti miellyttävän kuvan ilman jälkikäsittelyä.</p><p>Seuraavaksi käsitellään kuvan rekonstruktiota pakatuista mittauksista. Työssä kehitetään uudenlainen total variation (TV) -minimointia ja kuvamuunnoksen harvaa esitystä hyödyntävä rekonstruktioalgoritmi suorituskyvyn parantamiseksi. Koska luonnossa esiintyvät signaalit voidaan usein esittää tehokkaasti eri muunnoksilla, algoritmi laajennetaan hyödyntämään useaa rinnakkaista signaalimuunnosta. Tässä mallissa TV-algoritmia muokataan lisäämällä <em>l</em>₁-normiin perustuva sakkotermi ja ehdotetaan räätälöity menetelmä optimointiongelman ratkaisemiseksi.</p></div>