This paper proposes generalized approximate message passing (GAMP) for reconstruction of sparse signals from generalized linear measurements. The signal sparsity is assumed to grow sublinearly in the signal dimension, in contrast to conventional linear sparsity. State evolution is utilized to design GAMP for signals with sublinear sparsity. When the support of nonzero signals does not include a neighborhood of zero, the so-called all-or-nothing phenomenon occurs for Bayesian GAMP: Bayesian GAMP achieves asymptotically exact signal reconstruction if and only if the prefactor in the sample complexity scaling is larger than a threshold. Numerical simulations show that Bayesian GAMP outperforms existing algorithms for the reconstruction of signals with sublinear sparsity in the linear measurement and 1-bit compressed sensing.

This paper addresses the reconstruction of an unknown signal vector with sublinear sparsity from generalized linear measurements. Generalized approximate message-passing (GAMP) is proposed via state evolution in the sublinear sparsity limit, where the signal dimensionN, measurement dimensionM, and signal sparsityksatisfy logk/ logN→ γ ∈ [0, 1) andM/{klog(N/k)} → δ asNandktend to infinity. While the overall flow in state evolution is the same as that for linear sparsity, each proof step for inner denoising requires stronger assumptions than those for linear sparsity. The required new assumptions are proved for Bayesian inner denoising. When Bayesian outer and inner denoisers are used in GAMP, the obtained state evolution recursion is utilized to evaluate the prefactor δ in the sample complexity, called reconstruction threshold. If and only if δ is larger than the reconstruction threshold, Bayesian GAMP can achieve asymptotically exact signal reconstruction. In particular, the reconstruction threshold is finite for noisy linear measurements when the support of non-zero signal elements does not include a neighborhood of zero. As numerical examples, this paper considers linear measurements and 1-bit compressed sensing. Numerical simulations for both cases show that Bayesian GAMP outperforms existing algorithms for sublinear sparsity in terms of the sample complexity.

This paper proposes decentralized generalized approximate message-passing (D-GAMP) for compressed sensing in a tree-structured network. In contrast to conventional GAMP that needs a central node to gather all measurements on the network, D-GAMP utilizes consensus propagation via message-passing between adjacent nodes to achieve the same performance as centralized GAMP. The Onsager correction in D-GAMP is designed via rigorous state evolution so that the asymptotic Gaussianity of estimation errors in D-GAMP is guaranteed in each iteration for consensus propagation. By following a recently developed long-memory proof strategy, state evolution recursion for Bayes-optimal D-GAMP is proved to converge toward the Bayes-optimal fixed point— achieved by Bayes-optimal centralized GAMP—when the fixed point is unique.

Orthogonal approximate message-passing (OAMP) is proposed for signal recovery from right-orthogonally invariant linear measurements with spatial coupling. Conventional state evolution is generalized to a unified framework of state evolution for the spatial coupling and long-memory case. The unified framework is used to formulate the so-called Onsager correction in OAMP for spatially coupled systems. The state evolution recursion of Bayes-optimal OAMP is proved to converge for spatially coupled systems via Bayes-optimal long-memory OAMP and its state evolution. This paper proves the information-theoretic optimality of Bayes-optimal OAMP for noiseless spatially coupled systems with right-orthogonally invariant sensing matrices.

Decentralized generalized approximate message-passing (GAMP) is proposed for compressed sensing from distributed generalized linear measurements in a tree-structured network. Consensus propagation is used to realize average consensus required in GAMP via local communications between adjacent nodes. Decentralized GAMP is applicable to all tree-structured networks that do not necessarily have central nodes connected to all other nodes. State evolution is used to analyze the asymptotic dynamics of decentralized GAMP for zero-mean independent and identically distributed Gaussian sensing matrices. The state evolution recursion for decentralized GAMP is proved to have the same fixed points as that for centralized GAMP when homogeneous measurements with an identical dimension in all nodes are considered. Furthermore, existing long-memory proof strategy is used to prove that the state evolution recursion for decentralized GAMP with the Bayes-optimal denoisers converges to a fixed point. These results imply that the state evolution recursion for decentralized GAMP with the Bayes-optimal denoisers converges to the Bayes-optimal fixed point for the homogeneous measurements when the fixed point is unique. Numerical results for decentralized GAMP are presented in the cases of linear measurements and clipping. As examples of tree-structured networks, a one-dimensional chain and a tree with no central nodes are considered.

