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.

Filter by
Sorted by
Tagged with
3 votes
0 answers
179 views

A.G. Vitushkin's "Easily representable families of functions" - can it be generalized?

Background In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...
dima's user avatar
  • 949
4 votes
1 answer
215 views

Transfinitely iterated limit computability

Call a real $x$ limit computable iff there is a Turing machine $T$ such that, for any $i\in\omega$, there is $t(i)\in\omega$ such that the $i$th entry on the tape is not changed after time $t(i)$ and ...
M Carl's user avatar
  • 521
3 votes
0 answers
211 views

Find a minimum entropy code for a simple gibbs random field.

Just to make precise what I am talking about, I will include the definition of a minimum entropy code. I will then define the precise markov random field I am asking about. In the rest of this ...
Alin's user avatar
  • 131
2 votes
1 answer
868 views

Continuity of relative entropy with respect to the weak* topology

Let $X$ be a measurable space, and let $T$ be a measurable transformation $T:X \to X$. Let $\mathcal{P}(X)$ be the space of probability measures on $X$, equipped with the weak* topology. Define the $T$...
Vladimir's user avatar
  • 1,210
5 votes
1 answer
754 views

Upper bound on joint Renyi entropy

Renyi entropy of a random pair $(X,Y)$ with probability distribution $p_{X,Y}$ is defined by \begin{equation} H_\alpha(X,Y) = \frac{1}{1-\alpha}\log\sum_{x,y} p_{X,Y}(x,y)^\alpha. \end{equation} ...
newuser's user avatar
  • 61
6 votes
1 answer
742 views

Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...
Brazen's user avatar
  • 61
5 votes
2 answers
614 views

Proving that a complicated function is eventually concave

I have a function $f:\mathbb{R}^+ \to \mathbb{R}^+$ that I want to prove is eventually concave - i.e. that there exists $\gamma _0 > 0$ such that for every $\gamma>\gamma_0$, $f(\gamma)$ is ...
Yair Carmon's user avatar
8 votes
2 answers
513 views

Maximum entropy priors in infinite dimensional spaces

Is there an extension of maximum entropy probability distributions for function spaces? For $\mathbb{R}^n$ and discrete spaces, there is much literature about this problem under names such as "non-...
Nick Alger's user avatar
  • 1,140
5 votes
0 answers
291 views

The partition function of a discrete memoryless channel at capacity

Suppose we have a discrete memoryless channel with input and output alphabets each composed of $n$ symbols $\{x_j\}$ and $\{y_k\}$, respectively, and specified by the matrix $W_{jk} := \mathbb{P}(y_k|...
Steve Huntsman's user avatar
2 votes
1 answer
284 views

MMSE estimator expressed through cumulants

I have a linear model $$Y=HX+N,$$ where $H$ is a matrix and $X$ are drawn from $p_X(X)$, and $N$ is Gaussian noise variates. Now, if $X$ is multivariate Gaussian, then a linear estimator $\hat{X}=A+BY$...
Pierre Robert's user avatar
1 vote
1 answer
190 views

Channel capacity of a coin flip

I'm having some issue in understanding the channel capacity. $C=max_{p(x)}I(X, Y)$ In particular the practical side. For example (an exercise), if I toss a fair coin and I transmit the result in a ...
Andrea's user avatar
  • 13
3 votes
1 answer
5k views

With Huffman code, why do we still need Shannon code?

I'm studying information theory by myself. I'm confused about that since we already have Huffman code, which is the optimal code method, why are Shannon code and some other code still useful? I ...
user18717's user avatar
  • 351
4 votes
1 answer
262 views

curvature of curves in the space of gaussians measures

I have a sequence of symmetric positive definite matrices in $GL(n)$ (in my case, covariance matrices of some gaussians) and vectors $R^n$ (the mean of these gaussians). I consider this sequence to be ...
WhitAngl's user avatar
  • 481
0 votes
2 answers
210 views

How to find the minimum string length to produce a set of a given size with a minimum pairwise Hamming distance

Given an alphabet of $q \ge 2$ letters, I want to construct a set $S$ of $x$ strings (of uniform length) such that the minimum Hamming distance between any two strings is $d$. What I need to figure ...
user25603's user avatar
29 votes
1 answer
1k views

Can a string's sophistication be defined in an unsophisticated way?

This question is about sophistication, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define ...
Scott Aaronson's user avatar
2 votes
1 answer
2k views

How to find next to optimal path in hidden Markov model or what should be LIST-Viterbi algorithm?

The Viterbi algorithm is an algorithm for finding the most likely sequence of hidden states – called the Viterbi path. Question If I am interested in list of several paths - optimal, sub-optimal, ...
Alexander Chervov's user avatar
1 vote
1 answer
445 views

What are "best" polynoms f(x) g(x) of degree n ? I.e. ideal generated by them is as far from zero as possible ? (Best convolutional codes.)

Consider polynoms f(x) g(x) of degree at most n. (I am mostly interested about F_2[x]). Let us multiply them by arbitrary polynoms p(x) i.e. consider ideal (p f , p g) in $F_2[x]\oplus F_2[x]$. Let ...
Alexander Chervov's user avatar
3 votes
0 answers
147 views

Find polynoms f,g such that for any polynom p(x): |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms.

How to construct examples (describe all) polynoms f,g such that for any polynom p(x) not equal to zero: |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms (=Hamming weight, by the way it ...
Alexander Chervov's user avatar
3 votes
1 answer
372 views

The degrees in a random subgraph

Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$. Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
0 votes
1 answer
218 views

Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Everything over F_2. Let us define Hamming norm of polynom |p(x)| = number of non-zero monoms. Respectivly for a pair of polynoms |[p ; g]| = |p| +|g|. Consider linear map $F_2[x] \to F_2[x] \oplus ...
Alexander Chervov's user avatar
3 votes
3 answers
895 views

Structure of F_p[G], for finite group G ?

Consider group algebra k[G] of finite group G. If k is alg.closed then every irrep lives there with multiplicity equal to dimension. (More conceptually as bimodule over GxG it is multiplicity free and ...
Alexander Chervov's user avatar
5 votes
2 answers
2k views

Is there a simple relation between the entropy of a matrix and its characteristic polynomial?

Assume $M$ is an invertible positive matrix of rank $N$. The Von Neumann entropy $H$ of a matrix $M$ with eigenvalues $\{ \lambda_n \}$ is $H[M] = -\sum_{n=1}^N \lambda_n \ln \lambda_n$. In ...
Jess Riedel's user avatar
1 vote
1 answer
232 views

Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)

Fix polynoms g1(x), g2(x) over F_2[x]. Question: How to find minimum over polynoms p(x) of the: HammingWeight(p(x) g1(x) ) + HammingWeight(p(x) g2(x) ) ? By HammingWeight of polynom I mean number ...
Alexander Chervov's user avatar
4 votes
3 answers
648 views

Good codes in practice for correcting combination of errors and erasures

In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?
Kelvin Lee's user avatar
2 votes
1 answer
502 views

Error correcting codes obtained as superposition of two codes e.g. CRC+Convolutional

Setup reminder: linear block error-correcting code is some linear subspace $C$ in $F_2^N$. (Correcting error means to find a point $c \in C$ which is "nearest" to a given $r$ in $F_2^N$, $r$ is ...
Alexander Chervov's user avatar
2 votes
1 answer
497 views

What is matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)

Everything over F_2. For any matrix $A$ define the number $N(A) = min_{x}$ HammingWeight $( [x , Ax])$. Where $x$ is vector and [a,b] is just concatenation of vectors: (a_1,...a_n, b_1,...,b_m). ...
Alexander Chervov's user avatar
0 votes
2 answers
718 views

multivariate distributions unaffected by unitary transformations

Hi, In my research I reached some very nice results for IID complex Gaussian vectors $\bf{x}$. Now I realize that my results hold for any random vectors that are unaffected by a unitary map, i.e., $\...
Tommaso's user avatar
1 vote
2 answers
286 views

How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)

Let us consider polynoms over $F_2$. Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40). Question: How many k-nomials belong to ...
Alexander Chervov's user avatar
4 votes
1 answer
343 views

What odd-length binary codes have Hamming weights restricted to be multiples of eight?

Let $G$ be a $k$ by $n$ binary matrix with row vectors $\lbrace \vec{x}_j {\rbrace} _{j=1}^k$. We can interpret $G$ as a generator matrix of a linear $[n,k]$ code $\cal{C}$ whose codewords consist of ...
Jim Harrington's user avatar
6 votes
2 answers
530 views

Number of neigbour Voronoi cells for a random set of points on S^k or cube [-1, 1]^k?

Consider $S^k \subset R^{k+1} $. Sample $N$ points by say uniform distribution. (Example k=120, N=2^24, i.e. N>>k ). Consider Voronoi cell around each point. How many neighbours would a cell have ...
Alexander Chervov's user avatar
4 votes
1 answer
1k views

Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity ...
Alexander Chervov's user avatar
0 votes
1 answer
412 views

Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
K A Khan's user avatar
  • 243
2 votes
2 answers
478 views

prove that flat shape maximizes a functional

The following functional arises in an information theoretic problem that I work on currently. $I(G(\omega)) = \int_{-\kappa\pi}^{\kappa\pi} \frac{A}{G(\omega)+A}d\omega-\frac{| \int_{-\kappa\pi}^{\...
Pierre Robert's user avatar
3 votes
2 answers
190 views

Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes

Math Motivation: consider LINEAR subspace $L$ in $R^n$ and given vector $E$ in $R^n$, then it is easy to find a closest vector $S \in L$ to $E$ - just ortogonal projection. Question Are they some ...
Alexander Chervov's user avatar
2 votes
1 answer
302 views

Error bounds for truncating a probability distribution based on the entropy?

Heuristic Background Consider a set of states labeled $n=1,2,...$ in order of non-increasing probability $p(n)$. The standard Shannon argument gives meaning to the entropy $S$ of $p$ in terms of the ...
Physics Monkey's user avatar
2 votes
2 answers
351 views

Will "error locating codes" have higher rates than ECCs?

I'm wondering to detect all the errors (i.e. their positions) in a codeword $(c_0, c_1, \cdots, c_{n-1})\in Q$ where $Q$ is an alphabet set with size $q$, i.e., to know whether $c_i$ is faulty or not, ...
Kelvin Lee's user avatar
5 votes
1 answer
811 views

Turing machines and Ising model

I have currently started a new research line aiming to prove a mapping between a 2-symbol Turing machine and the one dimensional Ising model. The connection is seen by recognizing that a set of ...
Jon's user avatar
  • 1,657
2 votes
2 answers
580 views

Measuring the independence between the components of a stochastic process

In a context of blind source separation (e.g. you want to extract the voice of a singer from a song), many approaches consist in maximizing the independence between the components of a certain ...
Mathieu Galtier's user avatar
1 vote
0 answers
4k views

Conditional KL divergence

Let $p$ and $q$ be two joint distributions of finite random variables $X$ and $Y$. Recall the definition of conditional KL divergence between $p$ and $q$ of $X$ conditioned on $Y$: $D_{KL}(q(X|Y)||p(X|...
Vladimir's user avatar
  • 1,210
4 votes
1 answer
2k views

Bounding Entropy in terms of KL-Divergence

Let $h(X)$ be the differential entropy of a continuous random variable $X$ with density $f$, and let $Y$ be another continuous random variable with density $g$. If $KL(X\mid\mid Y)$ is the Kullback-...
Ben Charrow's user avatar
3 votes
4 answers
2k views

History of the Sampling Theorem

In January, 1949, Shannon publishes the paper Communication in the Presence of Noise, Proc. IRE, Vol. 37, no. 1, pp. 10-21, available here, which establishes the Information Theory. In this paper, the ...
Papiro's user avatar
  • 1,568
4 votes
3 answers
9k views

Computing channel capacities for non-symmetric channels

I'm studying information theory right now and I'm reading about channel capacities. I know that there are known expressions for computing the capacities for some well known simple channels such as ...
Kelvin Lee's user avatar
2 votes
3 answers
593 views

mutual information and minimal communication required for generating correlation

Let $X$,$Y$ be two stochastic variables with probability distribution $\rho(X,Y)$. The mutual information, $I(X;Y)$, represents the information shared by the two variables. This intuitive ...
Alm's user avatar
  • 1,159
12 votes
2 answers
2k views

Proving a messy inequality

EDIT: After much work I was able to reduce the inequality to a single variable function which I need to show is non-positive. That function is (for $0\leq p\leq\frac{1}{2}$) $$\frac{p^2(\log(p))^2 - (...
VSJ's user avatar
  • 1,024
3 votes
0 answers
125 views

Is a parametric family which is universally consistent for multiple quantiles impossible?

Suppose I am dead-set on using Bayesian inference on independent and identically distributed data, but I'm lazy and insist on using a parametric likelihood function come what may. I'd be reassured to ...
R Hahn's user avatar
  • 2,721
4 votes
1 answer
1k views

Generalizing inequality relating Euclidean distance & Frobenius norm to Bregman divergences such as relative entropy & von Neumann divergence

Motivation- A Special Case Supposing $A,B\in\mathbb{S}^{m\times m}$ are symmetric positive semi-definite (SPD) matrices and $\mathbf{x}\in\mathbb{R}^m$ is a unit vector where $\|\mathbf{x}\|=1$, we ...
ppyang's user avatar
  • 607
1 vote
0 answers
85 views

Given the Fourier coefficient moduli, how to choose the phases to have integer components?

Take $n\geq 1$, and let $c_1,...,c_n$ be $n$ non-negative numbers. For every $\phi_1,...,\phi_n$, the formulae $$v_k=\sum_{j=1}^n c_k \omega^{jk+\phi_k}$$ define a vector $v\in \mathbb{R}^n$, where $...
kaleidoscop's user avatar
  • 1,268
13 votes
3 answers
2k views

Hot-topics in error correcting coding related to interesting math. ?

What are topics in error-correcting coding which are related to interesting math. ? I am primarely interested in nowdays hot topics, but old days topics are also welcome. Let me try to mention what ...
1 vote
0 answers
157 views

Morse code-like information channels

I'd like to know if there's any literature about information channels of the following sort. Sender can transmit a 0 or a 1 on each clock cycle --- but with the side condition that all the delays ...
David Feldman's user avatar
7 votes
2 answers
2k views

Are algebraic geometry error correcting codes (Goppa codes) "good" ?

Question (informal version): Are algebraic geometry error correcting codes (V.D. Goppa codes) "good" ? Some details. There is certain construction of error-correcting codes by means of algebraic ...
Alexander Chervov's user avatar

1
9
10
11 12 13