Search

A Gibbs distribution based combinatorial optimization algorithm for joint antenna splitting and user scheduling problem in full duplex massive multiple-input multiple-output (MIMO) system is proposed in this paper. The optimal solution of this problem can be determined by exhaustive search. However, the complexity of this approach becomes prohibitive in practice when the sample space is large, which is usually the case in massive MIMO systems. Our algorithm overcomes this drawback by converting the original problem into a Kullback-Leibler (KL) divergence minimization problem, and solving it through a related dynamical system via a stochastic gradient descent method. Using this approach, we improve the spectral efficiency (SE) of the system by performing joint antenna splitting and user scheduling. Additionally, numerical results show that the SE curves obtained with our proposed algorithm overlap with the curves achieved by exhaustive search for user scheduling. [ABSTRACT FROM AUTHOR]

The world’s first 2 $\times $ 30k-spin multi-chip CMOS annealing processor (AP)—based on the processing-in-memory approach for solving large-scale combinatorial optimization problem—was developed. To expand the bit width of coefficients and enhance the scalability of the AP, it has three key features: an expandable and high-accuracy spin operator for local communication, a highly integrated spin circuit using direct access to SRAM, and a low-latency inter-chip interface that does not affect the runtime or results of the annealing process. The AP is fabricated on the basis of 40-nm CMOS technology. It was experimentally demonstrated that the spin-flip ratio of the processor agrees well with theoretical values based on the Gibbs distribution over a wide temperature range. As a result, under two-chip operation with 2 $\times $ 30k spins, the AP achieves an annealing time of 22 $\mu \text{s}$ , which is 455 times and 2.6 $\times $ 104 times faster than those achieved by our previous CMOS-AP and a conventional CPU, respectively. Moreover, its energy efficiency is 1.75 $\times $ 105 times higher than that of a conventional CPU-based algorithm. [ABSTRACT FROM AUTHOR]

We investigate a probabilistic model for routeing in a multihop ad hoc communication network, where each user sends a message to the base station. Messages travel in hops via other users, used as relays. Their trajectories are chosen at random according to a Gibbs distribution, which favors trajectories with low interference, measured in terms of signal-to-interference ratio. This model was introduced in our earlier paper, where we expressed, in the limit of a high density of users, the typical distribution of the family of trajectories in terms of a law of large numbers. In this paper, we derive its qualitative properties. We analytically identify the emerging typical scenarios in three extreme regimes. We analyze the typical number of hops and the typical length of a hop and the deviation of the trajectory from the straight line, regime 1 in the limit of a large communication area and large distances and regime 2 in the limit of a strong interference weight. In both the regimes, the typical trajectory approaches a straight line quickly, in regime 1 with equal hop lengths. Interestingly, in regime 2, the typical length of a hop diverges logarithmically in the distance of the transmitter to the base station. We further analyze (regime 3) local and global repulsive effects of a densely populated subarea on the trajectories. [ABSTRACT FROM AUTHOR]

Distributed link scheduling algorithms based on carrier sense multiple access and Gibbs sampling are known to achieve throughput optimality, if certain parameters called the fugacities are appropriately chosen. However, the problem of computing these fugacities is NP-hard. Further, the complexity of the existing stochastic gradient descent-based algorithms that compute the exact fugacities scales exponentially with the network size. In this paper, we propose a general framework to estimate the fugacities using regional free energy approximations. In particular, we derive explicit expressions for approximate fugacities corresponding to any feasible service rate vector. We further prove that our approximate fugacities are exact for the class of chordal graphs. A distinguishing feature of our work is that the regional approximations that we propose are tailored to conflict graphs with small cycles, which is a typical characteristic of wireless networks. Numerical results indicate that the proposed methods are quite accurate, and significantly outperform the existing approximation techniques. [ABSTRACT FROM AUTHOR]

We consider a carrier sense multiple access (CSMA)-based scheduling algorithm for a single-hop wireless network under a realistic signal-to-interference-plus-noise ratio model for the interference. We propose two local optimization-based approximation algorithms to efficiently estimate certain attempt rate parameters of CSMA called fugacities. It is known that adaptive CSMA can achieve throughput optimality by sampling feasible schedules from a Gibbs distribution, with appropriate fugacities. Unfortunately, obtaining these optimal fugacities is an NP-hard problem. Furthermore, the existing adaptive CSMA algorithms use a stochastic gradient descent-based method, which usually entails an impractically slow (exponential in the size of the network) convergence to the optimal fugacities. To address this issue, we first propose an algorithm to estimate the fugacities, that can support a given set of desired service rates. The convergence rate and the complexity of this algorithm are independent of the network size, and depend only on the neighborhood size of a link. Furthermore, we show that the proposed algorithm corresponds exactly to performing the well-known Bethe approximation to the underlying Gibbs distribution. Then, we propose another local algorithm to estimate the optimal fugacities under a utility maximization framework, and characterize its accuracy. Numerical results indicate that the proposed methods have a good degree of accuracy, and achieve extremely fast convergence to near-optimal fugacities, and often outperform the convergence rate of the stochastic gradient descent by a few orders of magnitude. [ABSTRACT FROM AUTHOR]

