A phenomenon known as ``Neural Collapse (NC)'' in deep classification tasks, in which the penultimate-layer features and the final classifiers exhibit an extremely simple geometric structure, has recently attracted considerable attention, with the expectation that it can deepen our understanding of how deep neural networks behave. The Unconstrained Feature Model (UFM) has been proposed to explain NC theoretically, and there emerges a growing body of work that extends NC to tasks other than classification and leverages it for practical applications. In this study, we investigate whether a similar phenomenon arises in deep Ordinal Regression (OR) tasks, via combining the cumulative link model for OR and UFM. We show that a phenomenon we call Ordinal Neural Collapse (ONC) indeed emerges and is characterized by the following three properties: (ONC1) all optimal features in the same class collapse to their within-class mean when regularization is applied; (ONC2) these class means align with the classifier, meaning that they collapse onto a one-dimensional subspace; (ONC3) the optimal latent variables (corresponding to logits or preactivations in classification tasks) are aligned according to the class order, and in particular, in the zero-regularization limit, a highly local and simple geometric relationship emerges between the latent variables and the threshold values. We prove these properties analytically within the UFM framework with fixed threshold values and corroborate them empirically across a variety of datasets. We also discuss how these insights can be leveraged in OR, highlighting the use of fixed thresholds.

Creating images where surface patterns of one object - such as cracks, holes, or grooves - are precisely transferred onto objects made of different materials remains a challenging task in computer graphics. For example, recreating the exact pattern of wood grain cracks on a metallic surface, while maintaining the realistic metallic texture, requires sophisticated technical solutions. In this study, we introduce Harmonizing Attention, a new method that can automatically extract these surface patterns from pho-tographs and recreate them with different materials, while preserving natural-looking textures. Our approach achieves this through a novel attention mechanism that can process multiple reference images simultaneously, without requiring additional training. This makes the method both practical and efficient for real-world applications, opening up new possibilities in augmented reality, image editing, and beyond.

In image editing employing diffusion models, it is crucial to preserve the reconstruction fidelity to the original image while changing its style. Although existing methods ensure reconstruction fidelity through optimization, a drawback of these is the significant amount of time required for optimization. In this paper, we propose negative-prompt inversion, a method capable of achieving equivalent reconstruction solely through forward propagation without optimization, thereby enabling ultrafast editing processes. We experimentally demonstrate that the reconstruction fidelity of our method is comparable to that of existing methods, allowing for inversion at a resolution of 512 pixels and with 50 sampling steps within approximately 5 seconds, which is more than 30 times faster than null-text inversion. Reduction of the computation time by the proposed method further allows us to use a larger number of sampling steps in diffusion models to improve the reconstruction fidelity with a moderate increase in computation time.

This paper studies complexity measures of reservoir systems. For this purpose, a more general model that we call a feature-based learning system, which is the composition of a feature map and of a final estimator, is studied. We study complexity measures such as growth function, VC-dimension, pseudo-dimension and Rademacher complexity. On the basis of the results, we discuss how the unadjustability of reservoirs and the linearity of readouts can affect complexity measures of the reservoir systems. Furthermore, some of the results generalize or improve the existing results.

Approximation capability of reservoir systems whose reservoir is a recurrent neural network (RNN) is discussed. We show what we call uniform strong universality of RNN reservoir systems for a certain class of dynamical systems. This means that, given an approximation error to be achieved, one can construct an RNN reservoir system that approximates each target dynamical system in the class just via adjusting its linear readout. To show the universality, we construct an RNN reservoir system via parallel concatenation that has an upper bound of approximation error independent of each target in the class.

The mean shift (MS) algorithm seeks a mode of the kernel density estimate (KDE). This study presents a convergence guarantee of the mode estimate sequence generated by the MS algorithm and an evaluation of the convergence rate, under fairly mild conditions, with the help of the argument concerning the Łojasiewicz inequality. Our findings extend existing ones covering analytic kernels and the Epanechnikov kernel. Those are significant in that they cover the biweight kernel, which is optimal among non-negative kernels in terms of the asymptotic statistical efficiency for the KDE-based mode estimation.

This paper addresses modeling and analysis of interference in wireless networks. We present a novel clustered mean-field hard-core model with non-homogeneous clusters. We develop a theory for throughput equalization in this model which can serve as a distributed strategy for throughput equalization. We also present stability analysis of the throughput equalization strategy. This work recovers several previously known results as special cases. We present results of Monte-Carlo simulations to evaluate the proposed strategy in mean-field networks.

