As a paradigm to acquire sparse signals at a rate significantly below Nyquist rate, compressive sensing (CS) has attracted considerable attention in recent years. The major goal of CS is to recover a high dimensional sparse signal from its low dimensional linear measurements. It is now well-known th...
As a paradigm to acquire sparse signals at a rate significantly below Nyquist rate, compressive sensing (CS) has attracted considerable attention in recent years. The major goal of CS is to recover a high dimensional sparse signal from its low dimensional linear measurements. It is now well-known that if the measurement matrix satisfies the condition so called restricted isometry property (RIP) or mutual incoherence property (MIP), the sparse signal can be accurately recovered through properly designed recovery algorithms. Overall, the sparse recovery algorithms can be classified into two distinct categories: convex optimization method and greedy method. The convex optimization method recovers sparse signals using the linear programming (LP) technique. While this method provides excellent recovery performance, computational cost is often burdensome for large scale applications. As a cost-effective alternative of the convex optimization approach, greedy method has been widely used. The greedy method iteratively estimates the support or coefficients of the sparse signal to be recovered. In this dissertation, we investigate algorithms based on greedy method to improve sparse signal recovery performance. In the first part of the dissertation, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ``correct" indices, the gOMP algorithm is finished with much smaller number of iterations compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signal ($K > 1$), provided that the sensing matrix satisfies the RIP with $\delta_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity. In the second part of the dissertation, we propose an algorithm referred to as multipath matching pursuit (MMP) that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property (RIP) based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios. In the third part of the dissertation, we consider a detection problem of the underdetermined system when the input vector is sparse and its elements are chosen from a set of finite alphabets. This scenario is popular and embraces many of current and future wireless communication systems such as wireless sensor network, source localization, multiuser detection, downlink in massive MIMO, relaying in ad hoc network, to name just a few. We show that the simple modification of a parallel greedy search algorithm referred to as the multipath matching pursuit (MMP) is effective in recovering the discrete and sparse input signals. We also show that the addition of cross validation (CV) to the MMP algorithm is effective in identifying the sparsity level of input vector.
As a paradigm to acquire sparse signals at a rate significantly below Nyquist rate, compressive sensing (CS) has attracted considerable attention in recent years. The major goal of CS is to recover a high dimensional sparse signal from its low dimensional linear measurements. It is now well-known that if the measurement matrix satisfies the condition so called restricted isometry property (RIP) or mutual incoherence property (MIP), the sparse signal can be accurately recovered through properly designed recovery algorithms. Overall, the sparse recovery algorithms can be classified into two distinct categories: convex optimization method and greedy method. The convex optimization method recovers sparse signals using the linear programming (LP) technique. While this method provides excellent recovery performance, computational cost is often burdensome for large scale applications. As a cost-effective alternative of the convex optimization approach, greedy method has been widely used. The greedy method iteratively estimates the support or coefficients of the sparse signal to be recovered. In this dissertation, we investigate algorithms based on greedy method to improve sparse signal recovery performance. In the first part of the dissertation, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ``correct" indices, the gOMP algorithm is finished with much smaller number of iterations compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signal ($K > 1$), provided that the sensing matrix satisfies the RIP with $\delta_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity. In the second part of the dissertation, we propose an algorithm referred to as multipath matching pursuit (MMP) that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property (RIP) based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios. In the third part of the dissertation, we consider a detection problem of the underdetermined system when the input vector is sparse and its elements are chosen from a set of finite alphabets. This scenario is popular and embraces many of current and future wireless communication systems such as wireless sensor network, source localization, multiuser detection, downlink in massive MIMO, relaying in ad hoc network, to name just a few. We show that the simple modification of a parallel greedy search algorithm referred to as the multipath matching pursuit (MMP) is effective in recovering the discrete and sparse input signals. We also show that the addition of cross validation (CV) to the MMP algorithm is effective in identifying the sparsity level of input vector.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.