Search

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

Nonconvex constraints are valuable regularizers in many optimization problems. In particular, sparsity constraints have had a significant impact on sampling theory, where they are used in compressed sensing and allow structured signals to be sampled far below the rate traditionally prescribed. Nearly, all of the theory developed for compressed sensing signal recovery assumes that samples are taken using linear measurements. In this paper, we instead address the compressed sensing recovery problem in a setting where the observations are nonlinear. We show that, under conditions similar to those required in the linear setting, the iterative hard thresholding algorithm can be used to accurately recover sparse or structured signals from few nonlinear observations. Similar ideas can also be developed in a more general nonlinear optimization framework. In the second part of this paper, we therefore present related result that shows how this can be done under sparsity and union of subspaces constraints, whenever a generalization of the restricted isometry property traditionally imposed on the compressed sensing system holds. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the convergence speed of the Arimoto-Blahut algorithm. For many channel matrices, the convergence speed is exponential, but for some channel matrices it is slower than exponential. By analyzing the Taylor expansion of the defining function of the Arimoto-Blahut algorithm, we will make the conditions clear for the exponential or slower convergence. The analysis of the slow convergence in this paper is new. Based on this analysis, we will compare the convergence speeds of the Arimoto-Blahut algorithm numerically with the values obtained in our theorems for several channel matrices. The purpose of this paper is to obtain a complete understanding of the convergence speed of the Arimoto-Blahut algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider a general K-user Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC). We assume that the channel state is deterministic and known to all the nodes. While the private-message capacity region is well known to be achievable with dirty paper coding (DPC), we are interested in the simpler linearly precoded transmission schemes. In particular, we focus on linear precoding schemes combined with rate-splitting (RS). First, we derive an achievable rate region with minimum mean square error (MMSE) precoding at the transmitter and joint decoding of the sub-messages at the receivers. Then, we study the achievable sum rate of this scheme and obtain two findings: 1) an analytically tractable upper bound on the sum rate that is shown numerically to be a close approximation, and 2) how to reduce the number of active streams – crucial to the overall complexity – while preserving the sum rate to within a constant loss. The latter results in two practical algorithms: a stream elimination algorithm and a stream ordering algorithm. Finally, we investigate the constant-gap optimality of linearly precoded RS with respect to the capacity. Our result reveals that, while the achievable rate of linear precoding alone can be arbitrarily far from the capacity, the introduction of RS can help achieve the capacity region to within a constant gap in the two-user case. Nevertheless, we prove that the RS scheme’s constant-gap optimality does not extend to the three-user case. Specifically, we show, through a pathological example, that the gap between the sum rate and the sum capacity can be unbounded. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

Gossip protocols are popular methods for average consensus problems in distributed computing. We prove new convergence guarantees for a variety of such protocols, including path, clique, and synchronous pairwise gossip. These arise by exploiting the connection between these protocols and the block randomized Kaczmarz method for solving linear systems. Moreover, we extend existing convergence results for block randomized Kaczmarz to allow for a more general choice of blocks, rank-deficient systems, and provide a tighter convergence rate guarantee. Previous results for block randomized Kaczmarz assumed blocks formed a paving of the systems; our analysis, contrary to the title of our paper, generalizes to a broader class of blocks that we call coverings. We furthermore apply this analysis to inconsistent consensus models and obtain similar guarantees. An extensive empirical analysis of these methods is provided for a variety of synthetic and real networks. [ABSTRACT FROM AUTHOR]

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules. [ABSTRACT FROM AUTHOR]

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to the problem of recovering a signal $ {x}_{\star }\in \mathbb {C}^{n}$ from its phaseless measurements $\text {y}_{\text {i}}=| {a}_{i}^{ \mathsf {H}} {x}_{\star }|$ , where $\{ {a}_{\text {i}}\}_{\text {i}=1}^{ {m}}$ are the measurement vectors. Spectral method is widely used for initialization in many phase retrieval algorithms. The quality of spectral initialization can have a major impact on the overall algorithm. In this paper, we focus on the model where $ {A}=[ {a}_{1},\ldots, {a}_{ {m}}]^{ \mathsf {H}}$ has orthonormal columns, and study the spectral initialization under the asymptotic setting $ {m}, {n}\to \infty $ with $ {m}/ {n}\to \delta \in (1,\infty)$. We use the expectation propagation framework to characterize the performance of spectral initialization for Haar distributed matrices. Our numerical results confirm that the predictions of the EP method are accurate for not-only Haar distributed matrices, but also for realistic Fourier based models (e.g. the coded diffraction model). The main findings of this paper are the following: 1) There exists a threshold on $\delta $ (denoted as $\delta _{ \mathrm {weak}}$) below which the spectral method cannot produce a meaningful estimate. We show that $\delta _{ \mathrm {weak}}=2$ for the column-orthonormal model. In contrast, previous results by Mondelli and Montanari show that $\delta _{ \mathrm {weak}}=1$ for the i.i.d. Gaussian model. 2) The optimal design for the spectral method coincides with that for the i.i.d. Gaussian model, where the latter was recently introduced by Luo, Alghamdi and Lu. [ABSTRACT FROM AUTHOR]

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta }$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta $ of tests an individual can be placed in, or the maximum number $\Gamma $ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta $ -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma $ -sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta (1)$ , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms. [ABSTRACT FROM AUTHOR]