We consider matrix sketching for principal component analysis (PCA) with the input data matrices generated by the rank-one spiked model. In the high-dimensional limit, we evaluate the estimation performance of matrix sketching via the replica method. Numerical studies confirm the validity of our results. The obtained result shows that the performance of the estimator undergoes a phase transition at a certain value of the signal strength. A similar asymptotic behavior is well-known for PCA. We demonstrate that our result is a one-parameter generalization of the existing results for PCA. On the basis of our performance evaluation, we also derive the condition for matrix sketching to recover the underlying signal.

The rapid adoption of wireless sensor devices has made it easier to record location information of people in a variety of spaces (e.g., exhibition halls). Location information is often aggregated due to privacy and/or cost concerns. The aggregated data we use as input consist of the numbers of incoming and outgoing people at each location and at each time step. Since the aggregated data lack tracking information of individuals, determining the flow of people between locations is not straightforward. In this article, we address the problem of inferring latent people flows, that is, transition populations between locations, from just aggregated population data gathered from observed locations. Existing models assume that everyone is always in one of the observed locations at every time step; this, however, is an unrealistic assumption, because we do not always have a large enough number of sensor devices to cover the large-scale spaces targeted. To overcome this drawback, we propose a probabilistic model with flow conservation constraints that incorporate travel duration distributions between observed locations. To handle noisy settings, we adopt noisy observation models for the numbers of incoming and outgoing people, where the noise is regarded as a factor that may disturb flow conservation, e.g., people may appear in or disappear from the predefined space of interest. We develop an approximate expectation-maximization (EM) algorithm that simultaneously estimates transition populations and model parameters. Our experiments demonstrate the effectiveness of the proposed model on real-world datasets of pedestrian data in exhibition halls, bike trip data and taxi trip data in New York City.

We study properties of the mean shift (MS)-type algorithms for estimating modes of probability density functions (PDFs), via regarding these algorithms as gradient ascent on estimated PDFs with adaptive step sizes. We rigorously prove convergence of mode estimate sequences generated by the MS-type algorithms, under the assumption that an analytic kernel function is used. Moreover, our analysis on the MS function finds several new properties of mode estimate sequences and corresponding density estimate sequences, including the result that in the MS-type algorithm using a Gaussian kernel the density estimate monotonically increases between two consecutive mode estimates. This implies that, in the one-dimensional case, the mode estimate sequence monotonically converges to the stationary point nearest to an initial point without jumping over any stationary point.

We propose a probabilistic model for refining coarse-grained spatial data by utilizing auxiliary spatial data sets. Existing methods require that the spatial granularities of the auxiliary data sets are the same as the desired granularity of target data. The proposed model can effectively make use of auxiliary data sets with various granularities by hierarchically incorporating Gaussian processes. With the proposed model, a distribution for each auxiliary data set on the continuous space is modeled using a Gaussian process, where the representation of uncertainty considers the levels of granularity. The finegrained target data are modeled by another Gaussian process that considers both the spatial correlation and the auxiliary data sets with their uncertainty. We integrate the Gaussian process with a spatial aggregation process that transforms the fine-grained target data into the coarse-grained target data, by which we can infer the fine-grained target Gaussian process from the coarse-grained data. Our model is designed such that the inference of model parameters based on the exact marginal likelihood is possible, in which the variables of finegrained target and auxiliary data are analytically integrated out. Our experiments on real-world spatial data sets demonstrate the effectiveness of the proposed model.

Modal linear regression (MLR) is a method for obtaining a conditional mode predictor as a linear model. We study kernel selection for MLR from two perspectives: "which kernel achieves smaller error?" and "which kernel is computationally efficient?". First, we show that a Biweight kernel is optimal in the sense of minimizing an asymptotic mean squared error of a resulting MLR parameter. This result is derived from our refined analysis of an asymptotic statistical behavior of MLR. Secondly, we provide a kernel class for which iteratively reweighted least-squares algorithm (IRLS) is guaranteed to converge, and especially prove that IRLS with an Epanechnikov kernel terminates in a finite number of iterations. Simulation studies empirically verified that using a Biweight kernel provides good estimation accuracy and that using an Epanechnikov kernel is computationally efficient. Our results improve MLR of which existing studies often stick to a Gaussian kernel and modal EM algorithm specialized for it, by providing guidelines of kernel selection.

We have evaluated, via the replica method, phase transition thresholds for the mixed ℓ2/ℓ1-norm minimization applied to block-sparse compressed sensing with randomly generated measurement matrices. Our analysis takes into account that the matrix elements may be of non-zero mean, and shows that the phase transition threshold for the mixed ℓ2/ℓ1-norm minimization improves when the matrix elements have non-zero mean and the distribution of non-zero blocks of the target vector to be estimated has a certain imbalance.

