Search

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger–Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time. [ABSTRACT FROM AUTHOR]

The problem of recovering a pair of signals from their blind phaseless short-time Fourier transform measurements arises in several important phase retrieval applications, including ptychography and ultra-short pulse characterization. In this paper, we prove that in order to determine a pair of generic signals uniquely, up to trivial ambiguities, the number of phaseless measurements one needs to collect is, at most, five times the number of parameters required to describe the signals. This result improves significantly upon previous papers, which required the number of measurements to be quadratic in the number of parameters rather than linear. In addition, we consider the simpler problem of recovering a pair of generic signals from their blind short-time Fourier transform, when the phases are known. In this setting, which can be understood as a special case of the blind deconvolution problem, we show that the number of measurements required to determine the two signals, up to trivial ambiguities, equals exactly the number of parameters to be recovered. As a side result, we study the classical phase retrieval problem—that is, recovering a signal from its Fourier magnitudes—when some entries of the signal are known a priori. We derive a bound on the number of required measurements as a function of the size of the set of known entries. Specifically, we show that if most of the signal’s entries are known, then only a few Fourier magnitudes are necessary to determine a signal uniquely. [ABSTRACT FROM AUTHOR]

In this paper, we extend the notion of Cauchy–Schwarz divergence to point processes and establish that the Cauchy–Schwarz divergence between the probability densities of two Poisson point processes is half the squared L^2 -distance between their intensity functions. Extension of this result to mixtures of Poisson point processes and, in the case where the intensity functions are Gaussian mixtures, closed form expressions for the Cauchy–Schwarz divergence are presented. Our result also implies that the Bhattacharyya distance between the probability distributions of two Poisson point processes is equal to the square of the Hellinger distance between their intensity measures. We illustrate the result via a sensor management application where the system states are modeled as point processes. [ABSTRACT FROM PUBLISHER]

We consider the probabilistic group testing problem where $d$ random defective items in a large population of $N$ items are identified with high probability by applying binary tests. It is known that the $\Theta (d \log N)$ tests are necessary and sufficient to recover the defective set with vanishing probability of error when $d = O(N^{\alpha })$ for some $\alpha \in (0, 1)$. However, to the best of our knowledge, there is no explicit (deterministic) construction achieving $\Theta (d \log N)$ tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of $d$) achieves the order optimal $\Theta (d \log N)$ tests in the probabilistic group testing problem when $d = \Omega (\log ^{2}\,\,N)$. This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of $d$. To prove the order-optimality of Kautz and Singleton’s construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests. [ABSTRACT FROM AUTHOR]

The theory of compressed sensing (CS) asserts that an unknown signal x\in \mathbb R ^p can be accurately recovered from an underdetermined set of n linear measurements with n\ll p provided that x is sufficiently sparse. However, in applications, the degree of sparsity is typically unknown, and the problem of directly estimating \|x\|_{0} has been a longstanding gap between theory and practice. A closely related issue is that \|x\|_{0} is a highly idealized measure of sparsity, and for real signals with entries not equal to 0, the value \|x\|0=p is not a useful description of compressibility. In our previous conference paper [1] that examined these problems, we considered an alternative measure of soft sparsity, \|x\|1^{2}/\|x\|2^{2} , and designed a procedure to estimate \|x\|1^{2}/\|x\|2^{2} that does not rely on sparsity assumptions. This paper offers a new deconvolution-based method for estimating unknown sparsity, which has wider applicability and sharper theoretical guarantees. In particular, we introduce a family of entropy-based sparsity measures sq(x)=\big ({\|x\|q}/{\|x\|1}\big )^{({q}/{1-q})} parameterized by q\in [0,\infty ] . This family interpolates between \|x\|_{0}=s_{0}(x) and \|x\|_{1}^{2}/\|x\|_{2}^{2}=s_{2}(x) as q ranges over [0, 2]. For any q\in (0,2]\setminus \{1\} , we propose an estimator \hat {s}_{q}(x) whose relative error converges at the dimension-free rate of 1/\sqrt n , even when p/n\to \infty . Our main results also describe the limiting distribution of \hat sq(x) , as well as some connections to basis pursuit denosing, the Lasso, deterministic measurement matrices, and inference problems in CS. [ABSTRACT FROM PUBLISHER]