This paper presents a statistical-mechanics-inspired procedure for optimization of the sensor field configuration to detect mobile targets. The key idea is to capture the low-dimensional behavior of the sensor field configurations across the Pareto front in a multiobjective scenario for optimal sensor deployment, where the nondominated points are concentrated within a small region of the large-dimensional decision space. The sensor distribution is constructed using location-dependent energy-like functions and intensive temperature-like parameters in the sense of statistical mechanics. This low-dimensional representation is shown to permit rapid optimization of the sensor field distribution on a high-fidelity simulation test bed of distributed sensor networks. [ABSTRACT FROM PUBLISHER]

Backbone anatomical structure detection and labeling is a necessary step for various analysis tasks of the vertebral column. Appearance, shape and geometry measurements are necessary for abnormality detection locally at each disc and vertebrae (such as herniation) as well as globally for the whole spine (such as spinal scoliosis). We propose a two-level probabilistic model for the localization of discs from clinical magnetic resonance imaging (MRI) data that captures both pixel- and object-level features. Using a Gibbs distribution, we model appearance and spatial information at the pixel level, and at the object level, we model the spatial distribution of the discs and the relative distances between them. We use generalized expectation-maximization for optimization, which achieves efficient convergence of disc labels. Our two-level model allows the assumption of conditional independence at the pixel-level to enhance efficiency while maintaining robustness. We use a dataset that contains 105 MRI clinical normal and abnormal cases for the lumbar area. We thoroughly test our model and achieve encouraging results on normal and abnormal cases. [ABSTRACT FROM AUTHOR]

We present a number of contributions to the LP relaxation approach to weighted constraint satisfaction (= Gibbs energy minimization). We link this approach to many works from constraint programming, which relation has so far been ignored in machine vision and learning. While the approach has been mostly considered only for binary constraints, we generalize it to n-ary constraints in a simple and natural way. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion-however, we consider using other bound-optimizing algorithms as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black box, which is analogical to propagators for global constraints CSP. Diffusion exactly solves permuted n-ary supermodular problems. A hierarchy of gradually tighter LP relaxations is obtained simply by adding various zero constraints and coupling them in various ways to existing constraints. Zero constraints can be added incrementally, which leads to a cutting-plane algorithm. The separation problem is formulated as finding an unsatisfiable subproblem of a CSP. [ABSTRACT FROM AUTHOR]

Maximization of the information divergence from any hierarchical log-linear model is studied. A new upper bound on the maximum is presented and its tightness analyzed. For the models given by the bases of a matroid, the latter is related to matroid representations by partitions or, equivalently, to ideal secret-sharing schemes. A new link between the divergence maximization, the maximum-likelihood principle, and secret sharing is established. [ABSTRACT FROM AUTHOR]

As manufacturing technology reaches nanoscale, architectural designs need to accommodate the uncertainty inherent at such scales. These uncertainties are germane in the minuscule dimension of the devices, quantum physical effects, reduced noise margins, system energy levels reaching computing thermal limits, manufacturing defects, aging, and many other factors. Defect-tolerant architectures and their reliability measures will gain importance for logic and micro-architecture designs based on nanoscale substrates. Recently, the Markov random field has been proposed as a model of computation for nanoscale logic gates. This opens up new possibilities in designing logic and architecture where the conventional Boolean logic is replaced by a notion of an energy distribution function based on Gibbs distribution. In this computational scheme, probabilities of energy levels at various gate inputs and interconnects are considered, and belief propagation is used to propagate these probability distributions from the primary inputs to the primary outputs of a Boolean network. In this paper, we take this approach further by automating this computational scheme and belief propagation algorithm. We have developed MATLAB-based libraries for fundamental logic gates that can compute probability distributions and entropies at the outputs for specified discrete input distributions and in the presence of noise at the inputs and interconnects. Our tool automates the evaluation of reliability measures of combinational logic blocks. The effectiveness of this automation is illustrated in this paper by automatically deriving various reliability results for defect-tolerant architectures, such as triple modular redundancy (TMR), cascaded TMR, and multistage iterations of these. Also, signal noise is modeled as uniform and Gaussian distributions at the inputs and interconnects, so as to evaluate reliability-redundancy tradeoffs of these architectural configurations taking into account such noise models. [ABSTRACT FROM PUBLISHER]