We propose a probabilistic model for inferring the multivariate function from multiple areal data sets with various granularities. Here, the areal data are observed not at location points but at regions. Existing regression-based models can only utilize the sufficiently fine-grained auxiliary data sets on the same domain (e.g., a city). With the proposed model, the functions for respective areal data sets are assumed to be a multivariate dependent Gaussian process (GP) that is modeled as a linear mixing of independent latent GPs. Sharing of latent GPs across multiple areal data sets allows us to effectively estimate the spatial correlation for each areal data set; moreover it can easily be extended to transfer learning across multiple domains. To handle the multivariate areal data, we design an observation model with a spatial aggregation process for each areal data set, which is an integral of the mixed GP over the corresponding region. By deriving the posterior GP, we can predict the data value at any location point by considering the spatial correlations and the dependences between areal data sets, simultaneously. Our experiments on real-world data sets demonstrate that our model can 1) accurately refine coarse-grained areal data, and 2) offer performance improvements by using the areal data sets from multiple domains.

This paper considers the stationary distribution of the age of information (AoI) in information update systems. We first derive a general formula for the stationary distribution of the AoI, which holds for a wide class of information update systems. The formula indicates that the stationary distribution of the AoI is given in terms of the stationary distributions of the system delay and the peak AoI. To demonstrate its applicability and usefulness, we analyze the AoI in single-server queues with four different service disciplines: first-come first-served (FCFS), preemptive last-come first-served (LCFS), and two variants of non-preemptive LCFS service disciplines. For the FCFS and the preemptive LCFS service disciplines, the GI/GI/1, M/GI/1, and GI/M/1 queues are considered, and for the non-preemptive LCFS service disciplines, the M/GI/1 and GI/M/1 queues are considered. With these results, we further show comparison results for the mean AoI’s in the M/GI/1 and GI/M/1 queues under those service disciplines.

We study performance of theL1-norm minimization for compressed sensing with noiseless linear measurements when the elements of the measurement matrix are independent and identically-distributed Gaussian with non-zero mean. Using replica method in statistical mechanics, we derive in the large-system limit the condition for perfect estimation of sparse vectors in terms of the four parameters: the ratio of the number of measurements to the dimension of the sparse vector, the ratio of the number of non-zeros in the sparse vector to the dimension of the vector, the bias of the matrix elements, and the imbalance of the distribution of non-zeros of the sparse vector. We find that when the distribution of non-zeros is balanced the bias of the matrix elements does not affect the condition for perfect estimation. When the distribution of non-zeros is not balanced, on the other hand, theL1-norm minimization will be successful with a smaller number of linear measurements if one uses a biased measurement matrix. Numerical experiments are also conducted to confirm the derived condition.

We consider the stationary distributions of the age of information (AoI) and the peak AoI in information update systems. We first derive an invariant relation among the distributions of the AoI, the peak AoI, and the system delay, which holds for a wide class of information update systems. Based on this result, we next obtain several formulas for the stationary distributions of the AoI and the peak AoI in the first-come first-served (FCFS) GI/GI/1 queue, which is a general model of FCFS information update systems. Finally, we derive explicit formulas for the Laplace-Stieltjes transforms of the stationary distributions of the AoI and the peak AoI in FCFS M/GI/1 and GI/M/1 queues.

Approximate Massage Passing (AMP) algorithm is derived from Belief Propagation (BP) algorithm by introducing approximations. While the properties and behaviors of AMP in large systems are well studied and understood, there are few studies about AMP applied to relatively small sized problems where the effect of the approximations are neither negligible nor trivial. We investigate AMP in small-sized problems, especially focusing on the effects of the approximations and the mechanism of the performance degradation. To observe the effects of the approximations, we conduct numerical experiments which compare AMP and BP algorithms. We apply these algorithms to the problems of CDMA-MUD and Ising perceptron learning. In the numerical experiments, the results via Bayes optimal estimation obtained via exactly calculating marginals and an approximated BP algorithm which is obtained as an intermediate step to derive AMP from BP are also provided and discussed for the comparisons.

We study limiting eigenvalue distributions of block random matrix ensembles with one-dimensional coupling structure under the limit where the matrix size tends to infinity. Matrices in the ensembles have independent real symmetric random matrices of Wigner type on the diagonal blocks and a scalar multiple of the identity matrix on the blocks adjacent to the diagonal blocks. Explicit analytical formulas for the limiting eigenvalue distributions are derived for the 2 × 2-block ensemble as well as the 3 × 3-block circular ensemble. Further numerical results for B × B-block ensembles with B ≥ 3 are also shown.

