# Questions tagged [it.information-theory]

Theoretical and experimental aspects of information theory and coding theory. This tag covers but is not limited to following branches: information theory, information geometry, optimal transportation theory, coding theory.

617 questions
Filter by
Sorted by
Tagged with
1 vote
28 views

### From a constraint satisfaction problem (CSP) to a sudoku grid

one of the existing methods of solvin a sudoku grid is via constraints satisfaction (CSP), but can we do the inverse ie convert a CSP problem into a sudoku grid and then solve it ?
13 views

### Efficient compression techniques for low-rank matrix $A$ to maintain multiplication compatibility？

Suppose we have a large low-rank matrix $A$ and an input matrix $X$ (where $X$ is a tall, skinny matrix). We need to compute the product $AX$. To reduce computational cost and data transfer when ...
1 vote
68 views

### Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule ...
• 2,911
1 vote
74 views

### Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$. Assume the ...
• 15
11 views

1 vote
110 views

### Generalization of error-correcting codes

If you have a binary single-error correcting code with n-bit codewords, then it is the case that taking only a fixed n-1 out of the n bits gives an “approximate” code with the property that, for any ...
• 827
168 views

### Estimating means of multiple Gaussians

Let's say we have two Gaussian distributions $\mathcal{N}(\mu_1, \sigma^2I_d)$ and $\mathcal{N}(\mu_2, \sigma^2I_d)$. We are trying to get estimators $\hat \mu_1, \hat \mu_2$ to minimize the following ...
76 views

### Does there exist an established name for the exponential of surprisal (e.g. the reciprocal of probability?)

There are several different names that I know of for the exponential of the entropy of which "diversity" and "perplexity" are fairly well-established. Tom Leinster has a very ...
• 4,617
580 views

### A general inequality for KL divergence of functions of variables

The question concerns a very general setting and a very general inequality about KL divergence. I'm writing this thread to verify whether my intuition is correct. Let $E_1, E_2$ be two measurable ...
51 views

### Classifier-specific lower bounds on the misclassification rate in binary classification

Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...
• 13
49 views

• 720
269 views

### Bounding Kullback-Leibler

Suppose we have a probability distribution $P$ on a finite set $S$. We draw $N$ i.i.d. samples according to $P$ and use these samples to define an empirical distribution $R$. We measure the Kullback-...
• 3,819
1 vote
81 views

### Min-sum belief propagation not working on a chain model with equal unary potentials

Given is a chain factor graph as presented in the image below with the following properties: Each node can take values 0 or 1 All unary potentials are equal (e.g. $U(a)=0$) for every node $a$ All ...
120 views

• 334
86 views

### Asymptotic approximation of Fisher information matrix for small Gaussian perturbation

Let $$X=Y/a+b+\epsilon Z,$$ where $Y\sim\operatorname{Poisson}(\lambda)$ and $Z\sim\mathcal N(0,1)$ are independent. Also define $\theta=(\lambda,a,b,\epsilon)$. The Fisher information matrix  ...
1 vote
191 views

Let $\rho$ be a positive trace class operator on $H\otimes H$, where $H$ is a separable Hilbert space (not necessarily finite dimensional). We say that $\rho$ is countable separable if $\rho=\sum_{i=... • 11 2 votes 0 answers 45 views ### Moduli spaces of 'generalized mutually unbiased bases' Mutually unbiased bases in$\mathbb{C}^n$with a chosen inner product are collections of orthonormal bases such that for each pair of orthonormal bases$e_i,f_i$,$i=1,\ldots,n$we have$|\langle e_i, ...
• 1,061
Let $X\sim \mathcal{N}(\mu,\sigma^2)$ be a Gaussian random variable with random mean $\mu\sim {\sf Bernoulli}(p)$, i.e., $\mu=1$ with probability $p$ and $\mu=0$ with probability $1-p$. In other words,...