This paper presents a new achievable rate-distortion region for the general $L$ channel multiple descriptions (MDs) problem. A well-known general region for this problem is due to Venkataramani, Kramer, and Goyal (VKG). Their encoding scheme is an extension of the El Gamal-Cover (EC) and Zhang–Berger (ZB) coding schemes to the $L$ channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. As in ZB, the scheme also allows for a single common codeword to be shared by all descriptions. This paper proposes a novel encoding technique involving combinatorial message sharing (CMS), where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of. These shared codebooks provide a more flexible framework to tradeoff redundancy across the messages for resilience to descriptions loss. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the VKG region for general sources and distortion measures. We further show that CMS provides a strict improvement of the achievable region for any source and distortion measures for which some two-description subset is such that ZB achieves points outside the EC region. We then show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, including scenarios where the ZB and EC regions coincide for all two-description subsets. In particular, we show that CMS strictly improves on VKG, for the $L$ -channel quadratic Gaussian MD problem, for all $L\geq 3$ , despite the fact that the EC region is complete for the corresponding two-descriptions problem. Consequently, the correlated quantization scheme (an extreme special case of VKG) that has been proven to be optimal for several cross sections of the $L$ -channel quadratic Gaussian MD problem is strictly suboptimal in general. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross sections of the $L$ -channel quadratic Gaussian MD problem. [ABSTRACT FROM AUTHOR]

This paper is concerned with jointly recovering n node variables $\left \{{ x_{i}}\right \} _{1\leq i\leq n} from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of xi-xj ; the observation pattern is represented by a measurement graph \mathcal {G} with an edge set \mathcal E , such that xi-xj is observed if and only if (i,j)\in \mathcal E . To account for noisy measurements in a general manner, we model the data acquisition process by a set of channels with given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, we develop a unified framework to characterize the fundamental recovery criterion, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, our results isolate a family of minimum channel divergence measures to characterize the degree of measurement corruption, which together with the size of the minimum cut of \mathcal G dictates the feasibility of exact information recovery. For various homogeneous graphs, the recovery condition depends almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics; alternatively, the minimum sample complexity required for these graphs scales like (n\log n)/(\mathsf Hel1/2^{\min }) for certain information metric \mathsf Hel1/2^{\min } defined in the main text, as long as the alphabet size is not super-polynomial in n. We apply our general theory to three concrete applications, including the stochastic block model, the random corruption model, and the haplotype assembly problem. Our theory leads to orderwise tight recovery conditions for all these scenarios. [ABSTRACT FROM AUTHOR]

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well-known restricted isometry property cannot be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $\nu $ , the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nr\nu \log ^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different 3-D data and protein molecules validate the effectiveness and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Compressed sensing deals with the recovery of sparse signals from linear measurements. Without any additional information, it is possible to recover an s -sparse signal using m \gtrsim s \log (d/s) measurements in a robust and stable way. Some applications provide additional information, such as on the location the support of the signal. Using this information, it is conceivable that the threshold amount of measurements can be lowered. A proposed algorithm for this task is weighted \ell 1 -minimization. Put shortly, one modifies standard \ell 1 -minimization by assigning different weights to different parts of the index set $[1, \ldots d]$ . The task of choosing the weights is, however, non-trivial. This paper provides a complete answer to the question of an optimal choice of the weights. In fact, it is shown that it is possible to directly calculate unique weights that are optimal in the sense that the threshold amount of measurements needed for exact recovery is minimized. The proof uses recent results about the connection between convex geometry and compressed sensing-type algorithms. [ABSTRACT FROM PUBLISHER]

The problem of detecting correlations from samples of a high-dimensional Gaussian vector has recently received a lot of attention. In most existing work, detection procedures are provided with a full sample. However, following common wisdom in experimental design, the experimenter may have the capacity to make targeted measurements in an on-line and adaptive manner. In this paper, we investigate such adaptive sensing procedures for detecting positive correlations. It is shown that, using the same number of measurements, adaptive procedures are able to detect significantly weaker correlations than their nonadaptive counterparts. We also establish minimax lower bounds that show the limitations of any procedure. [ABSTRACT FROM AUTHOR]

High-order cumulants and high-order spectra play an important role in the theory of stationary processes. For nonlinear processes, it is quite challenging to develop an asymptotic theory for their estimators. This paper presents a systematic asymptotic theory for estimators of high-order moments for a general class of stationary processes, using the framework of functional dependence measures. In particular, we prove the asymptotic normality of the estimators and establish a uniform convergence rate. We also provide a sufficient condition for the summability of high-order cumulants. Based on the latter, we prove consistency and asymptotic normality of the third-order spectra or bispectrum estimators under mild and easily verifiable conditions. [ABSTRACT FROM AUTHOR]