In this paper we consider the problem of equalizing throughput of nodes in CSMA-based wireless networks. We model interference in a network using conflict graph, where edges represent hard-core interaction, meaning that the two nodes an edge connects cannot be simultaneously active, or transmitting. In practice, the degrees of nodes in a conflict graph are not constant. In such cases, using CSMA leads to lack of fairness since nodes with larger degree have the potential of getting hold of the medium for smaller fraction of time than the nodes with smaller degree. We present a distributed strategy for throughput equalization. The proposed strategy is based on a mean-field hard-core model of interference, and it equalizes the throughput of the nodes with different degrees. We also show that the mean-field hard-core model exhibits a certain phase transition. We present results of Monte-Carlo simulations to evaluate the the proposed strategy in square grid networks and Poisson networks, in addition to mean-field networks.

Pearl's belief propagation (BP) is an algorithm to solve inference problems on probability models defined in terms of graphical models. Computational complexity of BP per iteration is typically exponential in the degrees of nodes in the graph, which makes application of BP impractical in problems represented by dense graphs. For the alleviation of the computational difficulty of BP, an approximation of BP dubbed approximate message passing (AMP) is proposed in the area of compressed sensing. Since theoretical treatments of AMP are mostly in the infinite-dimensional limit, they are not mathematically justifiable when the system size is not large enough and little is known about the cases where the system size is small. We investigate poor performance of the AMP algorithm applied to small-sized problems, which is frequently observed in numerical experiments, by comparing performance of the AMP algorithm and that of the original BP algorithm. In this paper, firstly, we show that, under several assumptions, one can perform the original BP algorithm in time complexity that is polynomial in the degrees of the nodes, utilizing a method similar to what is employed in BP decoding for LDPC codes. Next, we apply the preceding discussion to the CDMA multiuser detection problem, to which AMP has been successfully applied in existing researches. Finally, we compare the performance of the BP and AMP algorithms and discuss the effects of the approximation involved in deriving the AMP algorithm, when the system size is not large enough.

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.

We consider the situation where the total number of measurements is limited in compressed sensing of sparse vectors with noisy measurements. In this situation there is a trade-off between acquiring as many independent observations as possible and performing averaging over several identical measurements in order to improve signal-to-noise ratio. With the help of the approximate message passing algorithm to solve LASSO problems, we have proved, via state evolution, that in order to minimize estimation errors one should perform as many independent linear measurements as possible rather than performing averaging to improve signal-to-noise ratio of the observations. Furthermore, we have confirmed via numerical experiments that the same holds in the case where the measurement matrix is constructed by randomly subsampling rows of a discrete Fourier matrix.

Polarization phenomenon over any finite field Fq with size q being a power of a prime is considered. This problem is a generalization of the original proposal of channel polarization by Arıkan for the binary field, as well as its extension to a prime field by Sasoglu, Telatar, and Arıkan. In this paper, a necessary and sufficient condition of a matrix over a finite field Fqis shown under which any source and channel are polarized. Furthermore, the result of the speed of polarization for the binary alphabet obtained by Arıkan and Telatar is generalized to arbitrary finite field. It is also shown that the asymptotic error probability of polar codes is improved by using the Reed-Solomon matrices, which can be regarded as a natural generalization of the 2 × 2 binary matrix used in the original proposal by Arıkan.

We study the problem of reconstructing low-rank matrices from their noisy observations. We formulate the problem in the Bayesian framework, which allows us to exploit structural properties of matrices in addition to low-rankedness, such as sparsity. We propose an efficient approximate message passing algorithm, derived from the belief propagation algorithm, to perform the Bayesian inference for matrix reconstruction. We have also successfully applied the proposed algorithm to a clustering problem, by formulating the problem of clustering as a low-rank matrix reconstruction problem with an additional structural property. Numerical experiments show that the proposed algorithm outperforms Lloyd's K-means algorithm.

