Basis Lab

Answers · The mathematics underneath

How can a finite list of samples be turned into frequencies and back with nothing lost?

In shortA finite list can be converted into frequencies and back exactly, because the transform is a reversible change of description, not a lossy summary.

Nothing is lost. A record of NN readings becomes NN numbers, and those numbers determine the readings uniquely; the inverse sum returns them to the last digit. The transform is a reversible change of description, not a summary that keeps the important part and drops the rest. The rest of the answer is the arithmetic that makes that claim true, including why the count of numbers on the two sides matches.

Xk=∑n=0N−1x[n] e−2πikn/N,x[n]=1N∑k=0N−1Xk e+2πikn/N.X_k = \sum_{n=0}^{N-1} x[n]\,e^{-2\pi i k n/N}, \qquad x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X_k\,e^{+2\pi i k n/N}.

The probe at rate kk is a single turning arrow, e−2πikn/Ne^{-2\pi i k n/N} at the nnth reading. Multiplying a reading by it produces an arrow whose across component is what a cosine probe would give and whose up component is what a sine probe would give. Adding those arrows over nn therefore does both jobs in one pass. Complex numbers are not an extra idea here; they are two real numbers carried together, which is exactly what the pair of probes was carrying separately.

The count

For a record of NN readings the distinct rates run from zero cycles across the record up to half a cycle per reading, which is N/2N/2 cycles across the record when NN is even. Above that, a probe turns so fast between readings that at the reading instants it repeats the values of a slower probe turning the other way. The duplicate is not a new question. For integer mm, e−2πi(k+mN)n/N=e−2πikn/Ne^{-2\pi i(k+mN)n/N}=e^{-2\pi i k n/N}, so shifting the rate by NN changes nothing at all. The mirror relation XN−k=Xk‾X_{N-k}=\overline{X_k}, which holds because the readings x[n]x[n] are real, is the same fact written in the output.

FIG 1
cycles across the recordindependent real numbers
01
12
22
32
41

The ledger for eight readings balances as 1+2+2+2+1=81+2+2+2+1=8. Rate zero carries one number, the average, because the probe does not turn and its up part is forced to zero. Rate four carries one number, because the probe flips sign at every reading and a shift by half a step cannot be expressed by the readings. Rates one, two and three carry two numbers each. That is eight real numbers from eight readings, not sixteen, and none of them is redundant.

Why it is not a summary

The natural guess is that asking how much of each rhythm is present must be lossy, because it sounds like averaging. That guess would be right if the transform kept only the size of each arrow. Size alone throws away direction, and two records with the same rhythm strengths but different timings would become indistinguishable. The transform keeps the whole arrow, direction included. The direction is the phase, and it is one of the two numbers that make the ledger balance. Dropping it would leave fewer numbers than readings and no exact inverse.

Take four readings x[0]=3x[0]=3, x[1]=1x[1]=1, x[2]=−3x[2]=-3, x[3]=−1x[3]=-1. At rate zero the products are 3,1,−3,−13,1,-3,-1, which sum to 00. At rate two the probe is 1,−1,1,−11,-1,1,-1, so the products are 3,−1,−3,13,-1,-3,1, which again sum to 00. At rate one the products are 3,−i,3,−i3,-i,3,-i, because the probe turns a quarter turn each step, so X1=6−2iX_1=6-2i. At rate three the products are 3,i,3,i3,i,3,i, so X3=6+2iX_3=6+2i. The fourth rate is the mirror of the second, as the relation requires.

The inverse runs the same arrows backwards and divides by four. For n=0n=0, x[0]=14(X0+X1+X2+X3)=14(0+(6−2i)+0+(6+2i))=3x[0]=\frac14(X_0+X_1+X_2+X_3)=\frac14(0+(6-2i)+0+(6+2i))=3. For n=1n=1, x[1]=14(X0+iX1−X2−iX3)=14(0+(2+6i)−0+(2−6i))=1x[1]=\frac14(X_0+iX_1-X_2-iX_3)=\frac14(0+(2+6i)-0+(2-6i))=1. The other two readings come back the same way. Nothing was rounded and no arrow was discarded.

∑n=0N−1e2πi(k−l)n/N={N,k=l,0,k≠l.\sum_{n=0}^{N-1} e^{2\pi i(k-l)n/N} = \begin{cases} N, & k=l,\\ 0, & k\ne l.\end{cases}

That identity is the algebraic reason the inverse is exact. Substitute the transform into the inverse sum. Every term with k≠lk\ne l sums to zero over a full set of probe positions, and the matching term contributes NN, which the factor 1/N1/N cancels. The cancellation is exact for the same reason a full turn of an arrow has zero average.

The exactness does depend on using all the rates that are distinct. If the readings are complex rather than real, the mirror relation is no longer forced, so all NN rates are independent and the inverse still holds with NN complex outputs. If the record is shortened, the distinct rates shrink with it; a rate above half a cycle per reading aliases to a lower rate and cannot be recovered as a separate question. The sign in the exponent and the placement of 1/N1/N are conventions, but the count and the exact inverse are not.

Worth keeping

  • The transform of N readings produces N independent real numbers, and the inverse sum rebuilds the readings exactly.
  • Rates above half a cycle per reading duplicate lower rates at the reading instants, so they add no new information.
  • Keeping only the size of each frequency would discard phase and destroy the exact inverse.

Where this goes next

This question is one step of The Fourier Transform, a course that works through its subject from the beginning. The page that teaches this part of it is The Transform of a Finite List, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. How does the FFT get the same answer without doing all the multiplications?The FFT gets the same spectrum by splitting the readings into even and odd positions and reusing the two half-length results for every rate, so shared partial sums are computed once instead of once per rate.
  2. Why does multiplying by a sine and summing pick out only that frequency?Multiplying by a sine and adding over whole cycles cancels every other frequency exactly and leaves a positive total for the matching one.
  3. Why does a fast wiggle look like a slow one when I sample too slowly?Because readings taken at regular instants cannot tell a rhythm from the same rhythm sped up by a whole number of cycles per reading, so the fast one is reported at a folded, slower rate.
  4. Why does sliding a filter along a signal become simple multiplication after a Fourier transform?Because a filter scales every steady rhythm without changing its rate, so the whole sliding sum collapses into one multiplication for each rhythm.
  5. What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
  6. How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.

Read alongside