This paper addresses the reconstruction of sparse signals from spatially coupled, linear, and noisy measurements. A unified framework of rigorous state evolution is established for developing long-memory message-passing (LM-MP) in spatially coupled systems. LM-MP utilizes all previous messages to compute the current message while conventional MP only uses the latest messages. The unified framework is utilized to propose orthogonal approximate message-passing (OAMP) for spatially coupled systems. The framework for LM-MP is used as a technical tool to prove the convergence of state evolution for OAMP. Numerical results show that OAMP for spatially coupled systems is superior to that for systems without spatial coupling in the so-called waterfall region.

This paper proves the convergence of Bayes-optimal orthogonal/vector approximate message-passing (AMP) to a fixed point in the large system limit. The proof is based on Bayes-optimal long-memory (LM) message-passing (MP) that is guaranteed to converge systematically. The dynamics of Bayes-optimal LM-MP is analyzed via an existing state evolution framework. The obtained state evolution recursions are proved to converge. The convergence of Bayes-optimal orthogonal/vector AMP is proved by confirming an exact reduction of the state evolution recursions to those for Bayes-optimal orthogonal/vector AMP.

Orthogonal/vector approximate message-passing (AMP) is a powerful message-passing (MP) algorithm for signal reconstruction in compressed sensing. This paper proves the convergence of Bayes-optimal orthogonal/vector AMP in the large system limit. The proof strategy is based on a novel long-memory (LM) MP approach: A first step is a construction of LM-MP that is guaranteed to converge systematically. A second step is a large-system analysis of LM-MP via an existing framework of state evolution. A third step is to prove the convergence of state evolution recursions for Bayes-optimal LM-MP via a new statistical interpretation of existing LM damping. The last is an exact reduction of the state evolution recursions for Bayes-optimal LM-MP to those for Bayes-optimal orthogonal/vector AMP. The convergence of the state evolution recursions for Bayes-optimal LM-MP implies that for Bayes-optimal orthogonal/vector AMP. Numerical simulations are presented to show the verification of state evolution results for damped orthogonal/vector AMP and a negative aspect of LM-MP in finite-sized systems.

To improve the convergence property of approximate message-passing (AMP), convolutional AMP (CAMP) has been proposed. CAMP replaces the Onsager correction in AMP with a convolution of messages in all preceding iterations while it uses the same low-complexity matched filter (MF) as AMP. This paper derives state evolution (SE) equations to design the Bayes-optimal denoiser in CAMP. Numerical results imply that CAMP with the Bayes-optimal denoiser-called Bayes-optimal CAMP-can achieve the Bayes-optimal performance for right-orthogonally invariant sensing matrices with low-to-moderate condition numbers.

This paper proposes Bayes-optimal convolutional approximate message-passing (CAMP) for signal recovery in compressed sensing. CAMP uses the same low-complexity matched filter (MF) for interference suppression as approximate message-passing (AMP). To improve the convergence property of AMP for ill-conditioned sensing matrices, the so-called Onsager correction term in AMP is replaced by a convolution of all preceding messages. The tap coefficients in the convolution are determined so as to realize asymptotic Gaussianity of estimation errors via state evolution (SE) under the assumption of orthogonally invariant sensing matrices. An SE equation is derived to optimize the sequence of denoisers in CAMP. The optimized CAMP is proved to be Bayes-optimal for all orthogonally invariant sensing matrices if the SE equation converges to a fixed-point and if the fixed-point is unique. For sensing matrices with low-to-moderate condition numbers, CAMP can achieve the same performance as high-complexity orthogonal/vector AMP that requires the linear minimum mean-square error (LMMSE) filter instead of the MF.

This letter proposes a novel message-passing algorithm for signal recovery in compressed sensing. The proposed algorithm solves the disadvantages of approximate message-passing (AMP) and orthogonal/vector AMP, and realizes their advantages. AMP converges only in a limited class of sensing matrices while it has low complexity. Orthogonal/vector AMP requires a high-complexity matrix inversion while it is applicable for a wide class of sensing matrices. The key feature of the proposed algorithm is the so-called Onsager correction via a convolution of messages in all preceding iterations while the conventional message-passing algorithms have correction terms that depend only on messages in the latest iteration. Thus, the proposed algorithm is called convolutional AMP (CAMP). Ill-conditioned sensing matrices are simulated as an example in which the convergence of AMP is not guaranteed. Numerical simulations show that CAMP can improve the convergence property of AMP and achieve high performance comparable to orthogonal/vector AMP in spite of low complexity comparable to AMP.

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix.

