## Signal Reconstruction from Projections

We now know how to project a signal onto other signals. We now need
to learn how to reconstruct a signal
from its projections
onto different vectors
,
. This
will give us the *inverse DFT* operation (or the inverse of
whatever transform we are working with).

As a simple example, consider the projection of a signal
onto the
rectilinear *coordinate axes* of . The coordinates of the
projection onto the 0th coordinate axis are simply
.
The projection along coordinate axis has coordinates
, and so on. The original signal is then clearly
the *vector sum* of its projections onto the coordinate axes:

To make sure the previous paragraph is understood, let's look at the details for the case . We want to project an arbitrary two-sample signal onto the coordinate axes in 2D. A coordinate axis can be generated by multiplying any nonzero vector by scalars. The horizontal axis can be represented by any vector of the form , while the vertical axis can be represented by any vector of the form , . For maximum simplicity, let's choose

The projection of onto is, by definition,

Similarly, the projection of onto is

The *reconstruction* of from its projections onto the coordinate
axes is then the *vector sum of the projections*:

The projection of a vector onto its coordinate axes is in some sense
trivial because the very meaning of the *coordinates* is that they are
scalars to be applied to the *coordinate vectors*
in
order to form an arbitrary vector
as a *linear combination*
of the coordinate vectors:

*orthogonal*. Since they are also unit length, , we say that the coordinate vectors are

*orthonormal*.

### Changing Coordinates

What's more interesting is when we project a signal onto a set
of vectors *other than* the coordinate set. This can be viewed
as a *change of coordinates* in . In the case of the DFT,
the new vectors will be chosen to be *sampled complex sinusoids*.

#### An Example of Changing Coordinates in 2D

As a simple example, let's pick the following pair of new coordinate vectors in 2D:

These happen to be the DFT sinusoids for having frequencies
(``dc'') and (half the sampling rate). (The sampled complex
sinusoids of the DFT reduce to real numbers only for and .) We
already showed in an earlier example that these vectors are *orthogonal*. However, they are not orthonormal since the norm is
in each case. Let's try projecting onto these vectors and
seeing if we can reconstruct by summing the projections.

The projection of onto is, by
definition,^{5.12}

Similarly, the projection of onto is

The sum of these projections is then

It worked!

### Projection onto Linearly Dependent Vectors

Now consider another example:

The projections of onto these vectors are

The sum of the projections is

Something went wrong, but what? It turns out that a set of
vectors can be used to reconstruct an arbitrary vector in from
its projections only if they are *linearly independent*. In
general, a set of vectors is linearly independent if none of them can
be expressed as a linear combination of the others in the set. What
this means intuitively is that they must ``point in different
directions'' in -space. In this example
so that they
lie along the *same line* in -space. As a result, they are
linearly *dependent*: one is a linear combination of the other
(
).

### Projection onto Non-Orthogonal Vectors

Consider this example:

These point in different directions, but they are not orthogonal. What happens now? The projections are

The sum of the projections is

So, even though the vectors are linearly independent, the sum of
projections onto them does not reconstruct the original vector. Since the
sum of projections worked in the orthogonal case, and since orthogonality
implies linear independence, we might conjecture at this point that the sum
of projections onto a set of vectors will reconstruct the original
vector only when the vector set is *orthogonal*, and this is true,
as we will show.

It turns out that one can apply an orthogonalizing process, called
*Gram-Schmidt orthogonalization* to any linearly independent
vectors in so as to form an orthogonal set which will always
work. This will be derived in Section 5.10.4.

Obviously, there must be at least vectors in the set. Otherwise,
there would be too few *degrees of freedom* to represent an
arbitrary
. That is, given the coordinates
of (which are scale factors relative to
the coordinate vectors
in ), we have to find at least
coefficients of projection (which we may think of as coordinates
relative to new coordinate vectors ). If we compute only
coefficients, then we would be mapping a set of complex numbers to
numbers. Such a mapping cannot be invertible in general. It
also turns out linearly independent vectors is always sufficient.
The next section will summarize the general results along these lines.

### General Conditions

This section summarizes and extends the above derivations in a more
formal manner (following portions of chapter 4 of
). In
particular, we establish that the sum of projections of
onto vectors
will give back the original vector
whenever the set
is an *orthogonal
basis* for .

**Definition: **A set of vectors is said to form a *vector space* if, given
any two members and from the set, the vectors
and are also in the set, where
is any
scalar.

**Definition: **The set of all -dimensional complex vectors is denoted
. That is, consists of all vectors
defined as a list of complex numbers
.

**Theorem: ** is a *vector space* under elementwise addition and
multiplication by complex scalars.

*Proof: *This is a special case of the following more general theorem.

**Theorem: **Let be an integer greater than 0. Then the set of all
linear combinations of vectors from forms a vector space
under elementwise addition and multiplication by complex scalars.

*Proof: *Let the original set of vectors be denoted
.
Form

which is yet another linear combination of the original vectors (since complex numbers are closed under addition). Since we have shown that scalar multiples and vector sums of linear combinations of the original vectors from are also linear combinations of those same original vectors from , we have that the defining properties of a vector space are satisfied.

Note that the closure of vector addition and scalar multiplication are ``inherited'' from the closure of complex numbers under addition and multiplication.

**Corollary: **The set of all linear combinations of *real* vectors
, using real scalars
, form a
vector space.

**Definition: **The set of all linear combinations of a set of
*complex* vectors from , using complex scalars, is called a
*complex vector space* of dimension .

**Definition: **The set of all linear combinations of a set of *real* vectors
from , using real scalars, is called a *real vector
space* of dimension .

**Definition: **If a vector space consists of the set of all linear
combinations of a finite set of vectors
, then
those vectors are said to *span* the space.