An incoherent low-rank matrix can be efficiently reconstructed after observing a few of its entries at random, and then, solving a convex program that minimizes the nuclear norm. In many applications, in addition to these entries, potentially valuable prior knowledge about the column and row spaces of the matrix is also available to the practitioner. In this paper, we incorporate this prior knowledge in matrix completion—by minimizing a weighted nuclear norm—and precisely quantify any improvements. In particular, we find in theory that reliable prior knowledge reduces the sample complexity of matrix completion by a logarithmic factor, and the observed improvement in numerical simulations is considerably more magnified. We also present similar results for the closely related problem of matrix recovery from generic linear measurements. [ABSTRACT FROM PUBLISHER]

In the context of the phase retrieval problem, it is known that certain natural classes of measurements, such as Fourier measurements and random Bernoulli measurements, do not lead to the unique reconstruction of all possible signals, even in combination with certain practically feasible random masks. To avoid this difficulty, the analysis is often restricted to measurement ensembles (or masks) that satisfy a small-ball probability condition, in order to ensure that the reconstruction is unique. This paper shows a complementary result: for random Bernoulli measurements, there is still a large class of signals that can be reconstructed uniquely, namely, those signals that are non-peaky. In fact, this result is much more general: it holds for random measurements sampled from any subgaussian distribution \mathcal D , without any small-ball conditions. This is demonstrated in two ways: 1) a proof of stability and uniqueness and 2) a uniform recovery guarantee for the PhaseLift algorithm. In all of these cases, the number of measurements $m$ approaches the information-theoretic lower bound. Finally, for random Bernoulli measurements with erasures, it is shown that PhaseLift achieves uniform recovery of all signals (including peaky ones). [ABSTRACT FROM PUBLISHER]

In this paper we prove two results related to the Gaussian optimizers conjecture for multimode bosonic system with gauge symmetry. First, we argue that the classical capacity of an arbitrary Gaussian observable is attained on a Gaussian ensemble of coherent states. This generalizes results previously known for heterodyne measurement in one mode. By using this fact and continuous variable version of ensemble-observable duality, we prove an old conjecture that accessible information of arbitrary Gaussian ensemble is attained on the multimode generalization of the heterodyne measurement. [ABSTRACT FROM AUTHOR]

The design of a detection system in which sensors are randomly located to detect a low-power signal emitter in a random location tends to be difficult because the measurements are conditionally dependent in general and the alternative hypothesis is composite. It is shown that there are conditions that allow a system designer to deal with these problems by assuming a least favorable distribution for the emitter location that not only makes the alternative hypothesis simple and ensures a detection performance, but also causes the measurements to become conditionally i.i.d., making models more amenable for analysis. Since a design based on a least favorable distribution may be considered too conservative, this paper proposes the use of a most favorable distribution for the emitter location and uses the theory of asymptotic relative efficiency (ARE) to evaluate how conservative the design based on a least favorable distribution is. It is further shown that, if the system designer can place sensors in an enlarged deployment region, then there are situations in which the design based on a least favorable distribution becomes less and less conservative as the dimensions of the region of interest increase. [ABSTRACT FROM PUBLISHER]

We introduce two information-theoretical invariants for the projective unitary group acting on a finite-dimensional complex Hilbert space: PVM- and POVM-dynamical (quantum) entropies, which are analogues of the classical Kolmogorov-Sinai entropy rate. They quantify the maximal randomness of the successive quantum measurement results in the case where the evolution of the system between each two consecutive measurements is described by a given unitary operator. We study the class of chaotic unitaries, i.e., the ones of maximal entropy, or equivalently, such that they can be represented by suitably rescaled complex Hadamard matrices in some orthonormal bases. We provide necessary conditions for a unitary operator to be chaotic, which become also sufficient for qubits and qutrits. These conditions are expressed in terms of the relation between the trace and the determinant of the operator. We also compute the volume of the set of chaotic unitaries in dimensions two and three, and the average PVM-dynamical entropy over the unitary group in dimension two. We prove that this mean value behaves as the logarithm of the dimension of the Hilbert space, which implies that the probability that the dynamical entropy of a unitary is almost as large as possible approaches unity as the dimension tends to infinity. [ABSTRACT FROM AUTHOR]

