Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Background: The Shannon sampling theorem states that a bandlimited function (an $L^2$ function whose Fourier transform has compact support) can be determined uniquely from sampling it an integer lattice. More precisely, if the Fourier transform* $\hat{f}$ is supported in $[-\Omega/2, \Omega/2]$ (which we express by writing $f \in B_{\Omega}$) and $\tau>0$ satisfies $\Omega \tau \leq 1$, then $f$ can be reconstructed from the family $\{ f(k\tau)}_{k \in \mathbb{Z}}$. This is proved more or less by periodizing and reducing to the theory of Fourier series. A higher-dimensional analog using lattices in higher dimensions can be proved similarly.

Question: What sets can these uniformly spaced lattices be replaced by? Is there a general criterion, or some characterization of the collection of such sets (e.g. measure-theoretic)?

If $\Omega$ is fixed, then for what sets $E$ (say, countable), is the map $B_{\Omega} \to \mathbb{R}^E$ injective?

Motivation: I overheard a conversation between a graduate student and a faculty member; the student wished to determine if one had a ``deformed lattice'' $\{ k\tau + X_k \}$ where $\tau$ was a very small mesh relative to $\Omega$ and the $X_k$ was a sequence of reals, for what sequences $\{X_k\}$ would the samples $\{f(k\tau + X_k)\}$ determine $f \in B_{\Omega}$? We could think of the $X_k$ as independent bounded random variables with a small variance, for instance. He suspected (and wanted to know) whether the set of singular parameters (where this information was insufficient) would be a set of measure zero. Intuitively, the small mesh size suggests something like this should be the case.

It was suggested that one might use some sort of finite-dimensional approximations to the full space $B_{\Omega}$ and taking finite subsets of the whole deformed lattice, and that the set of admissible $X_k$ would be some algebraic subvariety of proper codimension, therefore of measure zero, but it wasn't clear how to do this. This led to my more general question boxed above.

Another reason this question may be of interest is that the sampling used in practical applications (e.g. CAT-scans) does not sample based upon a lattice pattern as in the Shannon theorem.

*I am using the normalization with the factor $2\pi$ for the Fourier transform.

share|improve this question
I was just reminded of Dyson's idea to classify one-dimensional quasicrystals...I wonder if there is some relationship between such objects and the thrust of your question. –  Steve Huntsman Apr 10 '10 at 3:01
add comment

1 Answer

up vote 5 down vote accepted

One sufficient condition is that, if $|X_k| <= L$ for some $L < 1/4$ then the sampling map would be an injection, as well as a bounded map from $B$ to $l^2$. This is known as Kadec's theorem.


Nonuniform Sampling and Reconstruction in Shift-Invariant Spaces, Akram Aldroubi and Karlheinz Gröchenig, SIAM Review, Vol. 43, No. 4 (Dec., 2001), pp. 585-620

for a survey and further references.

share|improve this answer
Thanks! $ $ –  Akhil Mathew May 29 '10 at 12:01
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.