The operation given in
(Reference) can be viewed
as xx being a signal vector and with
bb being a vector whose entries are inner
products of xx and the rows of
AA . In other words, the elements of
bb are the projection coefficients of
xx onto the coordinates given by the rows of
AA . The multiplication of a signal by this
operator decomposes it and gives the coefficients of the decomposition.
An alternative view has xx being a set of weights
so that bb is a weighted sum of the columns of
AA . In other words,
bb will lie in the space spanned by the columns
of AA at a location determined by
xx . This view is a composition of a signal from a
set of weights which could have been obtained from a previous decomposition.
These two views of the operation as a decomposition of a signal or the
recomposition of the signal to or from a different basis system are extremely
valuable in signal analysis. The ideas of orthogonality, rank, adjoint, etc.
are all important here. The dimensions of the domain and range of the
operators may or may not be the same. The matrices may or may not be square
and may or may not be of full rank
[1].
A set of linearly independent vectors
x
n
x
n
forms a basis for a vector space if every vector
xx in the space can be uniquely written
x
=
∑
n
a
n
x
n
x
=
∑
n
a
n
x
n
(1)
and the dual basis vectors
x
˜
n
x
˜
n
allow a simple inner product to calculate the expansion coefficients as
a
n
=
<
x
,
x
˜
n
>
=
x
T
x
˜
n
a
n
=
<
x
,
x
˜
n
>
=
x
T
x
˜
n
(2)
Equation 1 can be
written as a matrix operation
F
a
=
x
F
a
=
x
(3)
where the columns of
FF are the basis vectors and the vector
aa
has the expansion coefficients
a
n
a
n
as entries. Equation
Equation 2 can also be
written as a matrix operation
F
˜
x
=
a
F
˜
x
=
a
(4)
which has the dual basis vectors as rows of
F
˜
F
˜
.
From
Equation 3 and
Equation 4, we have
F
F
˜
x
=
x
F
F
˜
x
=
x
(5)
Since this is true for all
x
x
,
F
F
˜
=
I
F
F
˜
=
I
(6)
or
F
˜
=
F
−
1
F
˜
=
F
−
1
(7)
which states the dual basis vectors are the rows of the inverse of the matrix
whose columns are the basis vectors (and vice versa). When the vector set is a
basis,
FF is necessarily square and from
Equation 3 and
Equation 4, one can show
F
F
˜
=
F
˜
F
.
F
F
˜
=
F
˜
F
.
(8)
Because this system requires two basis sets, the expansion basis and the dual
basis, it is called biorthogonal.
If the basis vectors are not only independent but orthonormal, the basis set
is its own dual and the inverse of F is simply its transpose.
F
˜
=
F
T
F
˜
=
F
T
(9)
When done in Hilbert spaces, this decomposition is sometimes called an
abstract Fourier expansion.
If a set of vectors spans a space but are not linearly independent,
Equation 1 still holds but
it is no longer unique. The set of vectors is called a
frame for the space
[2][3][4][5] [link]
and are redundant in the sense there are more than necessary for a basis. The
finite dimensional matrix version of this case would have FF
in Equation 3 with more
columns than rows but with full row rank. The dual frame vectors are also not
unique but a set can be found such that
Equation 4 and, therefore,
Equation 5 holds (but
Equation 8 does not). A
set of dual frame vectors could be found by adding a set of arbitrary but
independent rows to F until it is square, inverting it, then
taking the first
N
N
columns to form
F
˜
F
˜
whose rows will be a set of dual frame vectors. This method of construction
shows the non-uniqueness of the dual frame vectors. This non-uniqueness is
often resolved by minimizing some other parameter of the system
[5].
If the matrix operations are implementing a frame decomposition and the rows
of F are orthonormal,
F
˜
=
F
T
F
˜
=
F
T
and the vector set is called a tight frame
[2][5].
If the frame vectors are normalized to
||
x
k
||
=
1
||
x
k
||
=
1
,
the decomposition in
Equation 1 becomes
x
=
1
A
∑
n
〈
x
,
x
˜
n
〉
x
n
x
=
1
A
∑
n
〈
x
,
x
˜
n
〉
x
n
(10)
where the constant
A
A
is a measure of the redundancy of the expansion which has more expansion
vectors than necessary
[5].
The matrix form is
x
=
1
A
F
F
T
x
x
=
1
A
F
F
T
x
(11)
where
F
F
has more columns than rows. Examples can be found in
[6].
Frames and tight frames don't seem to be particularly useful in finite
dimensions, but become important in infinite dimensional signal analysis,
especially using the new idea of wavelet basis functions
[5].
In an infinite dimensional vector space, if basis vectors are chosen such that
all expansion converge very rapidly, the basis is called an
unconditional basis and is near optimal for a wide
class of signal representation and processing problems. This is discussed by
Donoho in [link].
Still another view of a matrix operator being a change of basis can be
developed using the eigenvectors (or singular values) of an operator as the
basis vectors. Then a signal can decomposed into its eigenvector components
which are then simply multiplied by the scalar eigenvalues to accomplish the
same task as a general matrix multiplication. This is an interesting idea but
will not be developed here.
If both xx and bb
are considered to be signals in the same coordinate or basis system, the
matrix operator AA is generally square. It may or
may not be of full rank and it may or may not have a variety of other
properties, but both xx and
bb are viewed in the same coordinate system.
One method of understanding and generating matrices of this sort is to
construct them as a product of first a decomposition operator, then a
modification operator in the new basis system, followed by a recomposition
operator. For example, one could first multiply a signal by the DFT operator
which will change it into the frequency domain. One (or more) of the frequency
coefficients could be removed (set to zero) and the remainder multiplied by
the inverse DFT operator to give a signal back in the time domain but changed
by having a frequency component removed. That is a form of signal filtering.
It would be instructive for the reader to make sense out of the cryptic
statement ``the DFT diagonalizes the cyclic convolution matrix" to add to the
ideas in this note.
-
Paul R. Halmos. (1958). Finite-Dimensional Vector Spaces. Princeton, NJ: Van Nostrand.
-
R. M. Young. (1980). An Introduction to Nonharmonic Fourier Series. New York: Academic Press.
-
Ole Christensen. (2002). An Introduction to Frames and Riesz Bases. New York: Birkhauser.
-
Jelena Kovacevic and Amina Chebira. (2007). Life Beyond Bases: The Advent of Frames (Part I). IEEE Signal Processing Magazine, 24, 86-104.
-
Ingrid Daubechies. (1992). Ten Lectures on Wavelets. [Notes from the 1990 CBMS-NSF Conference on Wavelets and Applications at Lowell, MA]. Philadelphia, PA: SIAM.
-
C. Sidney Burrus, Ramesh A. Gopinath and Haitao Guo. (1998). Introduction to Wavelets and the Wavelet Transform. Upper Saddle River, NJ: Prentice Hall.