Network navigation is a promising paradigm for providing location awareness in wireless environments, where nodes estimate their locations based on sensor measurements and prior knowledge. In the presence of limited wireless resources, only a subset rather than all of the node pairs can perform inter-node measurements. The procedure of selecting node pairs at different times for inter-node measurements, referred to as network scheduling, affects the evolution of the localization errors. Thus, it is crucial to design efficient scheduling strategies for network navigation. This paper introduces situation-aware scheduling that exploits network states to select measurement pairs, and develops a framework to characterize the effects of scheduling strategies and of network settings on the error evolution. In particular, both sufficient and necessary conditions for the boundedness of the error evolution are provided. Furthermore, opportunistic and random situation-aware scheduling strategies are proposed, and bounds on the corresponding time-averaged network localization errors are derived. These strategies are shown to be optimal in terms of the error scaling with the number of agents. Finally, the reduction of the error scaling by increasing the number of simultaneous measurement pairs is quantified. [ABSTRACT FROM PUBLISHER]

How hard is it to guess a password? Massey showed that a simple function of the Shannon entropy of the distribution from which the password is selected is a lower bound on the expected number of guesses, but one which is not tight in general. In a series of subsequent papers under ever less restrictive stochastic assumptions, an asymptotic relationship as password length grows between scaled moments of the guesswork and specific Rényi entropy was identified. Here, we show that, when appropriately scaled, as the password length grows, the logarithm of the guesswork satisfies a large deviation principle (LDP), providing direct estimates of the guesswork distribution when passwords are long. The rate function governing the LDP possesses a specific, restrictive form that encapsulates underlying structure in the nature of guesswork. Returning to Massey's original observation, a corollary to the LDP shows that expectation of the logarithm of the guesswork is the specific Shannon entropy of the password selection process. [ABSTRACT FROM AUTHOR]

We establish the fundamental limits of lossless analog compression by considering the recovery of arbitrary random vectors $ {{ {\mathsf {x}}}} \in {\mathbb R} ^{m}$ from the noiseless linear measurements $ {{ {\mathsf {y}}}} = {{ {A}}} {{ {\mathsf {x}}}} $ with measurement matrix $ {{ {A}}} \in {\mathbb R} ^{n\times m}$. Our theory is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression but applies to the nonasymptotic, i.e., fixed- $m$ case, and considers zero error probability. Specifically, our achievability result states that, for Lebesgue-almost all $ {{ {A}}} $ , the random vector $ {{ {\mathsf {x}}}} $ can be recovered with zero error probability provided that $n>K({{ {\mathsf {x}}}})$ , where $K({{ {\mathsf {x}}}})$ is given by the infimum of the lower modified Minkowski dimension over all support sets $ {\mathcal {U}} $ of $ {{ {\mathsf {x}}}} $ (i.e., sets $ {\mathcal {U}} \subseteq {\mathbb R} ^{m}$ with $ {\mathrm {P}} [ {{ {\mathsf {x}}}} \in {\mathcal {U}} ]=1$). We then particularize this achievability result to the class of $s$ -rectifiable random vectors as introduced in Koliander et al. (2016); these are random vectors of absolutely continuous distribution—with respect to the $s$ -dimensional Hausdorff measure—supported on countable unions of $s$ -dimensional $C^{1}$ -submanifolds of $ {\mathbb R} ^{m}$. Countable unions of $C^{1}$ -submanifolds include essentially all signal models used in the compressed sensing literature such as the standard union of subspaces model underlying much of compressed sensing theory and spectrum-blind sampling, smooth submanifolds, block-sparsity, and low-rank matrices as considered in the matrix completion problem. Specifically, we prove that, for Lebesgue-almost all $ {{ {A}}} $ , $s$ -rectifiable random vectors $ {{ {\mathsf {x}}}} $ can be recovered with zero error probability from $n>s$ linear measurements. This threshold is, however, found not to be tight as exemplified by the construction of an $s$ -rectifiable random vector that can be recovered with zero error probability from $n< s$ linear measurements. Motivated by this observation, we introduce the new class of $s$ -analytic random vectors, which admit a strong converse in the sense of $n\geq s$ being necessary for recovery with probability of error smaller than one. The central conceptual tools in the development of our theory are geometric measure theory and the theory of real analytic functions. [ABSTRACT FROM AUTHOR]

