Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Greedy Algorithms for Distributed Compressed Sensing
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
2014 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Compressed sensing (CS) is a recently invented sub-sampling technique that utilizes sparsity in full signals. Most natural signals possess this sparsity property. From a sub-sampled vector, some CS reconstruction algorithm is used to recover the full signal. One class of reconstruction algorithms is formed by the greedy pursuit, or simply greedy, algorithms, which is popular due to low complexity and good performance. Meanwhile, in sensor networks, sensor nodes monitor natural data for estimation or detection. One application of sensor networking is in cognitive radio networks, where sensor nodes want to estimate a power spectral density. The data measured by different sensors in such networks are typically correlated. Another type are multiple processor networks of computational nodes that cooperate to solve problems too difficult for the nodes to solve individually.

In this thesis, we mainly consider greedy algorithms for distributed CS. To this end, we begin with a review of current knowledge in the field. Here, we also introduce signal models to model correlation and network models for simulation of network. We proceed by considering two applications; power spectrum density estimation and distributed reconstruction algorithms for multiple processor networks. Then, we delve deeper into the greedy algorithms with the objective to improve reconstruction performance; this naturally comes at the expense of increased computational complexity. The main objective of the thesis is to design greedy algorithms for distributed CS that exploit data correlation in sensor networks to improve performance. We develop several such algorithms, where a key element is to use intuitive democratic voting principles. Finally, we show the merit of such voting principles by probabilistic analysis based on a new input/output system model of greedy algorithms in CS.

By comparing the new single sensor algorithms to well known greedy pursuit algorithms already present in the literature, we see that the goal of improved performance is achieved. We compare complexity using big-O analysis where the increased complexity is characterized. Using simulations we verify the performance and confirm complexity claims. The complexity of distributed algorithms is typically harder to analyze since it depends on the specific problem and network topology. However, when analysis is not possible, we provide extensive simulation results. No distributed algorithms based on the signal-models used in this thesis were so far available in the literature. Therefore, we compare our algorithms to standard single-sensor algorithms, and our results can then easily be used as benchmarks for future research. Compared to the stand-alone case, the new distributed algorithms provide significant performance gains. Throughout the thesis, we strive to present the work in a smooth flow of algorithm design, simulation results and analysis.

Abstract [sv]

Compressed sensing (CS) är en nyutvecklad teknik som utnyttjar gleshet i stora undersamplade signaler. Många intressanta signaler besitter dessa glesa egenskaper. Utifrån en undersamplad vektor återskapar CS-algoritmer hela den sökta signalen. En klass av rekonstruktionsalgoritmer är de så kallade giriga algoritmerna, som blivit populära tack vare låg komplexitet och god prestanda. CS kan användas i vissa typer av nätverk för att detektera eller estimera stora signaler. En typ av nätverk där detta kan göras är i sensornätverk för kognitiv radio, där man använder sensorer för att estimera effektspektrum. Datan som samplas av de olika sensorerna i sådana nätverk är typiskt korrelerad. En annan typ av nätverk är multiprocessornätverk bestående av distribuerade beräkningsnoder, där noderna genom samarbete kan lösa svårare problem än de kan göra ensamma.

Avhandlingen kommer främst att behandla giriga algoritmer för distribuerade CS-problem. Vi börjar med en överblick av nuvarande kunskap inom området. Här introducerar vi signalmodeller för korrelation och nätverksmodeller som används för simulering i nätverk. Vi fortsätter med att studera två tillämpningar; estimering av effektspektrum och en distribuerad återskapningsalgoritm för multiprocessornätverk. Därefter tar vi ett djupare steg i studien av giriga algoritmer, där vi utvecklar nya algoritmer med förbättrad prestanda, detta till priset av ökad beräkningskomplexitet. Huvudmålet med avhandlingen är giriga algoritmer för distribuerad CS, där algoritmerna utnyttjar datakorrelationen i sensornätverk. Vi utvecklar flera sådana algoritmer, där en huvudingrediens är att använda demokratiska röstningsalgoritmer. Vi analyserar sedan denna typ av röstningsalgoritmer genom att introducera en ingång/utgångs modell. Analysen visar att algoritmerna ger bra resultat.

Genom att jämföra algoritmer för enskilda sensorer med redan befintliga algoritmer i litteraturen ser vi att målet med ökad prestanda uppnås. Vi karaktäriserar också komplexiteten. Genom simulationer verifierar vi både prestandan och komplexiteten. Att analysera komplexitet hos distribuerade algoritmer är generellt svårare eftersom den beror på specifik signalrealisation, nätverkstopologi och andra parametrar. I de fall där vi inte kan göra analys presenterar vi istället genomgående simuleringsresultat. Vi jämför våra algoritmer med de vanligaste algoritmerna för enskilda sensorsystem, och våra resultat kan därför enkelt användas som referens för framtida forskning. Jämfört med prestandan för enskilda sensorer visar de nya distribuerade algoritmerna markant förbättring.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. , ix, 174 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2014:022
National Category
Telecommunications Signal Processing
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-144907ISBN: 978-91-7595-140-9 (print)OAI: oai:DiVA.org:kth-144907DiVA: diva2:715302
Public defence
2014-05-21, F3, Lindstedtsvägen 26 (2 tr), Kungl. Tekniska högskolan, Stockholm, 14:15 (English)
Opponent
Supervisors
Available from: 2014-05-06 Created: 2014-05-02 Last updated: 2014-05-06Bibliographically approved

Open Access in DiVA

Thesis(1753 kB)1251 downloads
File information
File name FULLTEXT01.pdfFile size 1753 kBChecksum SHA-512
82483b66917d0856a19f6432e84703aa5b3571b1d0e17bb22febe93ac6443aff7e634b62c8b559562a8c24c6d641c883ca9015e4108fdf3a293179c57428ca52
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Sundman, Dennis
By organisation
Communication TheoryACCESS Linnaeus Centre
TelecommunicationsSignal Processing

Search outside of DiVA

GoogleGoogle Scholar
Total: 1251 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 888 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf