The sparse recovery problem aims to reconstruct a high-dimensional sparse signal from its low-dimensional measurements given a carefully designed measuring process. This thesis presents a framework for graphical-model based sparse recovery algorithms. Differing measurement processes lead to specific problems. The sparse recovery problems studied in this thesis include compressive sensing, network tomography, group testing and compressive phase retrieval. For compressive sensing and network tomography, the measurement processes are linear (freely chosen, and topology constrained measurements respectively). For group testing and compressivephase retrieval, the processes are non-linear (disjunctive, and intensity measurements respectively). For all the problems in this thesis, we present algorithms whose measurement structures are based on bipartite graphs. By studying the properties of bipartite graphs and designing novel measuring process and corresponding decoding algorithms, the number of measurements and computational decoding complexities of all the algorithms are information-theoretically either order-optimal or nearly order-optimal. / 稀疏還原問題旨在通過精心設計的低維度度量重建高維度稀疏信號。這篇論文提出了一個基於圖模型的稀疏還原演算法的框架。研究的稀疏還原問題包括了壓縮感知，網路斷層掃描，組測試和壓縮相位恢復。對於壓縮感知和網路斷層掃描，度量過程是線性的（分別是無約束的度量和拓撲結構約束的度量）。對於組測試和壓縮相位恢復，度量過程是非線性的（分別是邏輯度量和強度度量）。對於提到的問題，這篇論文提出的演算法的度量結構基於二部圖。通過學習二部圖的性質，我們提出了新穎的度量方法和相對應的解碼演算法。對於這些演算法，它們的度量維度和解碼演算法的運算複雜度都是（或接近於）資訊理論最優解。 / Cai, Sheng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2015. / Includes bibliographical references (leaves 229-247). / Abstracts also in Chinese. / Title from PDF title page (viewed on 05, October, 2016). / Detailed summary in vernacular field only.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_1290662 |
| Date | January 2015 |
| Contributors | Cai, Sheng (author.), Jaggi, Sidharth (thesis advisor.), Bakshi, Mayank (thesis advisor.), Chen, Minghua , active 2015 (thesis advisor.), Chinese University of Hong Kong Graduate School. Division of Information Engineering. (degree granting institution.) |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography, text |
| Format | electronic resource, electronic resource, remote, 1 online resource (xv, 247 leaves) : illustrations (some color), computer, online resource |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons "Attribution-NonCommercial-NoDerivatives 4.0 International" License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.002 seconds