Information Theory (cs.IT)

• This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent --- when randomly initialized --- yields an $\epsilon$-accurate solution in $O\big(\log n+\log(1/\epsilon)\big)$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.
• We interpret part of the experimental results of Shwartz-Ziv and Tishby [2017]. Inspired by these results, we established a conjecture of the dynamics of the machinary of deep neural network. This conjecture can be used to explain the counterpart result by Saxe et al. [2018].
• Mar 22 2018 cs.IT math.IT arXiv:1803.07937v1
The existence of a unique Augustin mean is established for any positive order and probability mass function on the input set. The Augustin mean is shown to be the unique fixed point of an operator defined in terms of the order and the input distribution. The Augustin information is shown to be continuously differentiable in the order. For any channel and any convex constraint set with finite Augustin capacity, the existence of a unique Augustin center and associated van Erven-Harremoes bound are established.The Augustin-Legendre (A-L) information, capacity, center, and radius are introduced and the latter three is proved to be equal to the corresponding Renyi-Gallager quantities. The equality of the A-L capacity to the A-L radius for arbitrary channels and the existence of a unique A-L center for channels with finite A-L capacity are established. For all interior points of the feasible set of cost constraints, the cost constrained Augustin capacity and center are expressed in terms the A-L capacity and center. Certain shift invariant families of probability measures and certain Gaussian channels are analyzed as examples.
• In this paper, we describe a new Niederreiter cryptosystem based on quasi-cyclic $\frac{m-1}{m}$ codes that is quantum-secure. This new cryptosystem has good transmission rate compared to the one using binary Goppa codes and uses smaller keys.
• A source submits status updates to a network for delivery to a destination monitor. Updates follow a route through a series of network nodes. Each node is a last-come-first-served queue supporting preemption in service. We characterize the average age of information at the input and output of each node in the route induced by the updates passing through. For Poisson arrivals to a line network of preemptive memoryless servers, we show that average age accumulates through successive network nodes.
• Mobile relaying is emerged as a promising technique to assist wireless communication, driven by the rapid development of unmanned aerial vehicles (UAVs). In this paper, we study secure transmission in a four-node (source, destination, mobile relay, and eavesdropper) system, wherein we focus on maximizing the secrecy rate via jointly optimizing the relay trajectory and the source/relay transmit power. Nevertheless, due to the coupling of the trajectory designing and the power allocating, the secrecy rate maximization (SRM) problem is intractable to solve. Accordingly, we propose an alternating optimization (AO) approach, wherein the trajectory designing and the power allocating are tackled in an alternating manner. Unfortunately, the trajectory designing is a nonconvex problem, and thus is still hard to solve. To circumvent the nonconvexity, we exploit sequential convex programming (SCP) to derive an iterative algorithm, which is proven to converge to a Karush-Kuhn-Tucker (KKT) point of the trajectory design problem. The simulation results demonstrate the efficacy of the joint power and trajectory design in improving the secrecy throughput.
• A network model is considered where Poisson distributed base stations transmit to $N$ power-domain non-orthogonal multiple access (NOMA) users (UEs) each that employ successive interference cancellation (SIC) for decoding. We propose three models for the clustering of NOMA UEs and consider two different ordering techniques for the NOMA UEs: mean signal power-based and instantaneous signal-to-intercell-interference-and-noise-ratio-based. For each technique, we present a signal-to-interference-and-noise ratio analysis for the coverage of the typical UE. We plot the rate region for the two-user case and show that neither ordering technique is consistently superior to the other. We propose two efficient algorithms for finding a feasible resource allocation that maximize the cell sum rate $\mathcal{R}_{\rm tot}$, for general $N$, constrained to: 1) a minimum rate $\mathcal{T}$ for each UE, 2) identical rates for all UEs. We show the existence of: 1) an optimum $N$ that maximizes the constrained $\mathcal{R}_{\rm tot}$ given a set of network parameters, 2) a critical SIC level necessary for NOMA to outperform orthogonal multiple access. The results highlight the importance in choosing the network parameters $N$, the constraints, and the ordering technique to balance the $\mathcal{R}_{\rm tot}$ and fairness requirements. We also show that interference-aware UE clustering can significantly improve performance.
• An angular distribution of received signals has a significant impact on their spectral and correlational properties. Most of angular dispersion models do not consider antenna patterns. The developed procedure for determining the propagation path parameters enables a wide range of assessment of the impact of the propagation environment on the received signal properties. In contrast to the other models, this procedure is based on a geometrical structure, which parameters are defined on the basis of power delay profile or spectrum This modeling method allows also the power radiation pattern (PRP) of the transmitting antenna. The aim of the paper is to present the influence of the transmitter antenna PRP on the scattering propagation paths that arrive at the receiver. This analysis is realized on the basis of simulations studies using the developed procedure. Presented in this paper procedure maps the effects of propagation phenomena that predominate in an azimuth plane.
• Considering Rayleigh fading channels, in this work we adopt channel inversion power control to achieve covert communications, where a transmitter can possibly hide itself from a warden while transmitting information to a receiver. Specifically, we examine the performance of the achieved covert communications in two scenarios in terms of the effective covert rate (ECR), which quantifies the amount of information that the transmitter can reliably convey to the receiver subject to the warden's detection error probability being no less than some specific value. In the first scenario, the noise uncertainty at the warden serves as the enabler of covert communications and our examination shows that increasing the noise uncertainty at the warden and the receiver simultaneously may not continuously improve the ECR. In the second scenario, covert communications are aided by a full-duplex receiver, which always transmits artificial noise (AN) with a random power. Our analysis indicates that the achieved ECR approaches to an upper bound as the transmit power of AN approaches to infinity. This work provides useful guidelines and performance limits on achieving covert communications and potentially hiding a transmitter in practical Rayleigh fading channels.
• In this paper, we propose a cross layer energy efficient resource allocation and remote radio head (RRH) selection algorithm for heterogeneous traffic in power domain - non-orthogonal multiple access (PD-NOMA) based heterogeneous cloud radio access networks (H-CRANs). The main aim is to maximize the EE of the elastic users subject to the average delay constraint of the streaming users and the constraints, RRH selection, subcarrier, transmit power and successive interference cancellation. The considered optimization problem is non-convex, NP-hard and intractable. To solve this problem, we transform the fractional objective function into a subtractive form. Then, we utilize successive convex approximation approach. Moreover, in order to increase the processing speed, we introduce a framework for accelerating the successive convex approximation for low complexity with the Lagrangian method on graphics processing unit. Furthermore, in order to show the optimality gap of the proposed successive convex approximation approach, we solve the proposed optimization problem by applying an optimal method based on the monotonic optimization. Studying different scenarios show that by using both PD-NOMA technique and H-CRAN, the system energy efficiency is improved.
• Measurement results for millimeter wave LOS MIMO systems are presented with a focus on time variation and multipath propagation. Different system setups are used, including 2x2 and 3x3 MIMO, and involving different synchronization procedures and front-ends. Furthermore, different propagation scenarios are evaluated, covering a wide area of applications. The results show that the LOS component carries significantly more power than the NLOS components, and that frequency selectivity from front-ends should be taken into account when designing these high bandwidth systems. Frequency offsets and other phase variations due to transmit and receive oscillator differences are treated as part of the channel and thus, depending on the synchronization setup, the MIMO system exhibits different time variations, particularly in the case of independent local oscillators. It is also observed that these systems experience significant non-trivial long-term variations in terms of amplitude and phase.
• The Gaussian width is a fundamental quantity in probability, statistics and geometry, known to underlie the intrinsic difficulty of estimation and hypothesis testing. In this work, we show how the Gaussian width, when localized to any given point of an ellipse, can be controlled by the Kolmogorov width of a set similarly localized. This connection leads to an explicit characterization of the estimation error of least-squares regression as a function of the true regression vector within the ellipse. The rate of error decay varies substantially as a function of location: as a concrete example, in Sobolev ellipses of smoothness $\alpha$, we exhibit rates that vary from $(\sigma^2)^{\frac{2 \alpha}{2 \alpha + 1}}$, corresponding to the classical global rate, to the faster rate $(\sigma^2)^{\frac{4 \alpha}{4 \alpha + 1}}$. We also show how the local Kolmogorov width can be related to local metric entropy.
• In this paper we determine the delivery time for a multi-server coded caching problem when the cache size of each user is small. We propose an achievable scheme based on coded cache content placement, and employ zero-forcing techniques at the content delivery phase. Surprisingly, in contrast to previous multi-server results which were proved to be order-optimal within a multiplicative factor of 2, for the low memory regime we prove that our achievable scheme is optimal. Moreover, we compare the performance of our scheme with the uncoded solution, and show our proposal improvement over the uncoded scheme. Our results also apply to Degrees-of-Freedom (DoF) analysis of Multiple-Input Single-Output Broadcast Channels (MISO-BC) with cache-enabled users, where the multiple-antenna transmitter replaces the role of multiple servers. This shows that interference management in the low memory regime needs different caching techniques compared with medium-high memory regimes discussed in previous works.
• The decoupling of data and control planes, as proposed for 5G networks, will enable the efficient implementation of multitier networks where user equipment (UE) nodes obtain coverage and connectivity through the top-tier macro-cells, and, at the same time, achieve high-throughput low-latency communication through lower tiers in the hierarchy. This paper considers a new architecture for such lower tiers, dubbed fog massive MIMO, where the UEs are able to establish high-throughput low-latency data links in a seamless and opportunistic manner, as they travel through a dense fog of high-capacity wireless infrastructure nodes, referred to as remote radio heads (RRHs). Traditional handover mechanisms in dense multicell networks inherently give rise to frequent handovers and pilot sequence re-assignments, incurring, as a result, excessive protocol overhead and significant latency. In the proposed fog massive MIMO architecture, UEs seamlessly and implicitly associate themselves to the most convenient RRHs in a completely autonomous manner. Each UE makes use of a unique uplink pilot sequence, and pilot contamination is mitigated by a novel coded "on-the-fly" pilot contamination control mechanism. We analyze the spectral efficiency and the outage probability of the proposed architecture via stochastic geometry, using some recent results on unique coverage in Boolean models, and provide a detailed comparison with respect to an idealized baseline massive MIMO cellular system, that neglects protocol overhead and latency due to explicit user-cell association. Our analysis, supported by extensive system simulation, reveals that there exists a "sweet spot" of the per-pilot user load (number of users per pilot), such that the proposed system achieves spectral efficiency close to that of an ideal cellular system with the minimum distance user-base station association and no pilot/handover overhead.
• Quantum maximum-distance-separable (MDS) codes are an important class of quantum codes. In this paper, using constacyclic codes and Hermitain construction, we construct some new quantum MDS codes of the form $q=2am+t$, $n=\frac{q^{2}+1}{a}$. Most of these quantum MDS codes are new in the sense that their parameters are not covered be the codes available in the literature.

gae Jul 26 2017 21:19 UTC

For those interested in the literature on teleportation simulation of quantum channels, a detailed and *comprehensive* review is provided in Supplementary Note 8 of https://images.nature.com/original/nature-assets/ncomms/2017/170426/ncomms15043/extref/ncomms15043-s1.pdf
The note describes well the t

...(continued)
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)
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.

Patrick Hayden May 28 2015 17:31 UTC

Wonderful! I've been waiting for a book like this for a while now! Thanks, Marco.

I do have one trivial comment from a 30 second preliminary scan, though: please consider typesetting the proofs with a font size matching the main text. If us readers are already squinting hard trying to understand

...(continued)
Marco Tomamichel Apr 02 2015 03:21 UTC

This is a preliminary version and I am happy to incorporate feedback I receive in the coming month. Any comments are welcome.