**Example: **The *coordinate vectors* in span since every vector
can be expressed as a linear combination of the coordinate vectors
as

**Definition: **The vector space spanned by a set of vectors from
is called an -dimensional *subspace* of .

**Definition: **A vector
is said to be *linearly dependent* on
a set of vectors
,
, if
can be expressed as a linear combination of those vectors.

Thus, is linearly dependent on if there exist scalars such that . Note that the zero vector is linearly dependent on every collection of vectors.

**Theorem: **(i) If
span a vector space, and if one of them,
say , is linearly dependent on the others, then the same vector
space is spanned by the set obtained by omitting from the
original set. (ii) If
span a vector space,
we can always select from these a linearly independent set that spans
the same space.

*Proof: *Any in the space can be represented as a linear combination of the
vectors
. By expressing as a linear
combination of the other vectors in the set, the linear combination
for becomes a linear combination of vectors other than .
Thus, can be eliminated from the set, proving (i). To prove
(ii), we can define a procedure for forming the required subset of the
original vectors: First, assign to the set. Next, check to
see if and are linearly dependent. If so (*i.e.*,
is a scalar times ), then discard ; otherwise
assign it also to the new set. Next, check to see if is
linearly dependent on the vectors in the new set. If it is (*i.e.*,
is some linear combination of and ) then
discard it; otherwise assign it also to the new set. When this
procedure terminates after processing , the new set will
contain only linearly independent vectors which span the original
space.

**Definition: **A set of linearly independent vectors which spans a vector space
is called a *basis* for that vector space.

**Definition: **The set of coordinate vectors in
is called the *natural basis* for , where the th basis vector
is

**Theorem: **The linear combination expressing a vector in terms of basis vectors
for a vector space is *unique*.

*Proof: *Suppose a vector
can be expressed in two different ways as
a linear combination of basis vectors
:

where for at least one value of . Subtracting the two representations gives

Note that while the linear combination relative to a particular basis is
unique, the choice of basis vectors is not. For example, given any basis
set in , a new basis can be formed by *rotating* all vectors in
by the same angle. In this way, an infinite number of basis sets can
be generated.

As we will soon show, the DFT can be viewed as a *change of
coordinates* from coordinates relative to the *natural basis* in ,
, to coordinates relative to the *sinusoidal
basis* for ,
, where
. The sinusoidal basis set for consists of length
sampled complex sinusoids at frequencies
. Any scaling of these vectors in by complex
scale factors could also be chosen as the sinusoidal basis (*i.e.*, any
nonzero amplitude and any phase will do). However, for simplicity, we will
only use unit-amplitude, zero-phase complex sinusoids as the Fourier
``frequency-domain'' basis set. To summarize this paragraph, the
time-domain samples of a signal are its coordinates relative to the natural
basis for , while its spectral coefficients are the coordinates of the
signal relative to the sinusoidal basis for .

**Theorem: **Any two bases of a vector space contain the same number of vectors.

*Proof: *Left as an exercise (or see [47]).

**Definition: **The number of vectors in a basis for a particular space is called
the *dimension* of the space. If the dimension is , the space is
said to be an * dimensional space*, or *-space*.

In this book, we will only consider finite-dimensional vector spaces in any detail. However, the discrete-time Fourier transform (DTFT) and Fourier transform (FT) both require infinite-dimensional basis sets, because there is an infinite number of points in both the time and frequency domains. (See Appendix B for details regarding the FT and DTFT.)

### Signal/Vector Reconstruction from Projections

We now arrive finally at the main desired result for this section:

**Theorem: **The projections of any vector
onto any orthogonal basis set
for can be summed to reconstruct exactly.

*Proof: *Let
denote any orthogonal basis set for .
Then since is in the space spanned by these vectors, we have

for some (unique) scalars . The projection of onto is equal to

### Gram-Schmidt Orthogonalization

Recall from the end of §5.10 above that an
*orthonormal* set of vectors is a set of *unit-length*
vectors that are mutually *orthogonal*. In other words,
orthonormal vector set is just an orthogonal vector set in which each
vector has been normalized to unit length
.

**Theorem: **Given a set of linearly independent vectors
from , we can construct an
*orthonormal* set
which are linear
combinations of the original set and which span the same space.

*Proof: *We prove the theorem by constructing the desired orthonormal
set
sequentially from the original set .
This procedure is known as *Gram-Schmidt orthogonalization*.

First, note that for all , since is linearly dependent on every vector. Therefore, .

- Set .
- Define
as minus the projection of
onto
:
- Set
(
*i.e.*, normalize the result of the preceding step). - Define
as minus the projection of
onto
and
:
- Normalize: .
- Continue this process until
has been defined.

The Gram-Schmidt orthogonalization procedure will construct an
orthonormal basis from any set of linearly independent vectors.
Obviously, by skipping the normalization step, we could also form
simply an orthogonal basis. The key ingredient of this procedure is
that each new basis vector is obtained by subtracting out the
projection of the next linearly independent vector onto the vectors
accepted so far into the set. We may say that each new linearly
independent vector is projected onto the *subspace*
spanned by the vectors
, and any nonzero
projection in that subspace is subtracted out of to make the
new vector orthogonal to the entire subspace. In other words, we
retain only that portion of each new vector which ``points
along'' a new dimension. The first direction is arbitrary and is
determined by whatever vector we choose first ( here). The
next vector is forced to be orthogonal to the first. The second is
forced to be orthogonal to the first two (and thus to the 2D subspace
spanned by them), and so on.

This chapter can be considered an introduction to some
important concepts of *linear algebra*. The student is invited to
pursue further reading in any textbook on linear algebra, such as
[47].^{5.13}

Matlab/Octave examples related to this chapter appear in Appendix I.

**Next Section:**

Signal Projection Problems

**Previous Section:**

The Inner Product