This paper considers the problem of secure parameter estimation when an estimation algorithm is prone to causative attacks. Causative attacks, in general, target decision-making algorithms (e.g., inference or learning algorithm) to alter their decisions in specific scenarios (e.g., distort parameter estimates for specific ranges of the parameter of interest). Such attacks influence the decisions via tampering with the mechanisms through which an algorithm acquires the statistical model of the population about which it aims to form a decision. Such attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the statistical model. In the presence of causative attacks, inference algorithms operate under a distorted statistical model for the data samples. This paper introduces a notion of secure parameter estimation and formalizes a framework under which secure estimation can be formulated and analyzed. The central premise underlying the secure estimation framework is that forming secure estimates introduces a new dimension to the estimation objective, pertaining to detecting attacks and isolating the true model. Since detection and isolation decisions themselves are imperfect, their inclusion induces an inherent coupling between the desired secure estimation objective and the auxiliary detection and isolation decisions that need to be formed in conjunction with the estimates. This paper establishes the fundamental interplay among these decisions, and characterizes the general decision rules in closed-forms for any desired estimation cost function. Furthermore, to circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm is provided, which is shown to enjoy certain optimality guarantees. Finally, the theory developed is applied to secure parameter estimation in sensor networks. [ABSTRACT FROM AUTHOR]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