We consider the asymptotic behavior of the polarization process in the large block-length regime when transmission takes place over a binary-input memoryless symmetric channel$W$. In particular, we study the asymptotics of the cumulative distribution$\BBP(Z_{n}\leq z)$, where$\{Z_{n}\}$is the Bhattacharyya process associated with$W$, and its dependence on the rate of transmission. On the basis of this result, we characterize the asymptotic behavior, as well as its dependence on the rate, of the block error probability of polar codes using the successive cancellation decoder. This refines the original asymptotic bounds by Arıkan and Telatar. Our results apply to general polar codes based on$\ell\times\ell$kernel matrices. We also provide asymptotic lower bounds on the block error probability of polar codes using the maximum a posteriori (MAP) decoder. The MAP lower bound and the successive cancellation upper bound coincide when$\ell=2$, but there is a gap for$\ell > 2$.

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like α(ε,t)/n+Θ(n-2) as the blocklengthntends to infinity where α(ε,t) denotes a specific constant determined by the code ensemble considered, the numbertof iterations, and the erasure probability ε of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant α(ε,t) for standard irregular ensembles. The dominant difference α(ε,t)/ncan be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using α(ε,t) is accurate even for small blocklengths.

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.

In statistical physics and information theory, while asymptotic behavior of the partition function is often of our primary interest, the most of works are dedicated to analysis of the exponent of the partition function. In our previous paper on sparse random factor graph ensembles, we show that the exponent of the expectation of the partition function is represented as the minimum of the Bethe free energy of the small averaged graph by using the method of types. In this paper, we present a general framework to study more precise asymptotic behaviors of the partition function, using the central approximation in conjunction with the method of types.

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.

We evaluate average error exponent of the undetected error probability of binary matrix ensembles by applying statistical-mechanics approach, which is called the “quenched” average error exponent. In the exixting analysis, the “annealed” average error exponent, which is the error exponent of the average undetected error probability, has been evaluated. The quenched average error exponent is more suitable to capture typical behaviors. We show that there are some cases where the annealed exponent is overestimated for the irregular sparse matrix ensemble. We also show that the quenched average error exponent is equivalent to the annealed average error exponents for the regular sparse matrix ensemble.

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.

ℓ1minimization for compressed sensing provides a computationally efficient means to reconstruct sparse signals from linear measurements whose number is less than the dimension of the signal. Reconstruction from a smaller number of measurements can be possible via iterative reweighted ℓ1minimization (IRL1). In this paper, adopting a statistical-mechanics approach, we propose an analytical framework for evaluating critical compression ratio, the ratio of the number of measurements to the dimension of the signal, for IRL1.

We propose a framework for improving classifier performance by effectively using auxiliary samples. The auxiliary samples are labeled not in terms of the target taxonomy according to which we wish to classify samples, but according to classification schemes or taxonomies that are different from the target taxonomy. Our method finds a classifier by minimizing a weighted error over the target and auxiliary samples. The weights are defined so that the weighted error approximates the expected error when samples are classified into the target taxonomy. Experiments using synthetic and text data show that our method significantly improves the classifier performance in most cases compared to conventional data augmentation methods.

We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing N-dimensional sparse vector x = (xi) from its linear transformation y = Fx of P dimensions on the basis of minimization of the Lp-norm ∥x∥p= lim∈→+0ΣNi=1|xi|p+∈. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio α = P/N and the density ρ of non-zero elements in x in the limit P, N → ∞ while keeping α ~ O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation αc(ρ) holds universally as long as FTF can be characterized asymptotically by a rotationally invariant random matrix ensemble and FFTis typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (Phil. Trans. R. Soc. A, vol. 367, pp. 4273-4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.

A method of channel polarization, proposed by Arikan, allows us to construct efficient capacity-achieving channel codes. In the original work, binary input discrete memoryless channels are considered. A special case of q-ary channel polarization is considered by Şaşoğlu, Telatar, and Arikan. In this paper, we consider more general channel polarization on q-ary channels. We further show explicit constructions using Reed-Solomon codes, on which asymptotically fast channel polarization is induced.

A rate-dependent upper bound of the best achievable block error probability of polar codes with successive-cancellation decoding is derived.

Compressed sensing of sparse sources can be improved by incorporating prior knowledge of the source. In this paper we demonstrate a method for optimal selection of weights in weighted ℓ1norm minimization for a noiseless reconstruction model, and show the improvements in compression that can be achieved.

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).

Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.

We review some recent progresses in studies on speed of channel polarization. Firstly, results on a coderate-dependent upper bound of block error probability of polar codes with successive cancellation decoding are reviewed. Then an approach of constructing polar codes for non-binary input alphabet with asymptotic speed of polarization much faster than previous approaches is briefly described.

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.

Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength n tends to infinity. The difference between the bit error probability with blocklength n and the large-blocklength limit behaves asymptotically like ¿/n, where the coefficient ¿ depends on the ensemble, the number of iterations and the erasure probability of the BEC. In, ¿ is calculated for regular ensembles. In this paper, ¿ for irregular expurgated ensembles is derived. It is demonstrated that convergence of numerical estimates of ¿ to the analytic result is significantly fast for irregular unexpurgated ensembles.