This paper presents a unified framework to understand the dynamics of message-passing algorithms in compressed sensing. State evolution is rigorously analyzed for a general error model that contains the error model of approximate message-passing (AMP), as well as that of orthogonal AMP. As a byproduct, AMP is proved to converge asymptotically if the sensing matrix is orthogonally invariant and if the moment sequence of its asymptotic singular-value distribution coincide with that of the Marčhenko-Pastur distribution up to the order that is at most twice as large as the maximum number of iterations.

This paper investigates sparse signal recovery based on expectation propagation (EP) from unitarily invariant measurements. A rigorous analysis is presented for the state evolution (SE) of an EP-based message-passing algorithm in the large system limit, where both input and output dimensions tend to infinity at an identical speed. The main result is the justification of an SE formula conjectured by Ma and Ping.

Kudekar et al. proved that the belief-propagation (BP) performance for low-density parity check codes can be boosted up to the maximum a posteriori (MAP) performance by spatial coupling. In this paper, spatial coupling is applied to sparsely spread code-division multiple-access systems to improve the performance of iterative multiuser detection based on BP. Two iterative receivers based on BP are considered: 1) one receiver is based on exact BP and 2) the other on an approximate BP with Gaussian approximation. The performance of the two BP receivers is evaluated via density evolution (DE) in the dense limit after taking the large-system limit, in which the number of users and the spreading factor tend to infinity while their ratio is kept constant. The two BP receivers are shown to achieve the same performance as each other in these limits. Furthermore, taking a continuum limit for the obtained DE equations implies that the performance of the two BP receivers can be improved up to the performance achieved by the symbol-wise MAP detection, called individually optimal detection, via spatial coupling. Numerical simulations show that spatial coupling can provide a significant improvement in bit-error rate for finite-sized systems especially in the region of high system loads.

Spatial coupling was proved to improve the belief-propagation (BP) performance up to the maximum-a-posteriori (MAP) performance. This paper addresses an extended class of spatially coupled (SC) systems. A potential function is derived for characterizing a lower bound on the BP performance of the extended SC systems, and shown to be different from the potential for the conventional SC systems. This may imply that the BP performance for the extended SC systems does not coincide with the MAP performance for the corresponding uncoupled system. SC bit-interleaved coded modulation with iterative decoding (BICM-ID) is also investigated as an application of the extended SC systems.

Spatially-coupled (SC) codes are constructed by coupling many regular low-density parity-check codes in a chain. The decoding chain of SC codes aborts when facing burst erasures. This problem cannot be overcome by increasing the chain length. In this paper, we introduce multi-dimensional (MD) SC codes to circumvent it. Numerical results show that two-dimensional SC codes are more robust against the burst erasures than one-dimensional SC codes. Furthermore, we consider designing multidimensional SC codes with smaller rateloss.

Iterative channel estimation and decoding based on probabilistic bias is investigated. In order to control the occurrence probability of transmitted symbols, biased convolutional codes (CCs) are proposed. A biased CC is obtained by puncturing the parity bit of a conventional (unbiased) CC and by inserting a fixed bit at the punctured position when the state is contained in a certain subset of all possible states. A priori information about the imposed bias is utilized for the initial linear minimum mean-squared error (LMMSE) channel estimation. This paper focuses on biased turbo codes that are constructed as the parallel concatenation of two biased CCs with interleaving, and proposes an iterative LMMSE channel estimation and decoding scheme based on approximate belief propagation. The convergence property of the iterative LMMSE channel estimation and decoding scheme is analyzed via density evolution (DE). The DE analysis allows one to design the magnitude of the bias according to the coherence time, in terms of the decoding threshold. The proposed scheme is numerically shown to outperform conventional pilot-based schemes in the moderate signal-to-noise ratio (SNR) regime, at the expense of a performance degradation in the high SNR regime.

