Search

The state-dependent Gaussian interference channel (IC) and Z-IC are investigated, in which two receivers are corrupted by the same but differently scaled states. The state sequence is noncausally known at both transmitters, but not known at either receiver. Three interference regimes are studied, i.e., the very strong, strong, and weak regimes. In the very strong regime, the capacity region is characterized under certain channel parameters by designing a cooperative dirty paper coding between the two transmitters to fully cancel the state. In the strong regime, points on the capacity region boundary are characterized under certain channel parameters by designing an achievable scheme based on rate splitting, layered dirty paper coding, and successive state cancellation. In the weak regime, the sum capacity is obtained by independent dirty paper coding at two transmitters. For all the above regimes, the capacity achieves that of the IC/Z-IC without state. Comparison between the state-dependent regular IC and the Z-IC suggests that even with one interference-free link, the Z-IC does not necessarily perform better, because dirty paper coded interference in the regular IC facilitates to cancel the state through the cooperative dirty paper coding between the transmitters. [ABSTRACT FROM AUTHOR]

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 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]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [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]

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]

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]

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]

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 this paper, we propose a lattice-based robust distributed source coding system for two correlated sources and provide a detailed performance analysis under the high resolution assumption. It is shown, among other things, that, in the asymptotic regime where: 1) the side distortion approaches 0 and 2) the ratio between the central and side distortions approaches 0, our scheme is capable of achieving the information-theoretic limit of quadratic multiple description coding when the two sources are identical, whereas a variant of the random coding scheme by Chen and Berger with Gaussian codes has a performance loss of 0.5 bits relative to this limit. [ABSTRACT FROM AUTHOR]

This semi-tutorial paper introduces the partial-inverse problem for polynomials and develops its application to decoding Reed–Solomon codes and some related codes. The most natural algorithm to solve the partial-inverse problem is very similar to, but more general than, the Berlekamp–Massey algorithm. Two additional algorithms are obtained as easy variations of the basic algorithm: the first variation is entirely new, while the second variation may be viewed as a version of the Euclidean algorithm. Decoding Reed–Solomon codes (and some related codes) can be reduced to the partial-inverse problem, both via the standard key equation and, more naturally, via an alternative key equation with a new converse. Shortened and singly-extended Reed–Solomon codes are automatically included. Using the properties of the partial-inverse problem, two further key equations with attractive properties are obtained. The paper also points out a variety of options for interpolation. [ABSTRACT FROM PUBLISHER]

