BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

David Stotz

David Stotz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.IT

Catalog footprint

What is connected

7works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

7 published item(s)

preprint2020arXiv

Canonical Conditions for K/2 Degrees of Freedom

We present a necessary and sufficient condition for $1/2$ degree of freedom for each user in constant $K$-user single-antenna interference channels. This condition applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving $1/2$ degree of freedom for each user for all channel matrices satisfying our condition.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Degrees of freedom in vector interference channels

This paper continues the Wu-Shamai-Verdu program [3] on characterizing the degrees of freedom (DoF) of interference channels (ICs) through Renyi information dimension. Specifically, we find a single-letter formula for the DoF of vector ICs, encompassing multiple-input multiple-output (MIMO) ICs, time- and/or frequency-selective ICs, and combinations thereof, as well as scalar ICs as considered in [3]. The DoF-formula we obtain lower-bounds the DoF of all channels--with respect to the choice of the channel matrix--and upper-bounds the DoF of almost all channels. It applies to a large class of noise distributions, and its proof is based on an extension of a result by Guionnet and Shlyakthenko [3] to the vector case in combination with the Ruzsa triangle inequality for differential entropy introduced by Kontoyiannis and Madiman [4]. As in scalar ICs, achieving full DoF requires the use of singular input distributions. Strikingly, in the vector case it suffices to enforce singularity on the joint distribution of each individual transmit vector. This can be realized through signaling in subspaces of the ambient signal space, which is in accordance with the idea of interference alignment, and, most importantly, allows the scalar entries of the transmit vectors to have non-singular distributions. The DoF-formula for vector ICs we obtain enables a unified treatment of "classical" interference alignment a la Cadambe and Jafar [5], and Maddah-Ali et al. [6], and the number-theoretic schemes proposed in [7], [8]. Moreover, it allows to calculate the DoF achieved by new signaling schemes for vector ICs. We furthermore recover the result by Cadambe and Jafar on the non-separability of parallel ICs [9] and we show that almost all parallel ICs are separable in terms of DoF. Finally, our results apply to complex vector ICs, thereby extending the main findings of [2] to the complex case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information-Theoretic Limits of Matrix Completion

We propose an information-theoretic framework for matrix completion. The theory goes beyond the low-rank structure and applies to general matrices of "low description complexity". Specifically, we consider $m\times n$ random matrices $\mathbf{X}$ of arbitrary distribution (continuous, discrete, discrete-continuous mixture, or even singular). With $\mathcal{S}$ an $\varepsilon$-support set of $\mathbf{X}$, i.e., $\mathrm{P}[\mathbf{X}\in\mathcal{S}]\geq 1-\varepsilon$, and $\underline{\mathrm{dim}}_\mathrm{B}(\mathcal{S})$ denoting the lower Minkowski dimension of $\mathcal{S}$, we show that $k> \underline{\mathrm{dim}}_\mathrm{B}(\mathcal{S})$ trace inner product measurements with measurement matrices $A_i$, suffice to recover $\mathbf{X}$ with probability of error at most $\varepsilon$. The result holds for Lebesgue a.a. $A_i$ and does not need incoherence between the $A_i$ and the unknown matrix $\mathbf{X}$. We furthermore show that $k> \underline{\mathrm{dim}}_\mathrm{B}(\mathcal{S})$ measurements also suffice to recover the unknown matrix $\mathbf{X}$ from measurements taken with rank-one $A_i$, again this applies to a.a. rank-one $A_i$. Rank-one measurement matrices are attractive as they require less storage space than general measurement matrices and can be applied faster. Particularizing our results to the recovery of low-rank matrices, we find that $k>(m+n-r)r$ measurements are sufficient to recover matrices of rank at most $r$. Finally, we construct a class of rank-$r$ matrices that can be recovered with arbitrarily small probability of error from $k<(m+n-r)r$ measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Characterizing degrees of freedom through additive combinatorics

We establish a formal connection between the problem of characterizing degrees of freedom (DoF) in constant single-antenna interference channels (ICs), with general channel matrix, and the field of additive combinatorics. The theory we develop is based on a recent breakthrough result by Hochman in fractal geometry. Our first main contribution is an explicit condition on the channel matrix to admit full, i.e., $K/2$ DoF; this condition is satisfied for almost all channel matrices. We also provide a construction of corresponding DoF-optimal input distributions. The second main result is a new DoF-formula exclusively in terms of Shannon entropies. This formula is more amenable to both analytical statements and numerical evaluations than the DoF-formula by Wu et al., which is in terms of Rényi information dimension. We then use the new DoF-formula to shed light on the hardness of finding the exact number of DoF in ICs with rational channel coefficients, and to improve the best known bounds on the DoF of a well-studied channel matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Explicit and almost sure conditions for K/2 degrees of freedom

It is well known that in K-user constant single-antenna interference channels K/2 degrees of freedom (DoF) can be achieved for almost all channel matrices. Explicit conditions on the channel matrix to admit K/2 DoF are, however, not available. The purpose of this paper is to identify such explicit conditions, which are satisfied for almost all channel matrices. We also provide a construction of corresponding asymptotically DoF-optimal input distributions. The main technical tool used is a recent breakthrough result by Hochman in fractal geometry.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Super-Resolution from Short-Time Fourier Transform Measurements

While spike trains are obviously not band-limited, the theory of super-resolution tells us that perfect recovery of unknown spike locations and weights from low-pass Fourier transform measurements is possible provided that the minimum spacing, $Δ$, between spikes is not too small. Specifically, for a cutoff frequency of $f_c$, Donoho [2] shows that exact recovery is possible if $Δ> 1/f_c$, but does not specify a corresponding recovery method. On the other hand, Candès and Fernandez-Granda [3] provide a recovery method based on convex optimization, which provably succeeds as long as $Δ> 2/f_c$. In practical applications one often has access to windowed Fourier transform measurements, i.e., short-time Fourier transform (STFT) measurements, only. In this paper, we develop a theory of super-resolution from STFT measurements, and we propose a method that provably succeeds in recovering spike trains from STFT measurements provided that $Δ> 1/f_c$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Almost Lossless Analog Signal Separation

We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals from a noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on almost lossless analog compression. The main results of the present paper are a general achievability bound for the compression rate in the analog signal separation problem, an exact expression for the optimal compression rate in the case of signals that have mixed discrete-continuous distributions, and a new technique for showing that the intersection of generic subspaces with subsets of sufficiently small Minkowski dimension is empty. This technique can also be applied to obtain a simplified proof of a key result in Wu and Verdú (2010).

0 citations0 reviewsNo code linkedOpen access