Information Theory (math.IT)

  • PDF
    Photoacoustic imaging (PAI) is an emerging biomedical imaging modality capable of providing both high contrast and high resolution of optical and UltraSound (US) imaging. When a short duration laser pulse illuminates the tissue as a target of imaging, tissue induces US waves and detected waves can be used to reconstruct optical absorption distribution. Since receiving part of PA consists of US waves, a large number of beamforming algorithms in US imaging can be applied on PA imaging. Delay-and-Sum (DAS) is the most common beamforming algorithm in US imaging. However, make use of DAS beamformer leads to low resolution images and large scale of off-axis signals contribution. To address these problems a new paradigm namely Delay-Multiply-and-Sum (DMAS), which was used as a reconstruction algorithm in confocal microwave imaging for breast cancer detection, was introduced for US imaging. Consequently, DMAS was used in PA imaging systems and it was shown this algorithm results in resolution enhancement and sidelobe degrading. However, in presence of high level of noise the reconstructed image still suffers from high contribution of noise. In this paper, a modified version of DMAS beamforming algorithm is proposed based on DAS inside DMAS formula expansion. The quantitative and qualitative results show that proposed method results in more noise reduction and resolution enhancement in expense of contrast degrading. For the simulation, two-point target, along with lateral variation in two depths of imaging are employed and it is evaluated under high level of noise in imaging medium. Proposed algorithm in compare to DMAS, results in reduction of lateral valley for about 19 dB followed by more distinguished two-point target. Moreover, levels of sidelobe are reduced for about 25 dB.
  • PDF
    We consider the problem of private information retrieval through wiretap channel II (PIR-WTC-II). In PIR-WTC-II, a user wants to retrieve a single message (file) privately out of $M$ messages, which are stored in $N$ replicated and non-communicating databases. An external eavesdropper observes a fraction $\mu_n$ (of its choice) of the traffic exchanged between the $n$th database and the user. In addition to the privacy constraint, the databases should encode the returned answer strings such that the eavesdropper learns absolutely nothing about the \emphcontents of the databases. We aim at characterizing the capacity of the PIR-WTC-II under the combined privacy and security constraints. We obtain a general upper bound for the problem in the form of a max-min optimization problem, which extends the converse proof of the PIR problem under asymmetric traffic constraints. We propose an achievability scheme that satisfies the security constraint by encoding a secret key, which is generated securely at each database, into an artificial noise vector using an MDS code. The user and the databases operate at one of the corner points of the achievable scheme for the PIR under asymmetric traffic constraints such that the retrieval rate is maximized under the imposed security constraint. The upper bound and the lower bound match for the case of $M=2$ and $M=3$ messages, for any $N$, and any $\boldsymbol{\mu}=(\mu_1, \cdots, \mu_N)$.
  • PDF
    DNA as a data storage medium has several advantages, including far greater data density compared to electronic media. We propose that schemes for data storage in the DNA of living organisms may benefit from studying the reconstruction problem, which is applicable whenever multiple reads of noisy data are available. This strategy is uniquely suited to the medium, which inherently replicates stored data in multiple distinct ways, caused by mutations. We consider noise introduced solely by uniform tandem-duplication, and utilize the relation to constant-weight integer codes in the Manhattan metric. By bounding the intersection of the cross-polytope with hyperplanes, we prove the existence of reconstruction codes with greater capacity than known error-correcting codes, which we can determine analytically for any set of parameters.
  • PDF
    We present the construction of a family of erasure correcting codes for distributed storage systems that achieve low repair bandwidth and low repair complexity. The construction is based on two classes of codes, where the primary goal of the first class of codes is to achieve a good fault tolerance, while the second class of codes aims at reducing the repair bandwidth and the repair complexity. The repair procedure is a two-step procedure where parts of the failed node are repaired in the first step using the first code. The downloaded symbols during the first step are cached in the memory and used to repair the remaining erased data symbols at no additional read cost during the second step of the repair process. The first class of codes is based on maximum distance separable (MDS) codes modified using piggybacks, while the second class of codes is designed to reduce the number of additional symbols that need to be downloaded to repair the remaining erased symbols. We show that the proposed codes achieve better repair bandwidth compared to MDS, Piggyback, and local reconstruction codes, while a better repair complexity is achieved when compared to MDS, Zigzag, and Piggyback codes.
  • PDF
    We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $\mathcal O(\log(n))$ bits in one sub-regime, and at most $\mathcal O(n^2)$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest.
  • PDF
    Using a drone as an aerial base station (ABS) to provide coverage to users on the ground is envisaged as a promising solution for beyond fifth generation (beyond-5G) wireless networks. While the literature to date has examined downlink cellular networks with ABSs, we consider an uplink cellular network with an ABS. Specifically, we analyze the use of an underlay ABS to provide coverage for a temporary event, such as a sporting event or a concert in a stadium. Using stochastic geometry, we derive the analytical expressions for the uplink coverage probability of the terrestrial base station (TBS) and the ABS. The results are expressed in terms of (i) the Laplace transforms of the interference power distribution at the TBS and the ABS and (ii) the distance distribution between the ABS and an independently and uniformly distributed (i.u.d.) ABS-supported user equipment and between the ABS and an i.u.d. TBS-supported user equipment. The accuracy of the analytical results is verified by Monte Carlo simulations. Our results show that varying the ABS height leads to a trade-off between the uplink coverage probability of the TBS and the ABS. In addition, assuming a quality of service of 90% at the TBS, an uplink coverage probability of the ABS of over 85% can be achieved, with the ABS deployed at or below its optimal height of typically between 250-500 m for the considered setup.
  • PDF
    Consider a data publishing setting for a data set with public and private features. The objective of the publisher is to maximize the amount of information about the public features in a revealed data set, while keeping the information leaked about the private features bounded. The goal of this paper is to analyze the performance of privacy mechanisms that are constructed to match the distribution learned from the data set. Two distinct scenarios are considered: (i) mechanisms are designed to provide a privacy guarantee for the learned distribution; and (ii) mechanisms are designed to provide a privacy guarantee for every distribution in a given neighborhood of the learned distribution. For the first scenario, given any privacy mechanism, upper bounds on the difference between the privacy-utility guarantees for the learned and true distributions are presented. In the second scenario, upper bounds on the reduction in utility incurred by providing a uniform privacy guarantee are developed.
  • PDF
    Recovery of data packets from packet erasures in a timely manner is critical for many streaming applications. An early paper by Martinian and Sundberg introduced a framework for streaming codes and designed rate-optimal codes that permit delay-constrained recovery from an erasure burst of length up to $B$. A recent work by Badr et al. extended this result and introduced a sliding-window channel model $\mathcal{C}(N,B,W)$. Under this model, in a sliding-window of width $W$, one of the following erasure patterns are possible (i) a burst of length at most $B$ or (ii) at most $N$ (possibly non-contiguous) arbitrary erasures. Badr et al. obtained a rate upper bound for streaming codes that can recover with a time delay $T$, from any erasure patterns permissible under the $\mathcal{C}(N,B,W)$ model. However, constructions matching the bound were absent, except for a few parameter sets. In this paper, we present an explicit family of codes that achieves the rate upper bound for all feasible parameters $N$, $B$, $W$ and $T$.
  • PDF
    This paper considers the massive connectivity application in which a large number of potential devices communicate with a base-station (BS) in a sporadic fashion. The detection of device activity pattern together with the estimation of the channel are central problems in such a scenario. Due to the large number of potential devices in the network, the devices need to be assigned non-orthogonal signature sequences. The main objective of this paper is to show that by using random signature sequences and by exploiting sparsity in the user activity pattern, the joint user detection and channel estimation problem can be formulated as a compressed sensing single measurement vector (SMV) problem or multiple measurement vector (MMV) problem, depending on whether the BS has a single antenna or multiple antennas, and be efficiently solved using an approximate message passing (AMP) algorithm. This paper proposes an AMP algorithm design that exploits the statistics of the wireless channel and provides an analytical characterization of the probabilities of false alarm and missed detection by using the state evolution. We consider two cases depending on whether the large-scale component of the channel fading is known at the BS and design the minimum mean squared error (MMSE) denoiser for AMP according to the channel statistics. Simulation results demonstrate the substantial advantage of exploiting the statistical channel information in AMP design; however, knowing the large-scale fading component does not offer tangible benefits. For the multiple-antenna case, we employ two different AMP algorithms, namely the AMP with vector denoiser and the parallel AMP-MMV, and quantify the benefit of deploying multiple antennas at the BS.
  • PDF
    In Compressive Sensing theory and its applications, quantization of signal measurements, as integrated into any realistic sensing model, impacts the quality of signal reconstruction. In fact, there even exist incompatible combinations of quantization functions (e.g., the 1-bit sign function) and sensing matrices (e.g., Bernoulli) that cannot lead to an arbitrarily low reconstruction error when the number of observations increases. This work shows that, for a scalar and uniform quantization, provided that a uniform random vector, or "random dithering", is added to the compressive measurements of a low-complexity signal (e.g., a sparse or compressible signal, or a low-rank matrix) before quantization, a large class of random matrix constructions known to respect the restricted isometry property (RIP) are made "compatible" with this quantizer. This compatibility is demonstrated by the existence of (at least) one signal reconstruction method, the "projected back projection" (PBP), whose reconstruction error is proved to decay when the number of quantized measurements increases. Despite the simplicity of PBP, which amounts to projecting the back projection of the compressive observations (obtained from their multiplication by the adjoint sensing matrix) onto the low-complexity set containing the observed signal, we also prove that given a RIP matrix and for a single realization of the dithering, this reconstruction error decay is also achievable uniformly for the sensing of all signals in the considered low-complexity set. We finally confirm empirically these observations in several sensing contexts involving sparse signals, low-rank matrices, and compressible signals, with various RIP matrix constructions such as sub-Gaussian random matrices and random partial Discrete Cosine Transform (DCT) matrices.
  • PDF
    This work deals with partial MDS (PMDS) codes, a special class of locally repairable codes, used for distributed storage system. We first show that a known construction of these codes, using Gabidulin codes, can be extended to use any maximum rank distance code. Then we define a standard form for the generator matrices of PMDS codes and use this form to give an algebraic description of PMDS generator matrices. This implies that over a sufficiently large finite field a randomly chosen generator matrix in PMDS standard form generates a PMDS code with high probability. This also provides sufficient conditions on the field size for the existence of PMDS codes.
  • PDF
    In cellular-D2D networks, users can select the communication mode either direct and form D2D links or indirect and communicate with BS. In former case, users should perform pairing selection and choose their pairs. The main focus in this paper is proposing an analytical framework by using tools from stochastic geometry to address these two issues, i.e. i) mode selection for the user devices to be established in either cellular or D2D mode, which is done based on received power from BS influenced by a bias factor, and ii) investigation of choosing nth-nearest neighbor as the serving node for the receiver of interest, by considering full-duplex (FD) radios as well as half- duplex (HD) in the D2D links. The analytic and simulation results demonstrate that even though the bias factor determines the throughput of each mode, it does not have any influence on the system sum throughput. Furthermore, we demonstrate that despite of suffering from self-interference, FD-D2D results in higher system sum throughput as well as higher coverage probability in comparison to its counterpart, namely purely HD- D2D network.

Recent comments

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.