Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Introduction to Compressive Sensing » Bases and frames

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Bases and frames

Module by: Marco F. Duarte, Mark A. Davenport. E-mail the authors

Summary: This module provides an overview of bases and frames in finite-dimensional Hilbert spaces.

A set Ψ={ψi}iIΨ={ψi}iI is called a basis for a finite-dimensional vector space VV if the vectors in the set span VV and are linearly independent. This implies that each vector in the space can be represented as a linear combination of this (smaller, except in the trivial case) set of basis vectors in a unique fashion. Furthermore, the coefficients of this linear combination can be found by the inner product of the signal and a dual set of vectors. In discrete settings, we will only consider real finite-dimensional Hilbert spaces where V=RNV=RN and I={1,...,N}I={1,...,N}.

Mathematically, any signal xRNxRN may be expressed as,

x = i I a i ψ i ˜ , x = i I a i ψ i ˜ ,
(1)

where our coefficients are computed as ai=x,ψiai=x,ψi and {ψi˜}iI{ψi˜}iI are the vectors that constitute our dual basis. Another way to denote our basis and its dual is by how they operate on xx. Here, we call our dual basis Ψ˜Ψ˜ our synthesis basis (used to reconstruct our signal by Equation 1) and ΨΨ is our analysis basis.

An orthonormal basis (ONB) is defined as a set of vectors Ψ={ψi}iIΨ={ψi}iI that form a basis and whose elements are orthogonal and unit norm. In other words, ψi,ψj=0ψi,ψj=0 if ijij and one otherwise. In the case of an ONB, the synthesis basis is simply the Hermitian adjoint of analysis basis (Ψ˜=ΨTΨ˜=ΨT).

It is often useful to generalize the concept of a basis to allow for sets of possibly linearly dependent vectors, resulting in what is known as a frame. More formally, a frame is a set of vectors {Ψi}i=1n{Ψi}i=1n in RdRd, d<nd<n corresponding to a matrix ΨRd×nΨRd×n, such that for all vectors xRdxRd,

A x 2 2 Ψ T x 2 2 B x 2 2 A x 2 2 Ψ T x 2 2 B x 2 2
(2)

with 0<AB<0<AB<. Note that the condition A>0A>0 implies that the rows of ΨΨ must be linearly independent. When AA is chosen as the largest possible value and BB as the smallest for these inequalities to hold, then we call them the (optimal) frame bounds. If AA and BB can be chosen as A=BA=B, then the frame is called AA-tight, and if A=B=1A=B=1, then ΨΨ is a Parseval frame. A frame is called equal-norm, if there exists some λ>0λ>0 such that Ψi2=λΨi2=λ for all i=1,...,Ni=1,...,N, and it is unit-norm if λ=1λ=1. Note also that while the concept of a frame is very general and can be defined in infinite-dimensional spaces, in the case where ΨΨ is a d×Nd×N matrix AA and BB simply correspond to the smallest and largest eigenvalues of ΨΨTΨΨT, respectively.

Frames can provide richer representations of data due to their redundancy: for a given signal xx, there exist infinitely many coefficient vectors αα such that x=Ψαx=Ψα. In particular, each choice of a dual frame Ψ˜Ψ˜ provides a different choice of a coefficient vector αα. More formally, any frame satisfying

Ψ Ψ ˜ T = Ψ ˜ Ψ T = I Ψ Ψ ˜ T = Ψ ˜ Ψ T = I
(3)

is called an (alternate) dual frame. The particular choice Ψ˜=(ΨΨT)-1ΨΨ˜=(ΨΨT)-1Ψ is referred to as the canonical dual frame. It is also known as the Moore-Penrose pseudoinverse. Note that since A>0A>0 requires ΨΨ to have linearly independent rows, we ensure that ΨΨTΨΨT is invertible, so that Ψ˜Ψ˜ is well-defined. Thus, one way to obtain a set of feasible coefficients is via

α d = Ψ T ( Ψ Ψ T ) - 1 x . α d = Ψ T ( Ψ Ψ T ) - 1 x .
(4)

One can show that this sequence is the smallest coefficient sequence in 22 norm, i.e., αd2α2αd2α2 for all αα such that x=Ψαx=Ψα.

Finally, note that in the sparse approximation literature, it is also common for a basis or frame to be referred to as a dictionary or overcomplete dictionary respectively, with the dictionary elements being called atoms.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

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

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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

Module to:

My Favorites (?)

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

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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