Channel polarization is a method of constructing capacity achieving codes for symmetric binary-input discrete memoryless channels (B-DMCs). In the original paper, the construction complexity is exponential in the blocklength. In this paper, a new construction method for arbitrary symmetric binary memoryless channel (B-MC) with linear complexity in the blocklength is proposed. Furthermore, new upper bound and lower bound of the block error probability of polar codes are derived for the BEC and arbitrary symmetric B-MC, respectively.

We propose a new method of approximating mutual information based on maximum likelihood estimation of a density ratio function. The proposed method, Maximum Likelihood Mutual Information (MLMI), possesses useful properties, e.g., it does not involve density estimation, the global optimal solution can be efficiently computed, it has suitable convergence properties, and model selection criteria are available. Numerical experiments show that MLMI compares favorably with existing methods.

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 discuss optimal spreading sequences for CDMA channels under assumption of an arbitrary data modulation. We evaluate, via replica method, capacity of a randomly spread, perfect power controlled CDMA channel in the large-system limit, under the assumption that the correlation matrix of random spreading sequences is orthogonally invariant. On the basis of the analytical result, we show that the capacity is maximized with orthogonally invariant random Welch bound equality spreading sequences in cases of non-Gaussian data modulation.

This paper studies decoupling principle of a linear vector channel, which is an extension of CDMA and MIMO channels. We show that the scalar-channel characterization obtained via the decoupling principle is valid not only for collections of a large number of elements of input vector, as discussed in previous studies, but also for individual elements of input vector, i.e., the linear vector channel for individual elements of channel input vector is decomposed into a bank of independent scalar Gaussian channels in the large-system limit, where dimensions of channel input and output are both sent to infinity while their ratio fixed.

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 derive density evolution equations for a belief- propagation (BP) based detection algorithm for a vector channel under assumption of random channel parameters and in the large-system limit, considering the conditions of a general information symbol prior probability and a general memoryless channel. From the density evolution equations, it is observed that there exists a bank of independent single-user Gaussian channels which is equivalent to the original vector channel at each stage of the BP-based detection algorithm in the sense that the posterior probabilities of information symbol of a user are equivalent to each other. It means that the decoupling principle holds not only at equilibrium, but also at each stage of the algorithm. We also show a microscopic stability condition for the BP-based detection algorithm, in order to discuss possible relationship with the stability of replica-symmetric solutions against replica symmetry breaking in the replica analysis.

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.

We consider a problem of evaluating average of a certain scalar function involving a random matrix in the large- dimension limit, the solution of which is given in terms of the integrated R-transform of the limiting eigenvalue distribution of the random matrix. This problem therefore serves as an example in which not the functional form but the values of the R-transform plays a significant role, which can be regarded as making this problem unique in the context of application of random matrix and free probability theories. We furthermore discuss a dualistic structure with Legendre transformation involving the Shannon transform and the integrated R-transform, which underlies the problem.

Theoretically, maximum information transmission in a CDMA channel is achieved when the receiver performs joint user detection and decoding. Performance will be reduced if the receiver performs user detection, followed by per-user decoding. We discuss, on the basis of the replica analysis, the loss in information-transmission capability of a CDMA channel, due to the separation of user detection and decoding. We generalize the analysis on a CDMA channel with additive Gaussian channel noise, by Guo and Verdu, IEEE Trans. Info. Theory, 2005, in such a way as to allow channel noise to be non-Gaussian and/or non-additive. The loss, in spectral efficiency, is shown to be represented in terms of conditional entropies of channel outputs, as well as mean-squared error of the posterior-mean estimator of channel inputs

In this paper, we present a framework of statistical-mechanics-based analysis of sparsely-spread CDMA systems. The sparsely-spread CDMA can be considered as a simple mathematical model for various types of CDMA such as frequency-hopping (FH) CDMA and time-hopping (TH) CDMA. After presenting a general framework of analysis by the replica method, we analyze the system with Gaussian inputs, on the basis of the effective medium approximation. We obtain the multiuser efficiency and the spectral efficiency of the sparsely-spread CDMA system, and evaluate its performance in comparison with the densely-spread CDMA system.

This paper investigates the structure of the replica-symmetric (RS) solutions for randomly-spread CDMA obtained with the replica method. The objective of this investigation is to resolve the apparent inconsistency observed between the RS solutions for the individually-optimum (IO) detection and those for the jointly-optimum (JO) detection: They appear to be inconsistent with each other in the limit of high signal-to-noise ratio. Our result reveals that the RS solutions have a complex structure at high-SNR regime, which has been mostly overlooked in the literature