Training-based transmission over Rayleigh block-fading multiple-input multiple-output (MIMO) channels is investigated. As a training method a combination of a pilot-assisted scheme and a biased signaling scheme is considered. The achievable rates of successive decoding (SD) receivers based on the linear minimum mean-squared error (LMMSE) channel estimation are analyzed in the large-system limit, by using the replica method under the assumption of replica symmetry. It is shown that negligible pilot information is best in terms of the achievable rates of the SD receivers in the large-system limit. The obtained analytical formulas of the achievable rates can improve the existing lower bound on the capacity of the MIMO channel with no channel state information (CSI), derived by Hassibi and Hochwald, for all SNRs. The comparison between the obtained bound and a high-SNR approximation of the channel capacity, derived by Zheng and Tse, implies that the high-SNR approximation is unreliable unless quite high SNR is considered. Energy efficiency in the low-SNR regime is also investigated in terms of the power per information bit required for reliable communication. The required minimum power is shown to be achieved at a positive rate for the SD receiver with no CSI, whereas it is achieved in the zero-rate limit for the case of perfect CSI available at the receiver. Moreover, numerical simulations imply that the presented large-system analysis can provide a good approximation for not so large systems. The results in this paper imply that SD schemes can provide a significant performance gain in the low-to-moderate SNR regimes, compared to conventional receivers based on one-shot channel estimation.

This paper presents a large-system analysis of the performance of joint channel estimation, multiuser detection, and per-user decoding (CE-MUDD) for randomly-spread multiple-input multiple-output (MIMO) direct-sequence code-division multiple-access (DS-CDMA) systems. A suboptimal receiver based on successive decoding in conjunction with linear minimum mean-squared error (LMMSE) channel estimation is investigated. The replica method, developed in statistical mechanics, is used to evaluate the performance in the large-system limit, where the number of users and the spreading factor tend to infinity while their ratio and the number of transmit and receive antennas are kept constant. The performance of the joint CE-MUDD based on LMMSE channel estimation is compared to the spectral efficiencies of several receivers based on one-shot LMMSE channel estimation, in which the decoded data symbols are not utilized to refine the initial channel estimates. The results imply that the use of joint CE-MUDD significantly reduces rate loss due to transmission of pilot signals, especially for multiple-antenna systems. As a result, joint CE-MUDD can provide significant performance gains, compared to the receivers based on one-shot channel estimation.

A novel signaling scheme for iterative channel estimation and data decoding is proposed. In the proposed scheme, the occurrence probability of transmitted symbols is biased. A priori information about the bias is utilized for the initial channel estimation. The proposed scheme is based on parallel concatenation of two biased convolutional codes (BCCs), which are constructed as systematic recursive convolutional codes with state-dependent puncturing. The BCCs can be regarded as a joint coding scheme that determines the insertion positions of pilot symbols according to information bits. The proposed scheme is numerically shown to outperform conventional pilot-based schemes in the waterfall region, while it is inferior to the conventional schemes in the error-floor region.

Kudekar et al. proved that the belief-propagation (BP) threshold for low-density parity-check codes can be boosted up to the maximum-a-posteriori (MAP) threshold by spatial coupling. In this paper, spatial coupling is applied to randomly-spread code-division multiple-access (CDMA) systems in order to improve the performance of BP-based multiuser detection (MUD). Spatially-coupled CDMA systems can be regarded as multi-code CDMA systems with two transmission phases. The large-system analysis shows that spatial coupling can improve the BP performance, while there is a gap between the BP performance and the individually-optimal (IO) performance.

The large system analysis of randomly spread MIMO DS-CDMA systems is provided. Correlated Rayleigh fading MIMO channels are assumed for all users. Linear multiuser detection with separate decoding and pilot-aided channel estimation are used. The results imply that with channel estimation, the performance can improve significantly as the correlation between the transmit antennas increases. No channel information at the transmitter is required, but the channel estimator needs knowlegde of the long term transmit correlation in advance. The numerical results demonstrate that in a 4 × 4 MIMO DS-CDMA system with two users per chip, high antenna correlation at the transmitter can double the ergodic spectral efficiency compared to the case of uncorrelated transmit antennas.

A Rayleigh block-fading multiple-input multiple-output (MIMO) channel with channel state information (CSI) available neither to the transmitter nor to the receiver is considered. A lower bound on the capacity is formulated based on a successive decoding (SD) scheme. An analytical expression of the lower bound is derived in the large-system limit, by using the replica method. Furthermore, the achievable rate of the linear minimum mean-squared error (LMMSE) receiver with SD is also evaluated in the large-system limit. The lower bound is superior to the lower bound derived by Hassibi and Hochwald for all signal-to-noise ratios (SNRs).

This paper studies large randomly spread direct-sequence code-division multiple-access system operating over a block fading multipath channel. Channel knowledge is obtained by a linear estimator whose initial decisions are iteratively refined by using a soft feedback from the single-user decoders. In addition to the traditional training symbol based signaling scheme, we study a novel method that utilizes a random bias in the symbol probabilities of the transmitted signal to construct the initial channel estimates. The numerical results suggest that in the large system limit, appropriate selection of the channel code and signaling method allows for successful communication with vanishing training overhead in overloaded systems if iterative channel and data estimation is performed at the receiver.