The Binary Iterative Hard Thresholding (BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. Despite considerable research on this algorithm, a theoretical understanding of the corresponding approximation error and convergence rate still remains an open problem. This paper shows that the normalized version of BIHT (NBIHT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using $m$ one-bit measurements of an $s$ -sparse vector $x$ , we prove that the approximation error of NBIHT is of order $O \left ({\frac{1 }{ m }}\right)$ up to logarithmic factors, which matches the information-theoretic lower bound $\Omega \left ({\frac{1 }{ m }}\right)$ proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square-root error decay rate $O \left ({\frac{1 }{ m^{1/2} }}\right)\vphantom {{\left ({\frac{1 }{ m^{1/2} }}\right)}^{'}}$. [ABSTRACT FROM AUTHOR]

Consider a massive random access scenario in which a small set of $k$ active users out of a large number of $n$ potential users need to be scheduled in $b\ge k$ slots. What is the minimum common feedback to the users needed to ensure that scheduling is collision-free? Instead of a naive scheme of listing the indices of the $k$ active users in the order in which they should transmit, at a cost of $k\log (n)$ bits, this paper shows that for the case of $b=k$ , the rate of the minimum fixed-length common feedback code scales only as $k \log (e)$ bits, plus an additive term that scales in $n$ as $\Theta (\log \log (n))$ for fixed $k$. If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires $k \log (e)$ bits, but the dependence on $n$ can be reduced to $O(1)$. When $b>k$ , the number of feedback bits needed for collision-free scheduling can be significantly further reduced. Moreover, a similar scaling on the minimum feedback rate is derived for the case of scheduling $m$ users per slot, when $k \le mb$. The problem of constructing a minimum collision-free feedback scheduling code is connected to that of constructing a perfect hashing family, which allows practical feedback scheduling codes to be constructed from perfect hashing algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a new algorithm, named Householder Dice (HD), for simulating dynamics on dense random matrix ensembles with rotational invariance. Examples include the Gaussian ensemble, the Haar-distributed random orthogonal ensemble, and their complex-valued counterparts. A “direct” approach to the simulation, where one first generates a dense $n \times n$ matrix from the ensemble, requires at least $\mathcal {O}(n^{2})$ resource in space and time. The HD algorithm overcomes this $\mathcal {O}(n^{2})$ bottleneck by using the principle of deferred decisions: rather than fixing the entire random matrix in advance, it lets the randomness unfold with the dynamics. At the heart of this matrix-free algorithm is an adaptive and recursive construction of (random) Householder reflectors. These orthogonal transformations exploit the group symmetry of the matrix ensembles, while simultaneously maintaining the statistical correlations induced by the dynamics. The memory and computation costs of the HD algorithm are $\mathcal {O}(nT)$ and $\mathcal {O}(nT^{2})$ , respectively, with $T$ being the number of iterations. When $T \ll n$ , which is nearly always the case in practice, the new algorithm leads to significant reductions in runtime and memory footprint. Numerical results demonstrate the promise of the HD algorithm as a new computational tool in the study of high-dimensional random systems. [ABSTRACT FROM AUTHOR]

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell $ defective items, where $0 \leq \ell < u$ , and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap. In this paper, we focus on the case $g > 0$ , i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$ ; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems. [ABSTRACT FROM AUTHOR]

In image detection, one problem is to test whether the set, though mainly consisting of uniformly scattered points, also contains a small fraction of points sampled from some (a priori unknown) curve, for example, a curve with Cα-norm bounded by β. One approach is to analyze the data by counting membership in multiscale multianisotropic strips, which involves an algorithm that delves into the length of the path connecting many consecutive “significant” nodes. In this paper, we develop the mathematical formalism of this algorithm and analyze the statistical property of the length of the longest significant run. The rate of convergence is derived. Using percolation theory and random graph theory, we present a novel probabilistic model named, pseudo-tree model. Based on the asymptotic results for the pseudo-tree model, we further study the length of the longest significant run in an “inflating” Bernoulli net. We find that the probability parameter p of significant node plays an important role: there is a threshold pc, such that in the cases of p < pc and p > pc, very different asymptotic behaviors of the length of the significant runs are observed. We apply our results to the detection of an underlying curvilinear feature and prove that the test based on our proposed longest run theory is asymptotically powerful. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

Line spectral estimation is a classical signal processing problem that aims to estimate the line spectra from their signal which is contaminated by deterministic or random noise. Despite a large body of research on this subject, the theoretical understanding of this problem is still elusive. In this paper, we introduce and quantitatively characterize the two resolution limits for the line spectral estimation problem under deterministic noise: one is the minimum separation distance between the line spectra that is required for exact detection of their number, and the other is the minimum separation distance between the line spectra that is required for a stable recovery of their supports. The quantitative results imply a phase transition phenomenon in each of the two recovery problems, and also the subtle difference between the two. We further propose a sweeping singular-value-thresholding algorithm for the number detection problem and conduct numerical experiments. The numerical results confirm the phase transition phenomenon in the number detection problem. [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

This paper revisits the ordered statistics decoding (OSD). It provides a comprehensive analysis of the OSD algorithm by characterizing the statistical properties, evolution and the distribution of the Hamming distance and weighted Hamming distance from codeword estimates to the received sequence in the reprocessing stages of the OSD algorithm. We prove that the Hamming distance and weighted Hamming distance distributions can be characterized as mixture models capturing the decoding error probability and code weight enumerator. Simulation and numerical results show that our proposed statistical approaches can accurately describe the distance distributions. Based on these distributions and with the aim to reduce the decoding complexity, several techniques, including stopping rules and discarding rules, are proposed, and their decoding error performance and complexity are accordingly analyzed. Simulation results for decoding various eBCH codes demonstrate that the proposed techniques can significantly reduce the decoding complexity with a negligible loss in the decoding error performance. [ABSTRACT FROM AUTHOR]

Communication for omniscience (CO) refers to the problem where the users in a finite set V observe a discrete multiple random source and want to exchange data over broadcast channels to reach omniscience, the state where everyone recovers the entire source. This paper studies how to improve the computational complexity for the problem of minimizing the sum-rate for attaining omniscience in V. While the existing algorithms rely on the submodular function minimization (SFM) techniques and complete in O(|V|2⋅SFM (|V|) time, we prove the strict strong map property of the nesting SFM problem. We propose a parametric (PAR) algorithm that utilizes the parametric SFM techniques and reduces the complexity to O(|V| ⋅SFM (|V|). We propose efficient solutions to the successive omniscience (SO): attaining omniscience successively in user subsets. We first focus on how to determine a complimentary subset X* ⊄ V in the existing two-stage SO such that if the local omniscience in X* is reached first, the global omniscience whereafter can still be attained with the minimum sum-rate. It is shown that such a subset can be extracted at one of the iterations of the PAR algorithm. We then propose a novel multi-stage SO strategy: a nesting sequence of complimentary user subsets X*(1) ⊄ . . . ⊆ X*(K) = V, the omniscience in which is attained progressively by the monotonic rate vectors rV(1) ≤ . . . rV(K). We propose algorithms to obtain this K-stage SO from the returned results by the PAR algorithm. The run time of these algorithms is the same as the PAR algorithm. [ABSTRACT FROM AUTHOR]

The Demirci-Selçuk’s meet-in-the-middle attack is one of the most important methods among all the cryptanalytic vectors, which gives the best result against the round-reduced AES with respect to the rounds, and tradeoffs between data, time and memory. While we have already built provable security models against the differential cryptanalysis, linear cryptanalysis cryptanalysis, impossible differential and zero-correlation linear cryptanalysis, the provable security against the meet-in-the-middle attack is missing. In this paper, we propose the subset representation of function based on which we could give an algorithm to compute the exact number of parameters of the Demirci-Selçuk’s distinguisher given the input and output, respectively. Experiments show that this algorithm can be more efficient than the automatical tool presented by Shi et al. at Asiacrypt 2018. We further extract a formula based on this algorithm and show an upper bound for the length of the Demirci-Selçuk’s distinguisher of an iterative SPN cipher. We prove that for an SPN block cipher whose block size equals the key size, an effective Demirci-Selçuk-type meet-in-the-middle distinguisher covers at most twice the maximum of the primitive indexes of the linear layer and its inverse. As a result, we show that the known length of the Demirci-Selçuk’s distinguisher of the AES-128 cannot be improved unless the details of the S-boxes are exploited, which demonstrates that the AES has a provable security against the Demirci-Selçuk’s meet-in-the-middle attack. [ABSTRACT FROM AUTHOR]

The paper addresses a sequential changepoint detection problem for a general stochastic model, assuming that the observed data may be non-i.i.d. (i.e., dependent and non-identically distributed) and prior distribution of the change point is arbitrary. Tartakovsky and Veeravalli (2005), Baron and Tartakovsky (2006), and, more recently, Tartakovsky (2017) developed a general asymptotic theory of changepoint detection for non-i.i.d. stochastic models, assuming certain stability of the log-likelihood ratio process, in the case of simple hypotheses when both pre-change and post-change models are completely specified. However, in most applications, the post-change distribution is not completely known. In the present paper, we generalize previous results to the case of parametric uncertainty, assuming that the parameter of the post-change distribution is unknown. We introduce two detection rules based on mixtures–the mixture Shiryaev rule and the mixture Shiryaev–Roberts rule–and study their asymptotic properties in the Bayesian context. In particular, we provide sufficient conditions under which these rules are first-order asymptotically optimal, minimizing moments of the delay to detection as the probability of false alarm approaches zero. [ABSTRACT FROM AUTHOR]

In many different applications, it is important to determine the Hilbert transform of a given function. However, it is generally impossible to calculate it in closed form. Therefore Hilbert transform approximations are used. This paper studies the convergence and divergence behavior of general classes of such approximation methods. These classes are characterized by two very natural axioms and they include basically all known traditional numerical algorithms. The convergence of these methods is investigated on a family of signal spaces of continuous functions with finite energy. These spaces are parametrized by a number which measures the energy concentration in the low frequency components of the signal. It is shown that stable methods only exist on signal spaces with a sufficient energy concentration and this paper gives some explicit examples of convergent methods. On all other spaces in the family of signal spaces, every sampling-based Hilbert transform approximation shows a blowup behavior of its peak value, i.e., on these spaces, every sampling-based Hilbert transform approximation diverges. [ABSTRACT FROM AUTHOR]

This paper studies the problem of inferring whether an agent is directly influenced by another agent over a network. Agent $i$ influences agent $j$ if they are connected (according to the network topology), and if agent $j$ uses the data from agent $i$ to update its online learning algorithm. The solution of this inference task is challenging for two main reasons. First, only the output of the learning algorithm is available to the external observer that must perform the inference based on these indirect measurements. Second, only output measurements from a fraction of the network agents is available, with the total number of agents itself being also unknown. The main focus of this paper is ascertaining under these demanding conditions whether consistent tomography is possible, namely, whether it is possible to reconstruct the interaction profile of the observable portion of the network, with negligible error as the network size increases. We establish a critical achievability result, namely, that for symmetric combination policies and for any given fraction of observable agents, the interacting and non-interacting agent pairs split into two separate clusters as the network size increases. This remarkable property then enables the application of clustering algorithms to identify the interacting agents influencing the observations. We provide a set of numerical experiments that verify the results for finite network sizes and time horizons. The numerical experiments show that the results hold for asymmetric combination policies as well, which is particularly relevant in the context of causation. [ABSTRACT FROM AUTHOR]

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding’s constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance. [ABSTRACT FROM AUTHOR]

Sparse subspace clustering (SSC) relies on sparse regression for accurate neighbor identification. Inspired by recent progress in compressive sensing, this paper proposes a new sparse regression scheme for SSC via two-step reweighted $\ell _{1} $ -minimization, which also generalizes a two-step $\ell _{1} $ -minimization algorithm introduced by E. J. Candès et al. in [The Annals of Statistics, vol. 42, no. 2, pp. 669–699, 2014] without incurring extra algorithmic complexity. To fully exploit the prior information offered by the computed sparse representation vector in the first step, our approach places a weight on each component of the regression vector, and solves a weighted LASSO in the second step. We propose a data weighting rule suitable for enhancing neighbor identification accuracy. Then, under the formulation of the dual problem of weighted LASSO, we study in depth the theoretical neighbor recovery rates of the proposed scheme. Specifically, an interesting connection between the locations of nonzeros of the optimal sparse solution to the weighted LASSO and the indexes of the active constraints of the dual problem is established. Afterwards, under the semi-random model, analytic probability lower/upper bounds for various neighbor recovery events are derived. Our analytic results confirm that, with the aid of data weighting and if the prior neighbor information is accurate enough, the proposed scheme with a higher probability can produce many correct neighbors and few incorrect neighbors as compared to the solution without data weighting. Computer simulations are provided to validate our analytic study and evidence the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. The main result of this paper gives a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. It is then shown that a small modification of the Candès–Recht nuclear norm minimization algorithm provides the required asymptotic solution whenever the sequence of problems is asymptotically solvable. The theory is fully deterministic, with no assumption of randomness. A number of open questions are listed. [ABSTRACT FROM AUTHOR]

Suppose that ${ { y}}= \lvert \text {A} { x}_{0}\rvert +\eta $ where ${ x}_{0}\in {\mathbb R} ^{{d}}$ is the target signal and $\eta \in {\mathbb R}^{{m}}$ is a noise vector. The aim of phase retrieval is to estimate ${x}_{0}$ from ${ { y}}$. A popular model for estimating ${ x}_{0}$ is the nonlinear least squares ${\widehat { {x}}}:={\mathrm{ argmin}}_{ x} \| \lvert \text {A} { x}\rvert - { { y}}\|_{2}$. One has already developed many efficient algorithms for solving the model, such as the seminal error reduction algorithm. In this paper, we present the estimation performance of the model with proving that $\| {\widehat { {x}}}- { x}_{0}\|\lesssim {\|\eta \|_{2}}/{\sqrt {{m}}}$ under the assumption of A being a Gaussian random matrix. We also prove the reconstruction error ${\|\eta \|_{2}}/{\sqrt {{m}}}$ is sharp. For the case where ${ x}_{0}$ is sparse, we study the estimation performance of both the nonlinear Lasso of phase retrieval and its unconstrained version. Our results are non-asymptotic, and we do not assume any distribution on the noise $\eta $. To the best of our knowledge, our results represent the first theoretical guarantee for the nonlinear least squares and for the nonlinear Lasso of phase retrieval. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on p nodes with maximum degree d can be learned in time f(d)p^2\log p , for a function f(d) defined explicitly in this paper, using nearly the information-theoretic minimum number of samples. [ABSTRACT FROM AUTHOR]

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security. [ABSTRACT FROM PUBLISHER]

In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately $k$ -sparse vector $x \in \mathbb {C} ^{n}$ given access to $y= |\Phi x|$ , where $|v|$ denotes the vector obtained from taking the absolute value of $v\in \mathbb {C} ^{n}$ coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a powerful technique based on Leave-One-Out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that NNM recovers an $d$ -by- $d$ rank- $r$ matrix with $\mathcal {O}(\mu r \log (\mu r) d\log d)$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, none of previous sample complexity results for tractable matrix completion algorithms satisfies these two properties simultaneously. [ABSTRACT FROM AUTHOR]

Graphical data is comprised of a graph with marks on its edges and vertices. The mark indicates the value of some attribute associated to the respective edge or vertex. Examples of such data arise in social networks, molecular and systems biology, and web graphs, as well as in several other application areas. Our goal is to design schemes that can efficiently compress such graphical data without making assumptions about its stochastic properties. Namely, we wish to develop a universal compression algorithm for graphical data sources. To formalize this goal, we employ the framework of local weak convergence, also called the objective method, which provides a technique to think of a marked graph as a kind of stationary stochastic processes, stationary with respect to movement between vertices of the graph. In recent work, we have generalized a notion of entropy for unmarked graphs in this framework, due to Bordenave and Caputo, to the case of marked graphs. We use this notion to evaluate the efficiency of a compression scheme. The lossless compression scheme we propose in this paper is then proved to be universally optimal in a precise technical sense. It is also capable of performing local data queries in the compressed form. [ABSTRACT FROM AUTHOR]

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers $\alpha $ , $\beta $ , and $\gamma $ , and degree sequences $\pi $ and $\pi '$ , the problem of determining whether there exists a simple bipartite graph with degree sequences $(\pi, \pi ')$ that has at most $\alpha $ ($\beta $ and $\gamma $) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence $\pi $ , a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is $\pi $ and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced. [ABSTRACT FROM AUTHOR]

The paper proposes an improved difference-of-syndromes decoding algorithm for decoding quadratic residue codes up to half the minimum distance. Therein, soft-decision information is not essential, but it can be used to speed up the computations. The improvement over the prior art is demonstrated by simulations. Moreover, the proposed algorithm is also compared with the classic Berlekamp-Massey algorithm by taking two BCH codes as examples. [ABSTRACT FROM AUTHOR]

Proving or disproving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving more than a few random variables is difficult to be proved or disproved manually. In 1997, Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under the framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. The way to automatically find a shortest proof or a smallest counterexample is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming. Lastly, we propose a scalable algorithmic framework based on the alternating direction method of multipliers to accelerate solving a multitude of user-specific problems whose overall computational cost can be amortized with the number of users, and present its publicly-available software implementation for large-scale problems. [ABSTRACT FROM AUTHOR]

This correspondence considers communication over two Gaussian channels with additive state interference anti noiseless output feedback-the multiple access channel (MAC) and the augmented broad- cast channel (ABC) (a special class of the physically degraded broadcast channel). The state interference is assumed to be available noncausally at the transmitters. Deterministic coding schemes for these two channels were suggested by Ozarow when there is no state present. Recently, Merhav and Weissman derived an optimal feedback coding scheme for the single-user Gaussian channel with additive state interference. Combining ideas from these two schemes, we extend Ozarow's coding algorithms to the state-dependent case, showing that the capacity regions of the MAC and the ABC are not affected, even though not all parts of the system have knowledge of the state. The proposed schemes attain a better error performance and reduce the coding complexity with respect to the standard random binning coding technique. [ABSTRACT FROM AUTHOR]

In this paper, we put forth a new joint sparse recovery algorithm called signal space matching pursuit (SSMP). The key idea of the proposed SSMP algorithm is to sequentially investigate the support of jointly sparse vectors to minimize the subspace distance to the residual space. Our performance guarantee analysis indicates that SSMP accurately reconstructs any row K-sparse matrix of rank r in the full row rank scenario if the sampling matrix $\mathbf {A}$ satisfies $\mathop{\mathrm{krank}}\limits (\mathbf {A}) \ge {K}+1$ , which meets the fundamental minimum requirement on $\mathbf {A}$ to ensure exact recovery. We also show that SSMP guarantees exact reconstruction in at most ${K}-{r}+\lceil \frac {{r}}{{L}} \rceil $ iterations, provided that $\mathbf {A}$ satisfies the restricted isometry property (RIP) of order ${L}({K}-{r})+{r}+1$ with $\delta _{{L}({K}-{r})+{r}+1} < \max \left \{{ \frac {\sqrt {{r}}}{\sqrt {{K}+\frac {{r}}{4}}+\sqrt {\frac {{r}}{4}}}, \frac {\sqrt {{L}}}{\sqrt {K}+1.15 \sqrt {{L}}} }\right \}$ , where L is the number of indices chosen in each iteration. This implies that the requirement on the RIP constant becomes less restrictive when r increases. Such behavior seems to be natural but has not been reported for most of conventional methods. We also show that if ${r}=1$ , then by running more than K iterations, the performance guarantee of SSMP can be improved to $\delta _{\lfloor 7.8{K} \rfloor } \le 0.155$. Furthermore, we show that under a suitable RIP condition, the reconstruction error of SSMP is upper bounded by a constant multiple of the noise power, which demonstrates the robustness of SSMP to measurement noise. Finally, from extensive numerical experiments, we show that SSMP outperforms conventional joint sparse recovery algorithms both in noiseless and noisy scenarios. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers has recently been adapted for linear programming decoding of low-density parity-check codes. The computation of the projection onto the parity polytope is the core of this algorithm and usually involves a sorting operation, which is the main effort of the projection. In this paper, we present an algorithm with low complexity to compute this projection. The algorithm relies on new findings in the recursive structure of the parity polytope and iteratively fixes selected components. As shown in our realistic simulation setup, it requires up to 37% less arithmetical operations compared with state-of-the-art projections. Additionally, it does not involve a sorting operation, which is needed in all exact state-of-the-art projection algorithms. These two benefits make it appealing for efficient hardware and software implementations. [ABSTRACT FROM AUTHOR]

The sparse representation classifier (SRC) has been utilized in various classification problems, which makes use of $\ell 1$ minimization and works well for image recognition satisfying a subspace assumption. In this paper we propose a new implementation of SRC via screening, establish its equivalence to the original SRC under regularity conditions, and prove its classification consistency under a latent subspace model and contamination. The results are demonstrated via simulations and real data experiments, where the new algorithm achieves comparable numerical performance and significantly faster. [ABSTRACT FROM AUTHOR]

Linear regression without correspondences is the problem of performing a linear regression fit to a dataset for which the correspondences between the independent samples and the observations are unknown. Such a problem naturally arises in diverse domains such as computer vision, data mining, communications and biology. In its simplest form, it is tantamount to solving a linear system of equations, for which the entries of the right hand side vector have been permuted. This type of data corruption renders the linear regression task considerably harder, even in the absence of other corruptions, such as noise, outliers or missing entries. Existing methods are either applicable only to noiseless data or they are very sensitive to initialization or they work only for partially shuffled data. In this paper we address these issues via an algebraic geometric approach, which uses symmetric polynomials to extract permutation-invariant constraints that the parameters $\xi ^{*} \in \mathbb {R} ^{\text {n}}$ of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains $\xi ^{*}$ in its root locus. Using the machinery of algebraic geometry we prove that as long as the independent samples are generic, this polynomial system is always consistent with at most n! complex roots, regardless of any type of corruption inflicted on the observations. The algorithmic implication of this fact is that one can always solve this polynomial system and use its most suitable root as initialization to the Expectation Maximization algorithm. To the best of our knowledge, the resulting method is the first working solution for small values of n able to handle thousands of fully shuffled noisy observations in milliseconds. [ABSTRACT FROM AUTHOR]

The problem of imaging point objects can be formulated as estimation of an unknown atomic measure from its ${M}+1$ consecutive noisy Fourier coefficients. The standard resolution of this inverse problem is $1/{M}$ and super-resolution refers to the capability of resolving atoms at a higher resolution. When any two atoms are less than $1/{M}$ apart, this recovery problem is highly challenging and many existing algorithms either cannot deal with this situation or require restrictive assumptions on the sign of the measure. ESPRIT is an efficient method which does not depend on the sign of the measure. This paper provides an explicit error bound on the support matching distance of ESPRIT in terms of the minimum singular value of Vandermonde matrices. When the support consists of multiple well-separated clumps and noise is sufficiently small, the support error by ESPRIT scales like $\text {SRF}^{2\lambda -2} \times \text {Noise}$ , where the Super-Resolution Factor (SRF) governs the difficulty of the problem and $\lambda $ is the cardinality of the largest clump. Our error bound matches the min-max rate of a special model with one clump of closely spaced atoms up to a factor of $M$ in the small noise regime, and therefore establishes the near-optimality of ESPRIT. Our theory is validated by numerical experiments. [ABSTRACT FROM AUTHOR]

So-called improper complex signals have been shown to be beneficial in the single-antenna two-user Gaussian interference channel under the assumptions that all input signals are Gaussian and that we treat interference as noise (TIN). This result has been obtained under a restriction to pure strategies without time-sharing, and it was extended to the case where the rates, but not the transmit powers, may be averaged over several transmit strategies. In this paper, we drop such restrictions and discuss the most general case of coded time-sharing, where both the rates and the powers may be averaged. Since coded time-sharing can in general not be expressed by means of a convex hull of the rate region, we have to account for the possibility of time-sharing already during the optimization of the transmit strategy. By means of a novel channel enhancement argument, we prove a surprising result: proper signals are optimal if coded time-sharing is allowed. In addition to establishing this result, we present an algorithm to compute the corresponding achievable rate region. [ABSTRACT FROM AUTHOR]

In the problem of structured signal recovery from high-dimensional linear observations, it is commonly assumed that full-precision measurements are available. Under this assumption, the recovery performance of the popular Generalized Lasso (G-Lasso) is by now well-established. In this paper, we extend these types of results to the practically relevant settings with quantized measurements. We study two extremes of the quantization schemes, namely, uniform and one-bit quantization; the former imposes no limit on the number of quantization bits, while the second only allows for one bit. In the presence of a uniform dithering signal and when measurement vectors are sub-gaussian, we show that the same algorithm (i.e., the G-Lasso) has favorable recovery guarantees for both uniform and one-bit quantization schemes. Our theoretical results, shed light on the appropriate choice of the range of values of the dithering signal and accurately capture the error dependence on the problem parameters. For example, our error analysis shows that the G-Lasso with one-bit uniformly dithered measurements leads to only a logarithmic rate loss compared to the full-precision measurements. [ABSTRACT FROM AUTHOR]

The collision channel without feedback (CCw/oFB) introduced by Massey and Mathys, depicts a scenario where multiple users share a communication channel but have arbitrary time offsets, and can never learn these time offsets due to the lack of feedback. This paper considers an extension of the CCw/oFB, which allows the receiver to use successive interference cancellation (SIC) to cancel the interference caused by those collided packets whose contents have been known by the receiver. We derive the zero-packet-loss throughput regions of this model for both the unsynchronized and slot-synchronized cases. Given an arbitrary number of users and a packet alphabet of arbitrary size, it is shown that these two regions coincide, and the outer boundary of this common region is the set of all points with only nonnegative components that add up to one. It is further shown that all points on this outer boundary with only rational components can be achieved without packet loss in the slot-synchronized case. The constructive proofs are based on a joint design of protocol sequences, identification/location algorithm and erasure correcting codes. These findings indicate that the negative impact of the lack of time synchronization on the throughput performance can be removed by the help of SIC. [ABSTRACT FROM AUTHOR]

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called Tubal-AltMin, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-AltMin alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Secondly, the theoretical performance guarantee is challenging since Tubal-AltMin is iterative and nonconvex. We prove that 1) Tubal-AltMin generates a best rank- $r$ approximate up to any predefined accuracy $\epsilon $ at an exponential rate, and 2) for an $n \times n \times k$ tensor $\mathcal {M}$ with tubal-rank $r \ll n$ , the required sampling complexity is $O((nr^{2}k ||\mathcal {M}||_{F}^{2} \log ^{3}~n) / \overline {\sigma }_{rk}^{2})$ , where $\overline {\sigma }_{rk}$ is the $rk$ -th singular value of the block diagonal matrix representation of $\mathcal {M}$ in the frequency domain, and the computational complexity is $O(n^{2}r^{2}k^{3} \log n \log (n/\epsilon))$. Finally, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization using alternating direction method of multipliers (TNN-ADMM), Tubal-AltMin-Simple (a simplified implementation of Tubal-AltMin) improves the recovery error by several orders of magnitude. In experiments, Tubal-AltMin-Simple is faster than TNN-ADMM by a factor of 5 for a $200 \times 200 \times 20$ tensor. [ABSTRACT FROM AUTHOR]

This paper investigates basic trade-offs between energy and delay in wireless communication systems using finite blocklength theory. We first assume that data arrive in constant stream of bits, which are put into packets and transmitted over a communications link. Our results show that depending on exactly how energy is measured, in general energy depends on $\sqrt {d^{-1}}$ or $\sqrt {d^{-1}\log {d}}$ , where $d$ is the delay. This means that the energy decreases quite slowly with increasing delay. Furthermore, to approach the absolute minimum of −1.59 dB on energy, bandwidth has to increase very rapidly, much more than what is predicted by infinite blocklength theory. We then consider the scenario when data arrive stochastically in packets and can be queued. We devise a scheduling algorithm based on finite blocklength theory and develop bounds for the energy-delay performance. Our results again show that the energy decreases quite slowly with increasing delay. [ABSTRACT FROM AUTHOR]

Dueck and Körner’s reliability function for discrete memoryless channels for rates above the capacity coincides with Arimoto’s exponent of correct decoding probability. The two exponent functions are described by seemingly different optimization problems over the space of probability distributions. Arimoto gave an iterative algorithm for solving the optimization problem that appears in his exponent function. However, no algorithm to solve the optimization problem that appears in Dueck and Körner’s exponent has been proposed. This paper proposes a new iterative algorithm for solving the minimization problem in Dueck and Körner’s exponent. In the proposed algorithm, a double minimization form with respect to two joint distributions on input and output symbols is introduced. This double minimization is connected to another double minimization that appears in Arimoto’s algorithm. Such a connection leads to a quadruple minimization problem, by which the match of Arimoto and Dueck-Körner exponents is easily proved. [ABSTRACT FROM AUTHOR]