Information and communication theory, circuits

Start here

• ConceptKullback–Leibler divergence

  The Kullback–Leibler divergence $D(P \,\|\, Q)$, also called relative entropy, measures how much a probability distribution $P$ differs from a reference distribution $Q$. It is non-negative and equals $0$ exactly when $P = Q$, but it is not symmetric and is not a metric. It is the rate function in Sanov's theorem and the expected log-likelihood ratio in statistics. In information theory, it is the extra code length when one codes for $Q$ but the data follow $P$.

• TheoremNyquist–Shannon sampling theorem

  Let $B > 0$. Let $f, g \in L^2(\R)$ be continuous band-limited functions with bandwidth $B$, that is, their Fourier transforms vanish almost everywhere outside $[-B, B]$. If $f(k / (2B)) = g(k / (2B))$ for every $k \in \Z$, then $f = g$.

• TheoremWhittaker–Shannon interpolation formula

  Let $B > 0$, and let $f \in L^2(\R)$ be a continuous band-limited function with bandwidth $B$, that is, its Fourier transform vanishes almost everywhere outside $[-B, B]$. Let $\operatorname{sinc}(t) = \sin(\pi t)/(\pi t)$ for $t \ne 0$ and $\operatorname{sinc}(0) = 1$. Then $$f(x) = \sum_{k \in \Z} f\Big( \frac{k}{2B} \Big)\, \operatorname{sinc}(2Bx - k) \quad \text{for every } x \in \R,$$ where the series converges in $L^2(\R)$ and uniformly on $\R$.

• ConceptCompressed sensing

  Compressed sensing is the recovery of a sparse vector from far fewer linear measurements than its length. Let $x \in \R^N$ have at most $s$ nonzero entries, and let $y = Ax$ for a suitable $m \times N$ matrix $A$ with $m$ much smaller than $N$. Then $x$ can be found from $y$ by solving a convex problem. The key sufficient condition on $A$ is the restricted isometry property, which random matrices satisfy with high probability when $m$ is of order $s \log(N/s)$. It was developed by Candès, Romberg, Tao and Donoho in the mid-2000s and is used in medical imaging and signal processing.

• ConceptRestricted isometry property

  A matrix has the restricted isometry property of order $s$ when it nearly preserves the length of every vector with at most $s$ nonzero entries. The size of the distortion is measured by the restricted isometry constant $\delta_s$. If $\delta_{2s}$ is small, $s$-sparse vectors can be recovered stably from their images by $\ell^1$ minimization. This is the basis of compressed sensing. Computing $\delta_s$ exactly is hard, but random Gaussian matrices have small constants with high probability.

• ConceptMatching pursuit

  Matching pursuit is a greedy algorithm that builds an approximation of a vector from a dictionary of unit vectors, one element at a time. At each step it picks the dictionary element most correlated with the current residual and removes the projection of the residual on that element. It gives a cheap way to compute n-term approximations and sparse approximations when the exact problem is too hard. A variant, orthogonal matching pursuit, re-projects onto all chosen elements at each step.