We present a theory to analyze the performance of the parallel interference canceller (PIC) for code-division multiple-access (CDMA) multiuser detection, applied to a randomly spread, fully synchronous baseband uncoded CDMA channel model with additive white Gaussian noise under perfect power control in the large-system limit. We reformulate PIC as an approximation to the belief propagation algorithm for the detection problem. We then apply the density evolution framework to analyze its detection dynamics. It turns out that density evolution for PIC is essentially the same as statistical neurodynamics, a theory to describe dynamics of a certain type of neural network model. Adopting this correspondence, we develop the density evolution framework for PIC using statistical neurodynamics. The resulting formulas, however, are only approximately correct for describing detection dynamics of PIC even in the large-system limit, because we ignore the Onsager reaction terms in the derivation. We then propose a modified PIC algorithm, in which we subtract the Onsager reaction terms algorithmically, for which the density evolution formulas give a correct description of the detection dynamics in the large-system limit.

In this paper we apply a modification scheme of the parallel interference cancellation (PIC), recently proposed by Tanaka and Okada based on techniques of the statistical neurodynamics, to the linear PIC (LPIC) with a tentative soft decision function f(x)=ax, and show that the modification enhances its convergence property.

A statistical-mechanical framework is presented to analyze the effect of phase mismatch in the multiuser detection problem for QPSK-modulated CDMA

Belief propagation (BP) is a universal method of stochastic reasoning. It gives exact inference for stochastic models with tree interactions and works surprisingly well even if the models have loopy interactions. Its performance has been analyzed separately in many fields, such as AI, statistical physics, information theory, and information geometry. This article gives a unified framework for understanding BP and related methods and summarizes the results obtained in many fields. In particular, BP and its variants, including tree reparameterization and concave-convex procedure, are reformulated with information-geometrical terms, and their relations to the free energy function are elucidated from an information-geometrical viewpoint. We then propose a family of new algorithms. The stabilities of the algorithms are analyzed, and methods to accelerate them are investigated.

We consider a canonical model for coded code-division multiple access (CDMA) with random spreading, where the receiver makes use of iterative belief-propagation (BP) joint decoding. We provide simple density-evolution analysis in the large-system limit (large number of users) of the performance of the BP decoder and of some suboptimal approximations based on interference cancellation (IC). Based on this analysis, we optimize the received user signal-to-noise ratio (SNR) distribution in order to maximize the system spectral efficiency for given user channel codes, channel load (users per chip), and target user bit-error rate (BER). The optimization of the received SNR distribution is obtained by solving a simple linear program and can be easily incorporated into practical power control algorithms. Remarkably, under the optimized SNR assignment, the suboptimal minimum mean-square error (MMSE) IC-based decoder performs almost as well as the more complex BP decoder. Moreover, for a large class of commonly used convolutional codes, we observe that the optimized SNR distribution consists of a finite number of discrete SNR levels. Based on this observation, we provide a low-complexity approximation of the MMSE-IC decoder that suffers from very small performance degradation while attaining considerable savings in complexity. As by-products of this work, we obtain a closed-form expression of the multiuser efficiency (ME) of power-mismatched MMSE filters in the large-system limit, and we extend the analysis of the symbol-by-symbol maximum a posteriori probability (MAP) multiuser detector in the large-system limit to the case of nonconstant user powers and nonuniform symbol prior probabilities.

Since the proposal of turbo codes in 1993, many studies have appeared on this simple and new type of codes which give a powerful and practical performance of error correction. Although experimental results strongly support the efficacy of turbo codes, further theoretical analysis is necessary, which is not straightforward. It is pointed out that the iterative decoding algorithm of turbo codes shares essentially similar ideas with low-density parity-check (LDPC) codes, with Pearl's belief propagation algorithm applied to a cyclic belief diagram, and with the Bethe approximation in statistical physics. Therefore, the analysis of the turbo decoding algorithm will reveal the mystery of those similar iterative methods. In this paper, we recapture and extend the geometrical framework initiated by Richardson to the information geometrical framework of dual affine connections, focusing on both of the turbo and LDPC decoding algorithms. The framework helps our intuitive understanding of the algorithms and opens a new prospect of further analysis. We reveal some properties of these codes in the proposed framework, including the stability and error analysis. Based on the error analysis, we finally propose a correction term for improving the approximation.