We propose a randomly-biased quadrature phase shift keying (QPSK) signaling scheme for a noncoherent Rayleigh block-fading multiple-input multiple-output (MIMO) channel. In order to optimize a prior of bias, we evaluate a lower bound of the spectral efficiency of the noncoherent MIMO channel with randomly-biased QPSK signaling in the large-system limit, by using the replica method. Our main result is that randomly-biased QPSK signaling with vanishing bias is optimal in the large-system limit for any signal-to-noise ratio.

The large system analysis of a randomly spread direct-sequence code-division multiple-access system operating over a frequency-selective fading channel is considered. Iterative multiuser detection and decoding based on generalized posterior mean estimation and interference cancellation is assumed. The channel is mismatched and provided by a linear estimator whose initial pilot-based decisions are iteratively refined by using a feedback from the single-user decoders. By an application of the replica method, a tool from statistical physics, and density evolution with Gaussian approximation, we show that the performance metrics of the considered multiuser system converge in distribution at the large system limit to that of a simple single-user system operating over a flat fading channel. We also give the exact result of the hard decision feedback based channel estimator analyzed approximately by Li et al. (2007).

We propose a novel signaling scheme for wireless communication systems without channel state information (CSI). In that scheme, a bias of the occurrence probabilities of constellation points is utilized as pilot information known to the receiver, whereas pilot signals known to the receiver are sent in conventional pilot-based approaches. We evaluate the performance of the new scheme and conventional pilot-based schemes for a large direct-sequence code-division multiple-access (DS-CDMA) system, by using the replica method. It is shown that the new scheme outperforms the conventional pilot-based scheme when the amount of pilot information is large.

We study the spectral efficiency of large random direct-sequence code-division multiple-access systems utilizing linear minimum mean square error (LMMSE) channel estimation and iterative multiuser detection and decoding (MUDD). Iterative MUDD based on non-linear data estimation and single-user decoding is considered as a benchmark for the more practical iterative LMMSE data estimator with soft parallel interference cancellation. The results showed that the channel parameters and the choice of error correction code have a great impact on the achievable spectral efficiency. It was also found that for the considered setups, the iterative LMMSE based channel estimator is near optimal for slowly time-varying multipath fading channels.

We consider impacts of channel estimation errors on performance of general multiuser detectors in MIMO DS-CDMA channels. We evaluate their performance in terms of asymptotic spectral efficiency, which is obtained via decoupling structure, by using the replica method. Numerical results imply that the performance of LMMSE detection is very close to that of MMSE detection for small system loads. Furthermore, we find that the spectral efficiency of MMSE detection grows discontinuously with the length of pilot sequences for large system loads, and that the critical length is close to the optimal length. While it is indistinguishable from that of LMMSE detection for short pilot sequences, the gap between the two is significantly large if the length of pilot sequences is longer than the critical length.

We analyze decoupling structures of MIMO DS-CDMA channels with general multiuser detector front ends, using the replica method, in order to compare the space-time spreading (STS) and time spreading (TS) schemes. In the many- user limit, a MIMO DS-CDMA channel with the STS scheme is decoupled into a bank of single-user SIMO channels. On the other hand, a MIMO DS-CDMA channel with the TS scheme is decoupled into a bank of single-user MIMO channels. In view of performance, the STS scheme outperforms the TS scheme in the fast fading situation if transmit spatial correlations exist. In terms of complexity, the STS scheme does not require any space-time coding. On the other hand, the TS scheme does require space-time coding in order to achieve comparable performance to the STS scheme. The STS scheme improves the performance of communications and reduces the complexity of transmitter and receiver architectures.

We analyze an uplink of a fast flat fading MIMO-CDMA channel in the case where the data symbol vector for each user follows an arbitrary distribution. The maximum spectral efficiency of the channel with CSI at the receiver is evaluated analytically with the replica method. The main result is that the hierarchical decoupling principle holds in the MIMO-CDMA channel, i.e., the MIMO-CDMA channel is decoupled into a bank of single-user MIMO channels in the many-user limit, and each single-user MIMO channel is further decoupled into a bank of scalar Gaussian channels in the many-antenna limit for a fading model with a limited number of scatterers.