Information Theory (cs.IT)

  • PDF
    In phase retrieval problems, a signal of interest (SOI) is reconstructed based on the magnitude of a linear transformation of the SOI observed with additive noise. The linear transform is typically referred to as a measurement matrix. Many works on phase retrieval assume that the measurement matrix is a random Gaussian matrix, which, in the noiseless scenario with sufficiently many measurements, guarantees invertability of the transformation between the SOI and the observations, up to an inherent phase ambiguity. However, in many practical applications, the measurement matrix corresponds to an underlying physical setup, and is therefore deterministic, possibly with structural constraints. In this work we study the design of deterministic measurement matrices, based on maximizing the mutual information between the SOI and the observations. We characterize necessary conditions for the optimality of a measurement matrix, and analytically obtain the optimal matrix in the low SNR regime. Practical methods for designing general measurement matrices and masked Fourier measurements are proposed. Simulation tests demonstrate the performance gain achieved by the proposed techniques compared to random Gaussian measurements for various phase recovery algorithms.
  • PDF
    Recent regulatory changes proposed by the Federal Communications Commission (FCC) permitting unlicensed use of television white space (TVWS) channels present new opportunities for designing wireless networks that make efficient use of this spectrum. The favorable propagation characteristics of these channels and their widespread availability, especially in rural areas, make them well-suited for providing broadband services in sparsely populated regions where economic factors hinder deployment of such services on licensed spectrum. In this context, this paper explores the deployment of an outdoor Wi-Fi-like network operating in TVWS channels, referred to commonly as a Super Wi-Fi network. Since regulations governing unlicensed use of these channels allow (a) mounting fixed devices up to a height of 30 m and operation at transmit powers of up to 4 W EIRP, and (b) operation at transmit powers of up to 100 mW EIRP for portable devices, such networks can provide extended coverage and higher rates than traditional Wi-Fi networks. However, these gains are subject to the viability of the uplink from the portable devices (clients) to the fixed devices (access points (AP)) because of tighter restrictions on transmit power of clients compared to APs. This paper leverages concepts from stochastic geometry to study the performance of such networks with specific focus on the effect of (a) transmit power asymmetry between APs and clients and its impact on uplink viability and coverage, and (b) the interplay between height and transmit power of APs in determining the network throughput. Such an analysis reveals that (a) maximum coverage of no more than 700 m is obtained even when APs are deployed at 30 m height, and (b) operating APs at transmit power of more than 1 W is beneficial only at sparse deployment densities when rate is prioritized over coverage.
  • PDF
    Millimeter wave (mmWave) communications have been considered as a key technology for future 5G wireless networks. In order to overcome the severe propagation loss of mmWave channel, mmWave multiple-input multiple-output (MIMO) systems with analog/digital hybrid precoding and combining transceiver architecture have been widely considered. However, physical layer security (PLS) in mmWave MIMO systems and the secure hybrid beamformer design have not been well investigated. In this paper, we consider the problem of hybrid precoder and combiner design for secure transmission in mmWave MIMO systems in order to protect the legitimate transmission from eavesdropping. When eavesdropper's channel state information (CSI) is known, we first propose a joint analog precoder and combiner design algorithm which can prevent the information leakage to the eavesdropper. Then, the digital precoder and combiner are computed based on the obtained effective baseband channel to further maximize the secrecy rate. Next, if prior knowledge of the eavesdropper's CSI is unavailable, we develop an artificial noise (AN)-based hybrid beamforming approach, which can jam eavesdropper's reception while maintaining the quality-of-service (QoS) of intended receiver at the pre-specified level. Simulation results demonstrate that our proposed algorithms offer significant secrecy performance improvement compared with other hybrid beamforming algorithms.
  • PDF
    For noisy compressive sensing systems, the asymptotic distortion with respect to an arbitrary distortion function is determined when a general class of least-square based reconstruction schemes is employed. The sampling matrix is considered to belong to a large ensemble of random matrices including i.i.d. and projector matrices, and the source vector is assumed to be i.i.d. with a desired distribution. We take a statistical mechanical approach by representing the asymptotic distortion as a macroscopic parameter of a spin glass and employing the replica method for the large-system analysis. In contrast to earlier studies, we evaluate the general replica ansatz which includes the RS ansatz as well as RSB. The generality of the solution enables us to study the impact of symmetry breaking. Our numerical investigations depict that for the reconstruction scheme with the "zero-norm" penalty function, the RS fails to predict the asymptotic distortion for relatively large compression rates; however, the one-step RSB ansatz gives a valid prediction of the performance within a larger regime of compression rates.
  • PDF
    Physical layer security has been considered as an important security approach in wireless communications to protect legitimate transmission from passive eavesdroppers. This paper investigates the physical layer security of a wireless multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) communication system in the presence of a multiple-antenna eavesdropper. We first propose a transmit-filter-assisted secure MIMO-OFDM system which can destroy the orthogonality of eavesdropper's signals. Our proposed transmit filter can disturb the reception of eavesdropper while maintaining the quality of legitimate transmission. Then, we propose another artificial noise (AN)-assisted secure MIMO-OFDM system to further improve the security of the legitimate transmission. The time-domain AN signal is designed to disturb the reception of eavesdropper while the legitimate transmission will not be affected. Simulation results are presented to demonstrate the security performance of the proposed transmit filter design and AN-assisted scheme in the MIMO-OFDM system.
  • PDF
    This paper investigates the problem of hybrid precoder and combiner design for multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) systems operating in millimeter-wave (mmWave) bands. We propose a novel iterative scheme to design the codebook-based analog precoder and combiner in forward and reverse channels. During each iteration, we apply compressive sensing (CS) technology to efficiently estimate the equivalent MIMO-OFDM mmWave channel. Then, the analog precoder or combiner is obtained based on the orthogonal matching pursuit (OMP) algorithm to alleviate the interference between different data streams as well as maximize the spectral efficiency. The digital precoder and combiner are finally obtained based on the effective baseband channel to further enhance the spectral efficiency. Simulation results demonstrate the proposed iterative hybrid precoder and combiner algorithm has significant performance advantages.
  • PDF
    In this paper, a practical wireless transmission scheme is proposed to transmit confidential messages to the desired user securely and precisely by the joint use of multiple tools including artificial noise (AN) projection, phase alignment (PA)/beamforming, and random subcarrier selection (RSCS) based on OFDM, and directional modulation (DM), short for RSCS-OFDM-DM. This RSCS-OFDM-DM scheme provides an extremely low-complexity structure for the desired receiver and makes the secure and precise wireless transmission realizable in practical. For illegitimate eavesdroppers, the receive power of confidential messages is so weak that their receivers cannot intercept these confidential messages successfully once it is corrupted by AN. In such a scheme, the design of phase alignment/beamforming vector and AN projection matrix depend intimately on the desired direction angle and distance. It is particularly noted that the use of RSCS leads to a significant outcome that the receive power of confidential messages mainly concentrates on the small adjacent region around the desired receiver and only its power small fraction leaks out to the remaining large broad regions. This concept is called secure precise transmission. The probability density function of real-time receive signal-to-interference-and-noise ratio (SINR) is derived, and the average SINR is attained. From simulation and analysis, it follows that the proposed scheme actually can achieve a secure and precise wireless transmission of confidential messages in line-of-propagation channel and can be applied to the various future wireless scenarios.
  • PDF
    Analog/digital hybrid precoder and combiner have been widely used in millimeter wave (mmWave) multiple-input multiple-output (MIMO) systems due to its energy-efficient and economic superiorities. Infinite resolution of phase shifters (PSs) for the analog beamformer can achieve very close performance compared to the full-digital scheme but will result in high complexity and intensive power consumption. Thus, more cost effective and energy efficient low resolution PSs are typically used in practical mmWave MIMO systems. In this paper, we consider the joint hybrid precoder and combiner design with one-bit quantized PSs in mmWave MIMO systems. We propose to firstly design the analog precoder and combiner pair for each data stream successively, aiming at conditionally maximizing the spectral efficiency. We present a novel binary analog precoder and combiner optimization algorithm under a Rank-1 approximation of the interference-included equivalent channel with lower than quadratic complexity. Then the digital precoder and combiner are computed based on the obtained baseband effective channel to further enhance the spectral efficiency. Simulation results demonstrate that the proposed algorithm outperforms the existing one-bit PSs based hybrid beamforming scheme.
  • PDF
    Millimeter-wave (mmWave) communications have been considered as a key technology for future 5G wireless networks because of the orders-of-magnitude wider bandwidth than current cellular bands. In this paper, we consider the problem of codebook-based joint analog-digital hybrid precoder and combiner design for spatial multiplexing transmission in a mmWave multiple-input multiple-output (MIMO) system. We propose to jointly select analog precoder and combiner pair for each data stream successively aiming at maximizing the channel gain while suppressing the interference between different data streams. After all analog precoder/combiner pairs have been determined, we can obtain the effective baseband channel. Then, the digital precoder and combiner are computed based on the obtained effective baseband channel to further mitigate the interference and maximize the sum-rate. Simulation results demonstrate that our proposed algorithm exhibits prominent advantages in combating interference between different data streams and offer satisfactory performance improvement compared to the existing codebook-based hybrid beamforming schemes.
  • PDF
    We consider a user-centric co-operative cellular network, where base stations close to a mobile co-operate to detect its signal using a (joint) linear minimum-mean-square-error receiver. The base stations, which have multiple antennas, and mobiles are modeled as independent Poisson Point Processes to avoid dependence on specific node locations. Combining stochastic geometry and infinite random matrix theory, we derive a simple expression for the spectral efficiency of this complex system as the number of antennas grows large. This expression is verified by Monte Carlo simulations which support its utility for even a moderate number of antennas. This result reveals the influence of tangible system parameters such as mobile and base-station densities, number of antennas per base station, and number of co-operating base stations on achievable spectral efficiencies. For instance, we find that for a given base station density and a constraint on the total number of co-operating antennas, all co-operating antennas should be located at a single base station. On the other hand, in our asymptotic regime, for the same number of co-operating antennas, if the network is limited by the area density of antennas, then the number of co-operating base stations should be increased with fewer antennas per base station.
  • PDF
    In the coded caching framework proposed by Maddah Ali and Niesen, there are two classes of coding schemes known in the literature, namely uncoded prefetching schemes and coded prefetching schemes. In this work, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen, when the number of files is no larger than that of users. We make a critical observation that a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. The intermediate operating points of this general scheme can in fact provide new tradeoff points previously not known in the literature, however, explicit characterizing the performance of this general scheme appears rather difficult.
  • PDF
    Most of the codes that have an algebraic decoding algorithm are derived from the Reed Solomon codes. They are obtained by taking equivalent codes, for example the generalized Reed Solomon codes, or by using the so-called subfield subcode method, which leads to Alternant codes and Goppa codes over the underlying prime field, or over some intermediate subfield. The main advantages of these constructions is to preserve both the minimum distance and the decoding algorithm of the underlying Reed Solomon code. In this paper, we propose a generalization of the subfield subcode construction by introducing the notion of subspace subcodes and a generalization of the equivalence of codes which leads to the notion of generalized subspace subcodes. When the dimension of the selected subspaces is equal to one, we show that our approach gives exactly the family of the codes obtained by equivalence and subfield subcode technique. However, our approach highlights the links between the subfield subcode of a code defined over an extension field and the operation of puncturing the $q$-ary image of this code. When the dimension of the subspaces is greater than one, we obtain codes whose alphabet is no longer a finite field, but a set of r-uples. We explain why these codes are practically as efficient for applications as the codes defined on an extension of degree r. In addition, they make it possible to obtain decodable codes over a large alphabet having parameters previously inaccessible. As an application, we give some examples that can be used in public key cryptosystems such as McEliece.
  • PDF
    We consider the problem of querying a string (or, a database) of length $N$ bits to determine all the locations where a substring (query) of length $M$ appears either exactly or is within a Hamming distance of $K$ from the query. We assume that sketches of the original signal can be computed off line and stored. Using the sparse Fourier transform computation based approach introduced by Pawar and Ramchandran, we show that all such matches can be determined with high probability in sub-linear time. Specifically, if the query length $M = O(N^\mu)$ and the number of matches $L=O(N^\lambda)$, we show that for $\lambda < 1-\mu$ all the matching positions can be determined with a probability that approaches 1 as $N \rightarrow \infty$ for $K \leq \frac{1}{6}M$. More importantly our scheme has a worst-case computational complexity that is only $O\left(\max\{N^{1-\mu}\log^2 N, N^{\mu+\lambda}\log N \}\right)$, which means we can recover all the matching positions in \it sub-linear time for $\lambda<1-\mu$. This is a substantial improvement over the best known computational complexity of $O\left(N^{1-0.359 \mu} \right)$ for recovering one matching position by Andoni \em et al. \citeandoni2013shift. Further, the number of Fourier transform coefficients that need to be computed, stored and accessed, i.e., the sketching complexity of this algorithm is only $O\left(N^{1-\mu}\log N\right)$. Several extensions of the main theme are also discussed.

Recent comments

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.

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)