Pascal O. Vontobel

Approximating the permanent of a complex-valued matrix is a fundamental problem with applications in Boson sampling and probabilistic inference. In this paper, we extend factor-graph-based methods for approximating the permanent of non-negative-real-valued matrices that are based on running the sum-product algorithm (SPA) on standard normal factor graphs, to factor-graph-based methods for approximating the permanent of complex-valued matrices that are based on running the SPA on double-edge normal factor graphs. On the algorithmic side, we investigate the behavior of the SPA, in particular how the SPA fixed points change when transitioning from real-valued to complex-valued matrix ensembles. On the analytical side, we use graph covers to analyze the Bethe approximation of the permanent, i.e., the approximation of the permanent that is obtained with the help of the SPA. This combined algorithmic and analytical perspective provides new insight into the structure of Bethe approximations in complex-valued problems and clarifies when such approximations remain meaningful beyond the non-negative-real-valued settings.

For various classes of graphical models it has been observed that the ratio of the partition sum to its Bethe approximation is often close to being the square of the ratio of the partition sum to its degree-2 Bethe approximation. This is of relevance because the latter ratio can often better be analyzed and/or quantified than the former ratio. In this paper, we give some justifications for the observed relationship between these two ratios and then analyze these ratios for two classes of log-supermodular graphical models.

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy function associated with some suitably defined factor graph; the resulting approximation to the permanent is called the Bethe permanent. Vontobel gave a combinatorial characterization of the Bethe permanent via degree- M Bethe permanents, which is based on degree- M covers of the underlying factor graph. In this paper, we prove a degree- M -Bethe-permanent-based lower bound on the permanent of a non-negative matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree- M -Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limit M → ∞, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix. Moreover, we prove similar results for an approximation to the permanent known as the (scaled) Sinkhorn permanent.

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first derive an achievable secure rate for ISI-WTCs without imposing any constraints on the input distribution. Afterwards, we focus on the setup where the input distribution of the ISI-WTC is constrained to be a time-invariant finite-order Markov chain. Optimizing the parameters of this Markov chain toward maximizing the achievable secure rates is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function with a suitable~surrogate function whose maximum can be found efficiently. Although the secure rates achieved in the unconstrained setup are potentially larger than the secure rates achieved in the constrained setup, the latter setup has the advantage of leading to efficient algorithms for estimating and optimizing the achievable secure rates, and also has the benefit of being the basis of efficient coding schemes.

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first derive an achievable secure rate for ISI-WTCs without imposing any constraints on the input distribution. Afterwards, we focus on the setup where the input distribution of the ISI-WTC is constrained to be a time-invariant finite-order Markov chain. Optimizing the parameters of this Markov chain toward maximizing the achievable secure rates is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function by a suitable surrogate function whose maximum can be found efficiently. Although the secure rates achieved in the unconstrained setup are potentially larger than the secure rates achieved in the constraint setup, the latter setup has the advantage of leading to efficient algorithms for estimating and optimizing the achievable secure rates, and also has the benefit of being the basis of efficient coding schemes.

We consider sparse regression codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves. Furthermore, we apply our proposed concatenated coding scheme to spatially coupled SPARCs. Besides that, we also introduce a novel class of design matrices, i.e., matrices that describe the encoding process, based on circulant matrices derived from Frank or from Milewski sequences. This class of design matrices has comparable encoding and decoding computational complexity as well as very close performance with the commonly-used class of design matrices based on discrete Fourier transform (DFT) matrices, but gives us more degrees of freedom when designing SPARCs for various applications.

We consider sparse superposition codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves. Furthermore, we apply our proposed concatenated coding scheme to spatially coupled SPARCs. Besides that, we also introduce a novel class of design matrices, i.e., matrices that describe the encoding process, based on circulant matrices derived from Frank or from Milewski sequences. This class of design matrices has comparable encoding and decoding computational complexity as well as very close performance with the commonly-used class of design matrices based on discrete Fourier transform (DFT) matrices, but gives us more degrees of freedom when designing SPARCs for various applications.

In previous work, we have shown that pseudocodewords can be used to characterize the behavior of decoders not only for classical codes but also for quantum stabilizer codes. With the insights obtained from this pseudocodewords-based analysis, we have also introduced a two-stage decoder based on pseudocodewords for quantum cycle codes that leads to improved decoding performance. In this paper, we consider quantum (stabilizer) color codes and propose a two-stage decoder that is a generalization of the pseudocodeword-based decoder for quantum cycle codes. Our decoder has only local or error-weight-dependent operations of low computational complexity and better decoding performance compared with previous decoding approaches for these types of codes.

We consider the scenario of classical communication over a finite-dimensional quantum channel with memory using a separable-state input ensemble and local output measurements. We propose algorithms for estimating the information rate of such communication setups, along with algorithms for bounding the information rate based on so-called auxiliary channels. Some of the algorithms are extensions of their counterparts for (classical) finite-state-machine channels. Notably, we discuss suitable graphical models for doing the relevant computations. Moreover, the auxiliary channels are learned in a data-driven approach; i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.

We consider the scenario of classical communication over a finite-dimensional quantum channel with memory using a separable-state input ensemble and local output measurements. We propose algorithms for estimating the information rate of such communication setups, along with algorithms for bounding the information rate based on so-called auxiliary channels. Some of the algorithms are extensions of their counterparts for (classical) finite-state-machine channels. Notably, we discuss suitable graphical models for doing the relevant computations. Moreover, the auxiliary channels are learned in a data-driven approach; i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.