The expectation-maximization (EM) algorithm with split-and-merge operations (SMEM algorithm) proposed by Ueda, Nakano, Ghahramani, and Hinton (2000) is a nonlocal searching method, applicable to mixture models, for relaxing the local optimum property of the EM algorithm. In this article, we point out that the SMEM algorithm uses the acceptance-rejection evaluation method, which may pick up a distribution with smaller likelihood, and demonstrate that an increase in likelihood can then be guaranteed only by comparing log likelihoods.

We present a theory, based on statistical mechanics, to evaluate analytically the performance of uncoded, fully synchronous, randomly spread code-division multiple-access (CDMA) multiuser detectors with additive white Gaussian noise (AWGN) channel, under perfect power control, and in the large-system limit. Application of the replica method, a tool developed in the literature of statistical mechanics, allows us to derive analytical expressions for the bit-error rate, as well as the multiuser efficiency, of the individually optimum (IO) and jointly optimum (JO) multiuser detectors over the whole range of noise levels. The information-theoretic capacity of the randomly spread CDMA channel and the performance of decorrelating and linear minimum mean-square error (MMSE) detectors are also derived in the same replica formulation, thereby demonstrating validity of the statistical-mechanical approach.

The mystery of belief propagation (BP) decoder, especially of the turbo decoding, is studied from information geometrical viewpoint. The loopy belief network (BN) of turbo codes makes it difficult to obtain the true “belief” by BP, and the characteristics of the algorithm and its equilib- rium are not clearly understood. Our study gives an intuitive understand- ing of the mechanism, and a new framework for the analysis. Based on the framework, we reveal basic properties of the turbo decoding.

We report a result of perturbation analysis on decoding error of the belief propagation decoder for Gallager codes. The analysis is based on infor- mation geometry, and it shows that the principal term of decoding error at equilibrium comes from the m-embedding curvature of the log-linear submanifold spanned by the estimated pseudoposteriors, one for the full marginal, and K for partial posteriors, each of which takes a single check into account, where K is the number of checks in the Gallager code. It is then shown that the principal error term vanishes when the parity-check matrix of the code is so sparse that there are no two columns with overlap greater than 1.

We analyze the bit error probability of multiuser demodulators for direct(cid:173) sequence binary phase-shift-keying (DSIBPSK) CDMA channel with ad(cid:173) ditive gaussian noise. The problem of multiuser demodulation is cast into the finite-temperature decoding problem, and replica analysis is ap(cid:173) plied to evaluate the performance of the resulting MPM (Marginal Pos(cid:173) terior Mode) demodulators, which include the optimal demodulator and the MAP demodulator as special cases. An approximate implementa(cid:173) tion of demodulators is proposed using analog-valued Hopfield model as a naive mean-field approximation to the MPM demodulators, and its performance is also evaluated by the replica analysis. Results of the per(cid:173) formance evaluation shows effectiveness of the optimal demodulator and the mean-field demodulator compared with the conventional one, espe(cid:173) cially in the cases of small information bit rate and low noise level.

I present a general theory of mean-field approximation based on information geometry and applicable not only to Boltzmann machines but also to wider classes of statistical models. Using perturbation expansion of the Kullback divergence (or Plefka expansion in statistical physics), a formulation of mean-field approximation of general orders is derived. It includes in a natural way the "naive" mean-field approximation and is consistent with the Thouless-Anderson-Palmer (TAP) approach and the linear response theorem in statistical physics.

Mean field approximation (MFA) is an effective method to reduce the amount of computation for Boltzmann machine (BM) learning, but at the expense of losing accuracy. To improve the accuracy, one uses linear response theorem (LRT) in MFA and/or one incorporates higher-order terms of the Taylor-expanded Gibbs free energy that is used to derive MFA. In this paper, we discuss the effectiveness of this incorporation of the higher-order terms for the MFA based on the LRT. We examine the effectiveness for the BM with hidden units. When the MFA based on the LRT is used, one can use one-shot algorithm in the case of BM without hidden units, for which the effectiveness has already be examined, but one has to iteratively estimate the expectations and update weights and biases in the case of BM with hidden units, for which the effectiveness has not be examined yet. By numerical experiments, we showed that the incorporation of the higher-order terms is more effective as far as the learning had converged.

We present a formulation of mean-field approximation for layered feedforward stochastic networks. In this formulation, one can obtain not only estimates of averages for state variables of the networks but also those of intra-layer correlations, the latter of which cannot be obtained by the conventional mean-field approximation. Moreover, this formulation provides a framework to treat "conditional" expectations, expectations under the constraint that external information about statistics are fed to some layers of the network which plays an important role in several applications such as the Helmholtz machine.