Compressed Sensing for Support Set Reconstruction: Information-Theoretic Results and Design of Practical Algorithm

Abstract

Compressed Sensing (CS) is a new signal acquisition and reconstruction framework which has attract-ed lots of interests in both the signal processing and the information theory communities. This framework promises to compressively sample a sparse signal via random linear projections at a rate below the Shan-non-Nyquist rate, and also indicates this sparse signal can be reliably reconstructed from its compressed samples. The signal acquisition can be easily done by only conducting matrix-vector multiplications. In contrast, the signal reconstruction can be complicated because the model of the acquisition is an under-determined linear system. However, if the support set of an original sparse vector, i.e., a set of indices corresponding to the nonzero elements in this sparse vector, is given, this under-determined linear system becomes an over-determined system, implying that the signal reconstruction can be easily done using traditional least square methods. Thus, there have been not only several information-theoretic works regarding necessary and sufficient conditions to reliably reconstruct this support set but also several algorithms to reconstruct the support set in practice. As CS has been applied into various applications such as wireless sensor network (WSN) and magnetic resonance imaging (MRI), the signals of interests are modeled to be jointly sparse vectors, implying that the signals share a single support set. There are two different approaches for sampling these signals. The first model is called multiple measurement vectors (MMV) with the same sensing matrix in which all of sparse signals are measured via the same sensing matrix. The second model is called MMV with different sensing matrices where different sensing matrices are used to sample each sparse signal. There have been information-theoretic works for MMV with the same sensing matrix in the presence of noise. In contrast, for MMV with different sensing matrices, the information-theoretic work has been only conducted in the absence of noise. This dissertation mainly focuses on not only an information-theoretic study for a reliable support set reconstruction but also a derivation of a practical algorithm which can reconstruct support set with large variables. In the first part, we aim to provide information-theoretic results regarding the reliable support set reconstruction under noisy MMV with different sensing matrices. We begin to define a decoder, ex-tended from a joint typical decoder proposed in the work of Akcakaya and Tarokh, and define a failure probability that the defined decoder fails to reconstruct the support set. Using mathematical tools such as the Fano’s inequality and the Chernoff bound, we develop upper and lower bounds of this failure proba-bility in terms of the sparsity, the ambient dimension, the minimum signal-to-noise ratio, the number of measurement vectors and the number of measurements. These bounds can be used to provide guidelines for determining the system parameters for various applications in CS under noisy MMV with different sensing matrices. We develop asymptotic necessary and sufficient conditions for the reliable support set reconstruction based on these bounds. Using these conditions, we not only show how the usage of the joint sparsity structure can result in benefits on the support set reconstruction but also provide theoretical explanations regarding results which have been only empirically reported in the works of Caione et al. and Wu et al.. We then compare our sufficient conditions with the other existing sufficient conditions which are obtained for noisy MMV with the same sensing matrix. In a sublinear sparsity regime under some reasonable assumptions, we show that noisy MMV with different sensing matrices may require fewer measurements for the reliable support set reconstruction, which is an advantage of the usage of different sensing matrices for sampling sparse vectors which have the joint sparsity structure. In the second part, we aim to propose a fast first-order-type algorithm for support set reconstruction with cheap per-iteration cost. We begin to reformulate the l0-norm minimization problem into a mixed integer quadratic programming (MIQP) problem by following the works of Bourguigon et al., where a solution to this MIQP problem is shown to be a support set. We then use an alternating direction method (ADM), recently becoming a popular and powerful method for solving various integer programming (IP) problems studied in the works of Souto and Dinis, Yadav et al., and Takapoui et al., to derive the pro-posed algorithm. We define two metrics such as a mean square error (MSE) and a support set error (SSE) to evaluate how this proposed algorithm can reconstruct support set properly. We conduct extensive simulations to provide phase transition results, indicating that i) our algorithm significantly surpasses other algorithms based on ADM in terms of both MSE and SSE, and ii) our algorithm exhibits good MSE and SSE close to those of an optimal decoder that knows support set a prior. Then, we empirically confirm that the computational costs of our algorithm is roughly O(n^1.3) , where n is the ambient dimension.