This paper studies networks that consist of $N$ half-duplex relays assisting the communication between a source and a destination. In ISIT’12 Brahma et al. conjectured that in Gaussian half-duplex diamond networks (i.e., without a direct link between the source and the destination, and with N$ non-interfering relays), an approximately optimal relay scheduling policy (i.e., achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) has at most N+1$ active states (i.e., at most N+1 possible relay listen-transmit configurations have a strictly positive probability). Such relay scheduling policies were referred to as simple. In ITW’13, we conjectured that simple approximately optimal relay scheduling policies exist for any Gaussian half-duplex multi-relay network irrespectively of the topology. This paper formally proves this more general version of the conjecture and shows it holds beyond Gaussian noise networks. In particular, for any class of memoryless half-duplex $N$ -relay networks with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an approximately optimal simple relay scheduling policy exists. The key step of the proof is to write the minimum of the submodular cut-set function by means of its Lovász extension and use the greedy algorithm for submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min–max problems and the existence of optimal basic feasible solutions for linear programs, proves the conjecture. As an example, for $N$ -relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most $N+1$ active states, irrespectively of the total number of antennas in the system, is proved. [ABSTRACT FROM PUBLISHER]

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast- $Z$ network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs. [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 history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis. [ABSTRACT FROM PUBLISHER]

We consider the problem of recovering a signal $ \mathbf {x^{*}}\in \mathbb {R}^{n}$ , from magnitude-only measurements, $y_{i} = \left |{ \left \langle{ { \mathbf {a}_{i}}, \mathbf {x^{*}} }\right \rangle }\right | $ for $i=\{1,2,\ldots ,m\}$. This is a stylized version of the classical phase retrieval problem, and is a fundamental challenge in nano- and bio-imaging systems, astronomical imaging, and speech processing. It is well-known that the above problem is ill-posed, and therefore some additional assumptions on the signal and/or the measurements are necessary. In this paper, we consider the case where the underlying signal $ \mathbf {x^{*}}$ is $s$ -sparse. For this case, we develop a novel recovery algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple and is obtained via a natural combination of the classical alternating minimization approach for phase retrieval with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that our algorithm achieves a sample complexity of $ \mathcal {O}\left ({{s^{2} \log n}}\right)$ with Gaussian measurements $ { \mathbf {a}_{i}}$ , which matches the best known existing results; moreover, it also demonstrates linear convergence in theory and practice. An appealing feature of our algorithm is that it requires no extra tuning parameters other than the signal sparsity level $s$. Moreover, we show that our algorithm is robust to noise. The quadratic dependence of sample complexity on the sparsity level is sub-optimal, and we demonstrate how to alleviate this via additional assumptions beyond sparsity. First, we study the (practically) relevant case where the sorted coefficients of the underlying sparse signal exhibit a power law decay. In this scenario, we show that the CoPRAM algorithm achieves a sample complexity of $ \mathcal {O}\left ({{s \log n}}\right)$ , which is close to the information-theoretic limit. We then consider the case where the underlying signal $ \mathbf {x^{*}}$ arises from structured sparsity models. We specifically examine the case of block-sparse signals with uniform block size of $b$ and block sparsity $k=s/b$. For this problem, we design a recovery algorithm that we call Block CoPRAM that further reduces the sample complexity to $ \mathcal {O}\left ({{ks \log n}}\right)$. For sufficiently large block lengths of $b=\Theta (s)$ , this bound equates to $ \mathcal {O}\left ({{s \log n}}\right)$. To our knowledge, our approach constitutes the first family of linearly convergent algorithms for signal recovery from magnitude-only Gaussian measurements that exhibit a sub-quadratic dependence on the signal sparsity level. [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]

Sparse linear inverse problems appear in a variety of settings, but often the noise contaminating observations cannot accurately be described as bounded by or arising from a Gaussian distribution. Poisson observations in particular are a characteristic feature of several real-world applications. Previous work on sparse Poisson inverse problems encountered several limiting technical hurdles. This paper describes a novel alternative analysis approach for sparse Poisson inverse problems that 1) sidesteps the technical challenges present in previous work, 2) admits estimators that can readily be computed using off-the-shelf LASSO algorithms, and 3) hints at a general framework for broad classes of noise in sparse linear inverse problems. At the heart of this new approach lies a weighted LASSO estimator for which data-dependent weights are based on Poisson concentration inequalities. Unlike previous analyses of the weighted LASSO, the proposed analysis depends on conditions which can be checked or shown to hold in general settings with high probability. 2000 Math Subject Classification: 60E15, 62G05, 62G08, and 94A12. [ABSTRACT FROM AUTHOR]

In this paper, we consider the mixture of sparse linear regressions model. Let $\boldsymbol {\beta }^{(1)},\ldots, \boldsymbol {\beta }^{(L)}\in \mathbb {C} ^{n}$ be $L $ unknown sparse parameter vectors with a total of $K $ non-zero elements. Noisy linear measurements are obtained in the form $y_{i} = \boldsymbol {x}_{i} ^{\mathrm{ H}} \boldsymbol {\beta }^{(\ell _{i})} + w_{i}$ , each of which is generated randomly from one of the sparse vectors with the label $\ell _{i} $ unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels $\ell _{i} $ as well as the estimation problem of recovering the sparse vectors $\boldsymbol {\beta }^{(\ell)} $. Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, Mixed-Coloring, which samples the mixture strategically using query vectors $\boldsymbol {x}_{i} $ constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. To find $K$ non-zero elements, it is clear that we need at least $\Theta (K)$ measurements, and thus the time complexity is at least $\Theta (K)$. In the noiseless setting, for a constant number of sparse parameter vectors, our algorithm achieves the order-optimal sample and time complexities of $\Theta (K)$. In the presence of Gaussian noise, for the problem with two parameter vectors (i.e., $L = 2$), we show that the Robust Mixed-Coloring algorithm achieves near-optimal $\Theta (K \mathop {\mathrm {polylog}}\nolimits (n))$ sample and time complexities. When $K = \mathcal {O}(n^{\alpha })$ for some constant $\alpha \in (0,1)$ (i.e., $K$ is sublinear in $n$), we can achieve sample and time complexities both sublinear in the ambient dimension. In one of our experiments, to recover a mixture of two regressions with dimension $n = 500$ and sparsity $K = 50$ , our algorithm is more than 300 times faster than EM algorithm, with about one third of its sample cost. 1 The proposed algorithm works even when the noise is non-Gaussian in nature, but the guarantees on sample and time complexities are difficult to obtain. [ABSTRACT FROM AUTHOR]

Local rank modulation (LRM) scheme was suggested for representing the information in flash memories in order to overcome the drawbacks of rank modulation. For $0 < s\leq t\leq n$ with $s$ dividing $n$ , an $(s,t,n)$ -LRM scheme is a LRM scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations, which requires less comparisons and less distinct values. The gap between two such windows equals to $s$. In this paper, encoding, decoding, and asymptotic enumeration of the $(1,t,n)$ -LRM scheme are studied. [ABSTRACT FROM AUTHOR]

This paper deals with lower bounds on aperiodic correlation of sequences. It intends to solve two open questions. The first one is on the validity of the Levenshtein bound for a set of sequences other than binary sequences or those over the roots of unity. Although this result could be a priori extended to polyphase sequences, a formal demonstration is presented here, proving that it does actually hold for these sequences. The second open question is on the possibility to find a bound tighter than Welch’s, in the case of a set consisting of two sequences $M = 2$. By including the specific structure of correlation sequences, a tighter lower bound is introduced for this case. Besides, this method also provides in the cases $M = 3$ and $M = 4$ a tighter bound than the up-to-now tightest bound provided by Liu et al. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing codes that can correct $\delta $ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(\delta =1)$ correcting codes and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $\delta $ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $\delta $ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization. [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]

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]

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]

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]

In an acyclic multicast network, it is well known that a linear network coding solution over GF( q ) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF( q ) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every \omega \geq 3 , there is a multicast network with source outdegree \omega linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF( q ) and over GF( q^m2 ) is not necessarily linearly solvable over GF( q^{m1 + m2} ); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size q_{\mathrm{ min}} for a linear solution over GF( q_{\mathrm{ min}} ) is lower bounded by \Theta (\sqrt T) , but not every larger field than GF( q\mathrm{ min} ) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network. [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]

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]

We study the following combinatorial version of the Slepian–Wolf coding scheme. Two isolated Senders are given binary strings $X$ and $Y$ , respectively; the length of each string is equal to $n$ , and the Hamming distance between the strings is at most $\alpha n$. The Senders compress their strings and communicate the results to the Receiver. Then, the Receiver must reconstruct both the strings $X$ and $Y$. The aim is to minimize the lengths of the transmitted messages. For an asymmetric variant of this problem (where one of the Senders transmits the input string to the Receiver without compression) with deterministic encoding, a nontrivial bound was found by Orlitsky and Viswanathany. In this paper, we prove a new lower bound for the schemes with syndrome coding, where at least one of the Senders uses linear encoding of the input string. For the combinatorial Slepian–Wolf problem with randomized encoding, the theoretical optimum of communication complexity was known earlier, even though effective protocols with optimal lengths of messages remained unknown. We close this gap and present a polynomial-time-randomized protocol that achieves the optimal communication complexity. [ABSTRACT FROM AUTHOR]

We present a framework for random access that is based on three elements: physical-layer network coding (PLNC), signature codes, and tree splitting. In presence of a collision, physical-layer network coding enables the receiver to decode, i.e., compute, the sum of the packets that were transmitted by the individual users. For each user, the packet consists of the user’s signature, as well as the data that the user wants to communicate. As long as no more than $K$ users collide, their identities can be recovered from the sum of their signatures. This framework for creating and transmitting packets can be used as a fundamental building block in random access algorithms, since it helps to deal efficiently with the uncertainty of the set of contending terminals. In this paper, we show how to apply the framework in conjunction with a tree-splitting algorithm, which is required to deal with the case that more than $K$ users collide. We demonstrate that our approach achieves throughput that tends to 1 rapidly as $K$ increases. We also present results on net data-rate of the system, showing the impact of the overheads of the constituent elements of the proposed protocol. We compare the performance of our scheme with an upper bound that is obtained under the assumption that the active users are a priori known. Also, we consider an upper bound on the net data-rate for any PLNC-based strategy in which one linear equation per slot is decoded. We show that already at modest packet lengths, the net data-rate of our scheme becomes close to the second upper bound, i.e., the overhead of the contention resolution algorithm and the signature codes vanishes. [ABSTRACT FROM AUTHOR]

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n -length signal, and has a computational complexity of O( n\log n) . If the DFT \vec X of the signal \vec x has only $k$ non-zero coefficients (where k< n$ ), can we do better? We addressed this question and presented a novel fast Fourier aliasing-based sparse transform (FFAST) algorithm that cleverly induces sparse-graph alias codes in the DFT domain, via a Chinese-remainder-theorem-guided sub-sampling operation in the time-domain. The induced sparse-graph alias codes are then exploited to devise a fast and iterative onion-peeling style decoder that computes k$ -sparse DFT of an n$ -length signal using only O( k)$ time-domain samples and O( k\log k)$ computations. In this paper, we generalize the FFAST framework by Pawar and Ramchandran to the noisy setting where the time-domain samples are corrupted by white Gaussian noise. We show that the noise-robust R-FFAST algorithm computes a k noise-corrupted time-domain samples in O( k\log ^{4} n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈ 10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients. [ABSTRACT FROM PUBLISHER]

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]

The location awareness is useful in many wireless networking solutions, such as cellular, ad hoc, self-organizing, cognitive radio networks, and so on. The RSS-based, non-Bayesian source localization is of particular interest, due to the presence of the RSS measurements in all radio devices, as well as the instantaneous estimations without extensive training and learning phases. However, most RSS-based localization algorithms usually neglect problems arising from inherent network topology uncertainty. The positions of some measuring anchors, usually assumed to be precisely known in advance, are often a subject of previous estimation, which propagates errors in the source localization procedure and results in performance degradation. A joint localization framework, termed source position estimation for anchor position uncertainty reduction (SPEAR), has been recently proposed as a possible solution to the problem of RSS-based localization in the presence of network topology uncertainty. The framework simultaneously estimates the positions of the sources and the uncertain anchors and serves as robust tool that provides improved source localization performance and more reliable anchor position estimates. This paper focuses on the theoretical assessment of SPEAR’s performance by deriving its fundamental lower bounds using the Cramér–Rao information inequality. The main contribution of this paper is the detailed information-theoretic interpretation of the obtained results. The interpretation provides valuable insight into the essence of the SPEAR localization problem because it identifies different position information components in the observed data, discovers how they are mutually related, and determines how they contribute toward the resulting position information. This paper also provides geometric interpretation of the obtained results and illustrates the principles of distribution of position information in space. The theoretical results as well as their information-theoretic and geometric interpretations can be used as a benchmark for RSS-based location-aware systems that operate in the presence of network topology uncertainty. [ABSTRACT FROM AUTHOR]

In this paper, we design novel distributed scheduling algorithms for multiuser multiple-input multiple-output systems and evaluate the resulting system capacity analytically. In particular, we consider algorithms which do not require sending channel state information to a central processing unit, nor do they require communication between the users themselves, yet, the resulting capacity closely approximates that of a centrally controlled system, which is able to schedule the strongest user in each time-slot. In other words, multiuser diversity is achieved in a distributed fashion. Our analysis is based on a novel application of the point-process approximation. This technique, besides tackling previously suggested models successfully, allows an analytical examination of new models, such as nonhomogeneous cases (nonidentically distributed users) or various quality of service considerations. This results in asymptotically exact expressions for the capacity of the system under these schemes, solving analytically problems which to date had been open. Possible applications include, but are not limited to, modern 4G networks, such as 3GPP LTE, or random access protocols. [ABSTRACT FROM PUBLISHER]

This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case, when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for nonplanar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between maximum distance separable codes. This paper illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations. [ABSTRACT FROM PUBLISHER]

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]

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]

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]

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]

In this paper, an application of the theoretical algebraic notion of a separable ring extension in the realm of cyclic convolutional codes or, more generally, ideal codes, is investigated. It is worked under very mild conditions that cover all previously known as well as new non-trivial examples. It is proved that ideal codes are direct summands, as left ideals, of the underlying non-commutative algebra, in analogy with cyclic block codes. This implies, in particular, that they are generated by a non-commutative idempotent polynomial. Hence, by using a suitable separability element, an efficient algorithm for computing one of such idempotents is designed. We show that such an idempotent generator polynomial can be used to get information on the free distance of the convolutional code. [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]

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. One of the defining features of the group testing problem is the distinction between the non-adaptive and adaptive settings. In the non-adaptive case, all tests must be designed in advance, whereas in the adaptive case, each test can be designed based on the previous outcomes. While tight information-theoretic limits and near-optimal practical algorithms are known for the adaptive setting in the absence of noise, surprisingly little is known in the noisy adaptive setting. In this paper, we address this gap by providing information-theoretic achievability and converse bounds under various noise models, as well as a slightly weaker achievability bound for a computationally efficient variant. These bounds are shown to be tight or near-tight in a broad range of scaling regimes, particularly at low noise levels. The algorithms used for the achievability results have the notable feature of only using two or three stages of adaptivity. [ABSTRACT FROM AUTHOR]