Information Theory (math.IT)

  • PDF
    We study the relations between the recently proposed machine-independent quantum complexity of P. Gacs~\citeGacs and the entropy of classical and quantum systems. On one hand, by restricting Gacs complexity to ergodic classical dynamical systems, we retrieve the equality between the Kolmogorov complexity rate and the Shannon entropy rate derived by A.A. Brudno~\citeBrudno. On the other hand, using the quantum Shannon-Mc Millan theorem~\citeBSM, we show that such an equality holds densely in the case of ergodic quantum spin chains.
  • PDF
    For decades, optimization has played a central role in addressing wireless resource management problems such as power control and beamformer design. However, these algorithms often require a considerable number of iterations for convergence, which poses challenges for real-time processing. In this work, we propose a new learning-based approach for wireless resource management. The key idea is to treat the input and output of a resource allocation algorithm as an unknown non-linear mapping and to use a deep neural network (DNN) to approximate it. If the non-linear mapping can be learned accurately and effectively by a DNN of moderate size, then such DNN can be used for resource allocation in almost \emphreal time, since passing the input through a DNN to get the output only requires a small number of simple operations. In this work, we first characterize a class of `learnable algorithms' and then design DNNs to approximate some algorithms of interest in wireless communications. We use extensive numerical simulations to demonstrate the superior ability of DNNs for approximating two considerably complex algorithms that are designed for power allocation in wireless transmit signal design, while giving orders of magnitude speedup in computational time.
  • PDF
    Given a database and a target attribute of interest, how can we tell whether there exists a functional, or approximately functional dependence of the target on any set of other attributes in the data? How can we reliably, without bias to sample size or dimensionality, measure the strength of such a dependence? And, how can we efficiently discover the optimal or $\alpha$-approximate top-$k$ dependencies? These are exactly the questions we answer in this paper. As we want to be agnostic on the form of the dependence, we adopt an information-theoretic approach, and construct a reliable, bias correcting score that can be efficiently computed. Moreover, we give an effective optimistic estimator of this score, by which for the first time we can mine the approximate functional dependencies from data with guarantees of optimality. Empirical evaluation shows that the derived score achieves a good bias for variance trade-off, can be used within an efficient discovery algorithm, and indeed discovers meaningful dependencies. Most important, it remains reliable in the face of data sparsity.
  • PDF
    Binary sequences with optimal autocorrelation play important roles in radar, communication, and cryptography. Finding new binary sequences with optimal autocorrelation has been an interesting research topic in sequence design. Ding-Helleseth-Lam sequences are such a class of binary sequences of period $p$, where $p$ is an odd prime with $p\equiv 1(\bmod~4)$. The objective of this letter is to present a construction of binary sequences of period $4p$ via interleaving four suitable Ding-Helleseth-Lam sequences. This construction generates new binary sequences with optimal autocorrelation which can not be produced by earlier ones.
  • PDF
    Provisioning of high throughput millimetre-wave signal to indoor areas that potentially serve large number of users, such as transportation hubs or convention centres, will require dedicated indoor millimetre-wave access point deployments. In this article we study dense deployments of millimetre-wave access points mounted on the ceiling, and illuminating selected spots on the ground with the use of fixed directional antennas. In this setup, the main factor limiting signal propagation are blockages by human bodies. We evaluate our system under a number of scenarios that take into account beamwidth of the main-lobe, access point density, and positioning of a mobile device with respect to the user's body. We find that both coverage and area spectral efficiency curves exhibit non-trivial behaviour which can be classified into four regions related to the selection of access point density, beamwidth, and height values. Furthermore, we observe a trade-off in beamwidth design, as the optimal beamwidth maximizes either coverage or area spectral efficiency but not both. Finally, when we consider different body shadowing scenarios, our network design will optimize coverage and area spectral efficiency performance towards either devices held in hand or worn directly against the body, as each of the scenarios requires mutually exclusive settings of access point density and beamwidth.
  • PDF
    The problem of recovering a signal from its phaseless Fourier transform measurements, called Fourier phase retrieval, arises in many applications in engineering and science. Fourier phase retrieval poses fundamental theoretical and algorithmic challenges. In general, there is no unique mapping between a one-dimensional signal and its Fourier magnitude and therefore the problem is ill-posed. Additionally, while almost all multidimensional signals are uniquely mapped to their Fourier magnitude, the performance of existing algorithms is generally not well-understood. In this chapter we survey methods to guarantee uniqueness in Fourier phase retrieval. We then present different algorithmic approaches to retrieve the signal in practice. We conclude by outlining some of the main open questions in this field.
  • PDF
    A new method for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel is presented. The proposed method termed belief-propagation--list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of regular and irregular quasi-cyclic LDPC codes of short and moderate lengths are studied by simulations and their performance is compared with the upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison with the BP decoding performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary LDPC code over the extension of the binary Galois field. The obtained simulation results are compared to the upper bound on the ensemble-average performance of the binary image of regular nonbinary LDPC codes.
  • PDF
    In this paper, we investigate the performance of the Viterbi decoding algorithm with/without automatic repeat request (ARQ) over a Rician flat fading channel with unlimited interleaving. We show that the decay rate of the average bit error probability with respect to the bit energy to noise ratio is of order between $d_f$ and $d_f+1$ at high bit energy to noise ratio for both cases (with ARQ and without ARQ), where $d_f$ is the free distance of the convolutional code. The Yamamoto-Itoh flag helps to reduce the average bit error probability by a factor of $4^{d_f}$ with a negligible retransmission rate. Besides, the error exponent with respect to the Rician factor is shown to be $d_f$ for any fixed bit energy per noise ratio.
  • PDF
    Ultra-reliable Point-to-Multipoint (PtM) communications are expected to become pivotal in networks offering future dependable services for smart cities. In this regard, sparse Random Linear Network Coding (RLNC) techniques have been widely employed to provide an efficient way to improve the reliability of broadcast and multicast data streams. This paper addresses the pressing concern of providing a tight approximation to the probability of a user recovering a data stream protected by this kind of coding technique. In particular, by exploiting the Stein-Chen method, we provide a novel and general performance framework applicable to any combination of system and service parameters, such as finite field sizes, lengths of the data stream and level of sparsity. The deviation of the proposed approximation from Monte Carlo simulations is negligible, improving significantly on the state of the art performance bound.
  • PDF
    Multi-soliton pulses are potential candidates for fiber optical transmission where the information is modulated and recovered in the so-called nonlinear Fourier domain. While this is an elegant technique to account for the channel nonlinearity, the obtained spectral efficiency, so far, is not competitive with the classic Nyquist-based schemes. In this paper, we study the evolution of the time-bandwidth product of multi-solitons as they propagate along the optical fiber. For second and third order soliton pulses, we numerically optimize the pulse shapes to achieve the smallest time-bandwidth product when the phase of the spectral amplitudes is used for modulation. Moreover, we analytically estimate the pulse-duration and bandwidth of multi-solitons in some practically important cases. Those estimations enable us to approximate the time-bandwidth product for higher order solitons.
  • PDF
    Discrete multiple signal classification (MUSIC) with its low computational cost and mild condition requirement becomes a significant noniterative algorithm for joint sparse recovery (JSR). However, it fails in rank defective problem caused by coherent or limited amount of multiple measurement vectors (MMVs). In this letter, we provide a novel sight to address this problem by interpreting JSR as a binary classification problem with respect to atoms. Meanwhile, MUSIC essentially constructs a supervised classifier based on the labeled MMVs so that its performance will heavily depend on the quality and quantity of these training samples. From this viewpoint, we develop a semisupervised MUSIC (SS-MUSIC) in the spirit of machine learning, which declares that the insufficient supervised information in the training samples can be compensated from those unlabeled atoms. Instead of constructing a classifier in a fully supervised manner, we iteratively refine a semisupervised classifier by exploiting the labeled MMVs and some reliable unlabeled atoms simultaneously. Through this way, the required conditions and iterations can be greatly relaxed and reduced. Numerical experimental results demonstrate that SS-MUSIC can achieve much better recovery performances than other MUSIC extended algorithms as well as some typical greedy algorithms for JSR in terms of iterations and recovery probability.
  • PDF
    In this paper, new equivalence relationships between a network code with link errors (NCLE) and an index code with side information errors (ICSIE) are studied. First, for a given network coding instance, the equivalent index coding instance is derived, where an NCLE is converted to the corresponding ICSIE and vice versa. Next, for a given index coding instance, the equivalent network coding instance is also derived, where an ICSIE is converted to the corresponding NCLE and vice versa if a pair of encoding functions of an original link and the duplicated link are functionally related in the network code. Finally, several properties of an NCLE are derived from those of the equivalent ICSIE using the fact that the NCLE and the ICSIE are equivalent.
  • PDF
    Fast and accurate analog beam tracking is an important and yet challenging issue in 5G wireless networks, due to the inherent non-convexity of the problem. In this paper, we develop a low-complexity recursive beam tracking algorithm. In static beam tracking scenarios, this algorithm converges to the Cramér-Rao lower bound (CRLB) with very high probability. In dynamic beam tracking scenarios, if combined with a simple TDMA pilot pattern, this algorithm has the potential to track hundreds of independent beams, generated by highly-mobile transmitters/reflectors, with low pilot overhead. Simulations are provided to illustrate the performance gain of this algorithm.
  • PDF
    The availability of very wide spectrum in millimeter wave bands combined with large antenna arrays and ultra dense networks raises two basic questions: What is the true value of overly abundant degrees of freedom and how can networks be designed to fully exploit them? This paper determines the capacity scaling of large cellular networks as a function of bandwidth, area, number of antennas and base station density. It is found that the network capacity has a fundamental bandwidth scaling limit, beyond which the network becomes power-limited. An infrastructure multi-hop protocol achieves the optimal network capacity scaling for all network parameters. In contrast, current protocols that use only single-hop direct transmissions can not achieve the capacity scaling in wideband regimes except in the special case when the density of base stations is taken to impractical extremes. This finding suggests that multi-hop communication will be important to fully realize the potential of next-generation cellular networks. Dedicated relays, if sufficiently dense, can also perform this task, relieving user nodes from the battery drain of cooperation. On the other hand, more sophisticated strategies such as hierarchical cooperation, that are essential for achieving capacity scaling in ad hoc networks, are unnecessary in the cellular context.
  • PDF
    We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.
  • PDF
    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 are zero-error single deletion $(\delta=1)$ correcting codes, and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions is an open problem. We propose a new family of codes, that we call Guess & Check (GC) codes, that can correct, with high probability, up to $\delta$ deletions occurring in a binary string. Moreover, we show that GC codes can also correct up to $\delta$ insertions. GC codes are based on MDS codes and have an asymptotically optimal redundancy that is $\Theta(\delta \log n)$. We provide deterministic polynomial time encoding and decoding schemes for these codes. We also describe the applications of GC codes to file synchronization.

Recent comments

Stefano Pirandola May 05 2017 05:45 UTC

Today I have seen on the arXiv the version 2 of this paper on quantum reading. I am sorry to say that this revision still misses to acknowledge important contributions from previous works, especially in relation to the methods on channel simulation and teleportation that are crucial for its claims.

...(continued)
gae spedalieri Mar 13 2017 14:13 UTC

1) Sorry but this is false.

1a) That analysis is specifically for reducing QECC protocol to an entanglement distillation protocol over certain class of discrete variable channels. Exactly as in BDSW96. Task of the protocol is changed in the reduction.

1b) The simulation is not via a general LOCC b

...(continued)
Siddhartha Das Mar 13 2017 13:22 UTC

We feel that we have cited and credited previous works appropriately in our paper. To clarify:

1) The LOCC simulation of a channel and the corresponding adaptive reduction can be found worked out in full generality in the 2012 Master's thesis of Muller-Hermes. We have cited the original paper BD

...(continued)
gae spedalieri Mar 13 2017 08:56 UTC

This is one of those papers where the contribution of previous literature is omitted and not fairly represented.

1- the LOCC simulation of quantum channels (not necessarily teleportation based) and the corresponding general reduction of adaptive protocols was developed in PLOB15 (https://arxiv.org/

...(continued)
Samad Khabbazi Oskouei Sep 05 2016 11:34 UTC

I think that we have missed the "semi-" at the conclusion. Because, the proof of the theorem 4.3 is based on the using universal semi-density matrix concept which is not computable. The semi-computability concept used here is like the Kolmogorov complexity which is not computable and so the Cubic co

...(continued)
Toby Cubitt Sep 01 2016 11:14 UTC

I could well be missing something. But as far as I could tell from a rather quick read through the paper, all they show is that the quantum capacity of a channel with computable matrix elements is given by the regularised coherent information optimised over input ensembles with computable matrix ele

...(continued)
Māris Ozols Aug 30 2016 17:52 UTC

Do I understand correctly that this paper claims to show that quantum capacity is computable?

> After defining the algorithmic quantum capacity we have proved that it
> equals the standard one. Furthermore we have shown that it is
> computable.

Richard Kueng Jul 28 2015 07:01 UTC

fyi: our quantum implications are presented in Subsection 2.2 (pp 7-9).

Marco Tomamichel May 31 2015 22:07 UTC

Thanks for the comment! This is a good idea, I will do that in the next arXiv version.