Recently, a nonconvex relaxation of low-rank matrix recovery (LMR), called the Schatten-p quasi-norm minimization (0< p< 1), was introduced instead of the previous nuclear norm minimization in order to approximate the problem of LMR closer. In this paper, we introduce a notion of the restricted p-isometry constants (0< p\leq 1) and derive a p-RIP condition for exact reconstruction of LMR via Schatten-p quasi-norm minimization. In particular, we determine how many random, Gaussian measurements are needed for the p-RIP condition to hold with high probability, which gives a theoretical result that it needs fewer measurements with small p for exact recovery via Schatten-p quasi-norm minimization than when p=1. [ABSTRACT FROM PUBLISHER]

We analyze the stability of standard, buffered, slotted-Aloha systems. Specifically, we consider a set of N users, each equipped with an infinite buffer. Packets arrive into user i's buffer according to some stationary ergodic Markovian process of intensity \lambdai. At the beginning of each slot, if user i has packets in its buffer, it attempts to transmit a packet with fixed probability pi over a shared resource/channel. The transmission is successful only when no other user attempts to use the channel. The stability of such systems has been open since their very first analysis in 1979 by Tsybakov and Mikhailov. In this paper, we propose an approximate stability condition that is provably exact when the number of users N grows large. We provide theoretical evidence and numerical experiments to explain why the proposed approximate stability condition is extremely accurate even for systems with a restricted number of users (even two or three). [ABSTRACT FROM AUTHOR]

In this paper, we study the question of the representation of random variables by means of frames or Riesz basis generated by stationary sequences. This concerns the representation of continuous time wide sense stationary random processes by means of discrete samples. [ABSTRACT FROM AUTHOR]

We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number. [ABSTRACT FROM AUTHOR]

We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures—the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically. [ABSTRACT FROM AUTHOR]

We extend upper bounds on the quantum independence number and the quantum Shannon capacity of graphs to their counterparts in the commuting operator model. We introduce a von Neumann algebraic generalization of the fractional Haemers bound (over $\mathbb {C}$) and prove that the generalization upper bounds the commuting quantum independence number. We call our bound the tracial Haemers bound, and we prove that it is multiplicative with respect to the strong product. In particular, this makes it an upper bound on the Shannon capacity. The tracial Haemers bound is incomparable with the Lovász theta function, another well-known upper bound on the Shannon capacity. We show that separating the tracial and fractional Haemers bounds would refute Connes’ embedding conjecture. Along the way, we prove that the tracial rank and tracial Haemers bound are elements of the (commuting quantum) asymptotic spectrum of graphs (Zuiddam, Combinatorica, 2019). We also show that the inertia bound (an upper bound on the quantum independence number) upper bounds the commuting quantum independence number. [ABSTRACT FROM AUTHOR]

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast that arises between the binary-alphabet and larger alphabet settings. This is surprising in some instances, since characterizations for the larger alphabet settings do not generalize their binary-alphabet counterparts. In particular, we show that $f $ -divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that Kullback–Leibler (KL) divergence is the unique Bregman divergence, which is also an $f $ -divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence, which is invariant to statistically sufficient transformations of the data, even when nondecomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three. [ABSTRACT FROM AUTHOR]

It has been shown recently that the framework of quantum sampling, as introduced by Bouman and Fehr, can lead to new entropic uncertainty relations highly applicable to finite-key cryptographic analyses. Here we revisit these so-called sampling-based entropic uncertainty relations, deriving newer, more powerful, relations and applying them to source-independent quantum random number generators and high-dimensional quantum key distribution protocols. Along the way, we prove several interesting results in the asymptotic case for our entropic uncertainty relations. These sampling-based approaches to entropic uncertainty, and their application to quantum cryptography, hold great potential for deriving proofs of security for quantum cryptographic systems, and the approaches we use here may be applicable to an even wider range of scenarios. [ABSTRACT FROM AUTHOR]

A unified approach is presented for establishing a broad class of Cramér–Rao inequalities for the location parameter, including, as special cases, the original inequality of Cramér and Rao, as well as an L^p version recently established by the authors. The new approach allows for generalized moments and Fisher information measures to be defined by convex functions that are not necessarily homogeneous. In particular, it is shown that associated with any log-concave random variable whose density satisfies certain boundary conditions is a Cramér–Rao inequality for which the given log-concave random variable is the extremal. Applications to specific instances are also provided. [ABSTRACT FROM PUBLISHER]

The trade-off between the two types of error probabilities in binary state discrimination may be quantified in the asymptotics by various error exponents. In the composite case, where the hypotheses consist of sets of states, any such exponent is upper bounded by the infimum of the corresponding pairwise exponents of discriminating individual members of the two sets. Attainability of this upper bound may depend on the type of exponents considered; whether the problem is classical or quantum; the cardinality and the geometric properties of the sets representing the hypotheses; and also on the dimensionality of the underlying Hilbert space. Our main contribution is clarifying this landscape considerably. We show that in the quantum case unattainability is the general behaviour for all the exponents, already in finite dimension, for a simple null-hypothesis and an alternative hypothesis consisting of only two states. Moreover, the upper bound may be strict even in the infinite-dimensional classical case if the alternative hypothesis contains at least countably infinitely many states. We also prove general attainability results, e.g., for classical adversarial and arbitrarily varying hypothesis testing, and for the quantum case where all states are pure, or the states commute with every state in the opposite hypothesis. [ABSTRACT FROM AUTHOR]

Data samples from ${\mathbb{R}}^ {d}$ with a common support of size $k$ are accessed through $m$ random linear projections (measurements) per sample. It is well-known that roughly $k$ measurements from a single sample are sufficient to recover the support. In the multiple sample setting, do $k$ overall measurements still suffice when only $m$ measurements per sample are allowed, with $m < k$ ? We answer this question in the negative by considering a generative model setting with independent samples drawn from a subgaussian prior. We show that $n=\Theta ((k^{2}/ m^{2})\cdot \log k(d- k))$ samples are necessary and sufficient to recover the support exactly. In turn, this shows that when $m < k$ , $k$ overall measurements are insufficient for support recovery; instead we need about $m$ measurements each from $k^{2}/ m^{2}$ samples, and therefore $k^{2}/ m$ overall measurements are necessary. [ABSTRACT FROM AUTHOR]

Whereas Shannon entropy is related to the growth rate of multinomial coefficients, we show that the quadratic entropy (Tsallis 2-entropy) is connected to their $ {q}$ -deformation; when $ {q}$ is a prime power, these $ {q}$ -multinomial coefficients count flags of finite vector spaces with prescribed length and dimensions. In particular, the $ {q}$ -binomial coefficients count vector subspaces of a given dimension. We obtain in this way a combinatorial explanation for the nonadditivity of the quadratic entropy, which arises from a recursive counting of flags. We show that the statistical systems whose configurations are described by flags provide a frequentist justification for the maximum entropy principle with Tsallis statistics. We then introduce a discrete-time stochastic process associated to the $ {q}$ -binomial probability distribution, that generates at time $ {n}$ a vector subspace of $\mathbb {F}_{ {q}}^{ {n}}$ (here $\mathbb {F}_{ {q}}$ is the finite field of order $ {q}$). The concentration of measure on certain “typical subspaces” allows us to extend the asymptotic equipartition property to this setting. The size of the typical set is quantified by the quadratic entropy. We discuss the applications to Shannon theory, particularly to source coding, when messages correspond to vector spaces. [ABSTRACT FROM AUTHOR]

The Pursley-Sarwate criterion of a pair of finite complex-valued sequences measures the collective smallness of the aperiodic autocorrelations and the aperiodic cross-correlations of the two sequences. It is known that this quantity is always at least 1 with equality if and only if the sequence pair is a Golay pair. We exhibit pairs of complex-valued sequences whose entries have unit magnitude for which the Pursley-Sarwate criterion tends to 1 as the sequence length tends to infinity. Our constructions use different carefully chosen Chu sequences. [ABSTRACT FROM AUTHOR]

We establish quantitative stability results for the entropy power inequality (EPI). Specifically, we show that if uniformly log-concave densities nearly saturate the EPI, then they must be close to Gaussian densities in the quadratic Kantorovich-Wasserstein distance. Furthermore, if one of the densities is Gaussian and the other is log-concave, or more generally has positive spectral gap, then the deficit in the EPI can be controlled in terms of the $L^{1}$ -Kantorovich-Wasserstein distance or relative entropy, respectively. As a counterpoint, an example shows that the EPI can be unstable with respect to the quadratic Kantorovich-Wasserstein distance when densities are uniformly log-concave on sets of measure arbitrarily close to one. Our stability results can be extended to non-log-concave densities, provided certain regularity conditions are met. The proofs are based on mass transportation. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering sparse vectors from underdetermined linear measurements via $\ell _{p}$ -constrained basis pursuit. Previous analyses of this problem based on generalized restricted isometry properties have suggested that two phenomena occur if $p\neq 2$. First, one may need substantially more than $s \log (en/s)$ measurements (optimal for $p=2$ ) for uniform recovery of all $s$ -sparse vectors. Second, the matrix that achieves recovery with the optimal number of measurements may not be Gaussian (as for $p=2$ ). We present a new, direct analysis, which shows that in fact neither of these phenomena occur. Via a suitable version of the null space property, we show that a standard Gaussian matrix provides $\ell _{q}/\ell _{1}$ -recovery guarantees for $\ell _{p}$ -constrained basis pursuit in the optimal measurement regime. Our result extends to several heavier-tailed measurement matrices. As an application, we show that one can obtain a consistent reconstruction from uniform scalar quantized measurements in the optimal measurement regime. [ABSTRACT FROM AUTHOR]

We consider a phase retrieval problem, where we want to reconstruct a $n$ -dimensional vector from its phaseless scalar products with $m$ sensing vectors, independently sampled from complex normal distributions. We show that, with a suitable initialization procedure, the classical algorithm of alternating projections (Gerchberg–Saxton) succeeds with high probability when $m\geq Cn$ , for some $C>0$ . We conjecture that this result is still true when no special initialization procedure is used, and present numerical experiments that support this conjecture. [ABSTRACT FROM PUBLISHER]

Semiconstrained systems (SCSs) were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply the techniques from constrained systems, we study the sequences of constrained systems that are contained in, or contain, a given SCS, while approaching its capacity. In the former case, we describe two such sequences resulting in constant-to-constant bit-rate block encoders and finite-state encoders. Perhaps surprisingly, we show in the latter case, under commonly made assumptions, that the only constrained system that contains a given SCS is the entire space. A refinement to this result is also provided, in which semiconstraints and zero constraints are mixed together. [ABSTRACT FROM AUTHOR]

A recent trend in compressed sensing is to consider nonconvex optimization techniques for sparse recovery. The important case of F -minimization has become of particular interest, for which the exact reconstruction condition (ERC) in the noiseless setting can be precisely characterized by the null space property (NSP). However, little work has been done concerning its robust reconstruction condition (RRC) in the noisy setting. We look at the null space of the measurement matrix as a point on the Grassmann manifold, and then study the relation between the ERC and RRC sets, denoted as \Omega _{J} and \Omega _{J}^{r} , respectively. It is shown that \Omega J^{r} is the interior of \Omega J , from which a previous result of the equivalence of ERC and RRC for \ell p -minimization follows easily as a special case. Moreover, when F is nondecreasing, it is shown that \overline {\Omega }_{J}\setminus \mathop {\mathrm {int\kern 0pt}} (\Omega _{J}) is a set of measure zero and of the first category. As a consequence, the probabilities of ERC and RRC are the same if the measurement matrix \mathbf {A} is randomly generated according to a continuous distribution. Quantitatively, if the null space \mathcal N( A) lies in the d -interior of \Omega J , then RRC will be satisfied with the robustness constant C=2+2d/d\sigma \min (\mathbf {A^{\top })} ; and conversely, if RRC holds with C=2-2d/d\sigma \max (\mathbf {A^{\top })} , then \mathcal N( A) must lie in $d$ -interior of \Omega J . We also present several rules for comparing the performances of different cost functions. Finally, these results are capitalized to derive achievable tradeoffs between the measurement rate and robustness with the aid of Gordon’s escape through the mesh theorem or a connection between NSP and the restricted eigenvalue condition. [ABSTRACT FROM PUBLISHER]

We examine the well-known problem of determining the capacity of multidimensional run-length-limited constrained systems. By recasting the problem, which is essentially a combinatorial counting problem, into a probabilistic setting, we are able to derive new lower and upper bounds on the capacity of (0,k)-RLL systems. These bounds are better than all previously-known analytical bounds for k\geqslant 2, and are tight asymptotically. Thus, we settle the open question: what is the rate at which the capacity of (0,k)-RLL systems converges to 1 as k\rightarrow\infty? We also provide the first nontrivial upper bound on the capacity of general (d,k)-RLL systems. [ABSTRACT FROM AUTHOR]