Skip to content Skip to navigation

Connexions

You are here: Home » Content » Change of Basis and Change to Signal

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Change of Basis and Change to Signal

Module by: C. Sidney Burrus. E-mail the author

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Summary: One can look at the operation of a matrix times a vector as changing the basis set for the vector or as changing the vector with the same basis description.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Change of Basis

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.

Frames and Tight Frames

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.

Change of Signal

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.

References

  1. Paul R. Halmos. (1958). Finite-Dimensional Vector Spaces. Princeton, NJ: Van Nostrand.
  2. R. M. Young. (1980). An Introduction to Nonharmonic Fourier Series. New York: Academic Press.
  3. Ole Christensen. (2002). An Introduction to Frames and Riesz Bases. New York: Birkhauser.
  4. Jelena Kovacevic and Amina Chebira. (2007). Life Beyond Bases: The Advent of Frames (Part I). IEEE Signal Processing Magazine, 24, 86-104.
  5. Ingrid Daubechies. (1992). Ten Lectures on Wavelets. [Notes from the 1990 CBMS-NSF Conference on Wavelets and Applications at Lowell, MA]. Philadelphia, PA: SIAM.
  6. C. Sidney Burrus, Ramesh A. Gopinath and Haitao Guo. (1998). Introduction to Wavelets and the Wavelet Transform. Upper Saddle River, NJ: Prentice Hall.

Content actions

Give Feedback:

E-mail the module author | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks