BZPEERReading, trust and collaboration for research
Menu

Discover

SearchFind papers, people, topics and opportunities from one place.GraphOpen maps around papers, topics and saved views.

Workspaces

HomeOpen the ranked research feed.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Sergio Verdú

Sergio Verdú contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITmath.PRmath.STStatistics TheoryCryptography and SecurityMachine Learning

Trust snapshot

Quick read

Trust 21 - Emerging
11works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2016arXiv

$f$-divergence Inequalities

This paper develops systematic approaches to obtain $f$-divergence inequalities, dealing with pairs of probability measures defined on arbitrary alphabets. Functional domination is one such approach, where special emphasis is placed on finding the best possible constant upper bounding a ratio of $f$-divergences. Another approach used for the derivation of bounds among $f$-divergences relies on moment inequalities and the logarithmic-convexity property, which results in tight bounds on the relative entropy and Bhattacharyya distance in terms of $χ^2$ divergences. A rich variety of bounds are shown to hold under boundedness assumptions on the relative information. Special attention is devoted to the total variation distance and its relation to the relative information and relative entropy, including "reverse Pinsker inequalities," as well as on the $E_γ$ divergence, which generalizes the total variation distance. Pinsker's inequality is extended for this type of $f$-divergence, a result which leads to an inequality linking the relative entropy and relative information spectrum. Integral expressions of the Rényi divergence in terms of the relative information spectrum are derived, leading to bounds on the Rényi divergence in terms of either the variational distance or relative entropy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

$f$-Divergence Inequalities via Functional Domination

This paper considers derivation of $f$-divergence inequalities via the approach of functional domination. Bounds on an $f$-divergence based on one or several other $f$-divergences are introduced, dealing with pairs of probability measures defined on arbitrary alphabets. In addition, a variety of bounds are shown to hold under boundedness assumptions on the relative information. The journal paper, which includes more approaches for the derivation of f-divergence inequalities and proofs, is available on the arXiv at https://arxiv.org/abs/1508.00335, and it has been published in the IEEE Trans. on Information Theory, vol. 62, no. 11, pp. 5973-6006, November 2016.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Key Capacity for Product Sources with Application to Stationary Gaussian Processes

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication between two terminals. This yields an alternative information-theoretic-converse-style proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a water-filling solution of the communication-rate--key-rate tradeoff for a wide class of discrete memoryless vector Gaussian sources which subsumes the case without an eavesdropper. Moreover, we derive an explicit formula for the maximum secret key per bit of communication for all discrete memoryless vector Gaussian sources using a tensorization property and a variation on the enhanced channel technique of Weingarten et al. Finally, a one-shot information spectrum achievability bound for key generation is proved from which we characterize the communication-rate--key-rate tradeoff for stationary Gaussian processes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Nonasymptotic noisy lossy source coding

This paper shows new general nonasymptotic achievability and converse bounds and performs their dispersion analysis for the lossy compression problem in which the compressor observes the source through a noisy channel. While this problem is asymptotically equivalent to a noiseless lossy source coding problem with a modified distortion function, nonasymptotically there is a noticeable gap in how fast their minimum achievable coding rates approach the common rate-distortion function, as evidenced both by the refined asymptotic analysis (dispersion) and the numerical results. The size of the gap between the dispersions of the noisy problem and the asymptotically equivalent noiseless problem depends on the stochastic variability of the channel through which the compressor observes the source.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Channels with cost constraints: strong converse and dispersion

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints and performs refined analysis of the third order term in the asymptotic expansion of the maximum achievable channel coding rate, showing that it is equal to $\frac 1 2 \frac {\log n}{n}$ in most cases of interest. The analysis is based on a non-asymptotic converse bound expressed in terms of the distribution of a random variable termed the $\mathsf b$-tilted information density, which plays a role similar to that of the $\mathsf d$-tilted information in lossy source coding. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Resolvability in Eγ with Applications to Lossy Compression and Wiretap Channels

We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the $E_γ$ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d.~setting where $γ=\exp(nE)$, a (nonnegative) randomness rate above $\inf_{Q_{\sf U}: D(Q_{\sf X}||π_{\sf X})\le E} \{D(Q_{\sf X}||π_{\sf X})+I(Q_{\sf U},Q_{\sf X|U})-E\}$ is necessary and sufficient to asymptotically approximate the output distribution $π_{\sf X}^{\otimes n}$ using the channel $Q_{\sf X|U}^{\otimes n}$, where $Q_{\sf U}\to Q_{\sf X|U}\to Q_{\sf X}$. The new resolvability result is then used to derive a one-shot upper bound on the error probability in the rate distortion problem, and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d.~settings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Variable-length compression allowing errors

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability $ε$, for lossless compression. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: $$(1 - ε) k H(\mathsf S) - \sqrt{\frac{k V(\mathsf S)}{2 π} } e^{- \frac {(Q^{-1}(ε))^2} 2 }$$ where $Q^{-1}(\cdot)$ is the functional inverse of the standard Gaussian complementary cdf, and $V(\mathsf S)$ is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of $1 - ε$, but this asymptotic limit is approached from below, i.e. larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fixed-length lossy compression in the finite blocklength regime

This paper studies the minimum achievable source coding rate as a function of blocklength $n$ and probability $ε$ that the distortion exceeds a given level $d$. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be closely approximated by $R(d) + \sqrt{\frac{V(d)}{n}} Q^{-1}(ε)$, where $R(d)$ is the rate-distortion function, $V(d)$ is the rate dispersion, a characteristic of the source which measures its stochastic variability, and $Q^{-1}(ε)$ is the inverse of the standard Gaussian complementary cdf.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Key Capacity with Limited One-Way Communication for Product Sources

We show that for product sources, rate splitting is optimal for secret key agreement using limited one-way communication at two terminals. This yields an alternative proof of the tensorization property of a strong data processing inequality originally studied by Erkip and Cover and amended recently by Anantharam et al. We derive a `water-filling' solution of the communication-rate--key-rate tradeoff for two arbitrarily correlated vector Gaussian sources, for the case with an eavesdropper, and for stationary Gaussian processes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Lossy joint source-channel coding in the finite blocklength regime

This paper finds new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the non-asymptotic regime. A joint source-channel code maps a block of $k$ source symbols onto a length$-n$ channel codeword, and the fidelity of reproduction at the receiver end is measured by the probability $ε$ that the distortion exceeds a given threshold $d$. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfy $nC - kR(d) \approx \sqrt{nV + k \mathcal V(d)} Q(ε)$, where $C$ and $V$ are the channel capacity and channel dispersion, respectively; $R(d)$ and $\mathcal V(d)$ are the source rate-distortion and rate-dispersion functions; and $Q$ is the standard Gaussian complementary cdf. Symbol-by-symbol (uncoded) transmission is known to achieve the Shannon limit when the source and channel satisfy a certain probabilistic matching condition. In this paper we show that even when this condition is not satisfied, symbol-by-symbol transmission is, in some cases, the best known strategy in the non-asymptotic regime.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Phase Transitions in Compressed Sensing

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. process with known distribution. Three classes of encoders are considered, namely optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by error probability and noise sensitivity in the absence and presence of measurement noise, respectively. The optimal phase transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

0 citations0 reviewsNo code linkedOpen access