TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. On the parallel reconstruction from pooled data
 
Options

On the parallel reconstruction from pooled data

Publikationstyp
Conference Paper
Date Issued
2022
Sprache
English
Author(s)
Gebhard, Oliver  
Hahn-Klimroth, Max  
Kaaser, Dominik 
Data Engineering E-19  
Loick, Philipp  
Institut
Data Engineering E-19  
TORE-URI
http://hdl.handle.net/11420/15129
Start Page
425
End Page
435
Citation
Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022 (): 425-435 (2022)
Contribution to Conference
36th IEEE International Parallel & Distributed Processing Symposium, IPDPS 2022  
Publisher DOI
10.1109/IPDPS53621.2022.00048
Scopus ID
2-s2.0-85136335939
Publisher
IEEE
In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal sigmain 0, 1n, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that VertsigmaVert₁= o(n) our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct s with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.
Subjects
Information Theory
Phase Transitions
Pooled Data
Reconstruction
Sparse Signal
DDC Class
004: Informatik
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback