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.
604
questions
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 ...
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 ...
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 ...
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$...
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}
...
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 ...
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 ...
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-...
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|...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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).
...
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., $\...
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 ...
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 ...
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 ...
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 ...
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?
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}^{\...
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 ...
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 ...
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, ...
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 ...
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 ...
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|...
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-...
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 ...
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 ...
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 ...
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 - (...
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 ...
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 ...
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 $...
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 ...
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 ...