Skip to content Skip to navigation

Connexions

You are here: Home » Content » Manifolds

Navigation

Lenses

What is a lens?

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.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS display tagshide tags

    This module is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing SocietyAs a part of collection: "Concise Signal Models"

    Comments:

    "A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."

    Click the "IEEE-SPS" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Concise Signal Models"

    Click the "UniqU content" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Manifolds

Module by: Michael Wakin. E-mail the author

Summary: This collection reviews fundamental concepts underlying the use of concise models for signal processing. Topics are presented from a geometric perspective and include low-dimensional linear, sparse, and manifold-based signal models, approximation, compression, dimensionality reduction, and Compressed Sensing.

As we will soon discuss, manifold models can provide an alternative to signal dictionaries as a framework for concise signal modeling. In this module, we present a minimal set of definitions and terminology from differential geometry and topology that serve as an introduction to manifolds. We refer the reader to the introductory and classical texts [5], [3], [2], [1] for more depth and technical precision.

General terminology

A KK-dimensional manifold MM is a topological space1 that is locally homeomorphic2 to RKRK [2]. This means that there exists an open cover of MM with each such open set mapping homeomorphically to an open ball in RKRK. Each such open set, together with its mapping to RKRK is called a chart; the set of all charts of a manifold is called an atlas.

The general definition of a manifold makes no reference to an ambient space in which the manifold lives. However, as we will often be making use of manifolds as models for sets of signals, it follows that such “signal manifolds” are actually subsets of some larger space (for example, of L2(R)L2(R) or RNRN). In general, we may think of a KK-dimensional submanifold embedded in RNRN as a nonlinear, KK-dimensional “surface” within RNRN.

Examples of manifolds

One of the simplest examples of a manifold is simply the circle in R2R2. A small, open-ended segment cut from the circle could be stretched out and associated with an open interval of the real line (see Figure 1). Hence, the circle is a 1-D manifold. (We note that at least two charts are required to form an atlas for the circle, as the entire circle itself cannot be mapped homeomorphically to an open interval in R1R1.)

Figure 1: A circle is a manifold because there exists an open cover consisting of the sets U1,U2U1,U2, which are mapped homeomorphically onto open intervals in the real line via the functions ϕ1,ϕ2ϕ1,ϕ2. (It is not necessary that the intervals intersect in RR.)
Figure 1 (circleManifold.png)

We refer the reader to [6] for an excellent overview of several manifolds with relevance to signal processing, including the rotation group SO(3)SO(3), which can be used for representing orientations of objects in 3-D space, and the Grassman manifold G(K,N)G(K,N), which represents all KK-dimensional subspaces of RNRN. (Without working through the technicalities of the definition of a manifold, it is easy to see that both types of data have a natural notion of neighborhood.)

Tangent spaces

A manifold is differentiable if, for any two charts whose open sets on MM overlap, the composition of the corresponding homeomorphisms (from RKRK in one chart to MM and back to RKRK in the other) is differentiable. (In our simple example, the circle is a differentiable manifold.)

To each point xx in a differentiable manifold, we may associate a KK-dimensional tangent space Tan x Tan x. For signal manifolds embedded in L2L2 or RNRN, it suffices to think of Tan x Tan x as the set of all directional derivatives of smooth paths on MM through xx. (Note that Tan x Tan x is a linear subspace and has its origin at 0, rather than at xx.)

Distances

One is often interested in measuring distance along a manifold. For abstract differentiable manifolds, this can be accomplished by defining a Riemannian metric on the tangent spaces. A Riemannian metric is a collection of inner products ,x,x defined at each point x∈Mx∈M. The inner product gives a measure for the “length” of a tangent, and one can then compute the length of a path on MM by integrating its tangent lengths along the path.

For differentiable manifolds embedded in RNRN, the natural metric is the Euclidean metric inherited from the ambient space. The length of a path γ:[0,1]↦Mγ:[0,1]↦M can then be computed simply using the limit

length ( γ ) = lim j → ∞ ∑ i = 1 j γ ( i / j ) - γ ( ( i - 1 ) / j ) 2 . length ( γ ) = lim j → ∞ ∑ i = 1 j γ ( i / j ) - γ ( ( i - 1 ) / j ) 2 .
(1)
The geodesic distance dM(x,y)dM(x,y) between two points x,y∈Mx,y∈M is then given by the length of the shortest path γγ on MM joining xx and yy.

Condition number

To establish a firm footing for analysis, we find it helpful assume a certain regularity to the manifold beyond mere differentiability. For this purpose, we adopt the condition number defined recently by Niyogi et al. [4].

Definition 1

[4] Let MM be a compact submanifold of RNRN. The condition number of MM is defined as 1/τ1/τ, where ττ is the largest number having the following property: The open normal bundle about MM of radius rr is imbedded in RNRN for all r<τr<τ.

The open normal bundle of radius rr at a point x∈Mx∈M is simply the collection of all vectors of length <r<r anchored at xx and with direction orthogonal to Tan x Tan x.

In addition to controlling local properties (such as curvature) of the manifold, the condition number has a global effect as well, ensuring that the manifold is self-avoiding. These notions are made precise in several lemmata, which we repeat below for completeness.

Lemma 1

[4] If MM is a submanifold of RNRN with condition number 1/τ1/τ, then the norm of the second fundamental form is bounded by 1/τ1/τ in all directions.

This implies that unit-speed geodesic paths on MM have curvature bounded by 1/τ1/τ. The second lemma concerns the twisting of tangent spaces.

Lemma 2

[4] Let MM be a submanifold of RNRN with condition number 1/τ1/τ. Let p,q∈Mp,q∈M be two points with geodesic distance given by dM(p,q)dM(p,q). Let θθ be the angle between the tangent spaces Tan p Tan p and Tan q Tan q defined by cos(θ)=minu∈ Tan pmaxv∈ Tan q|〈u,v〉|cos(θ)=minu∈ Tan pmaxv∈ Tan q|〈u,v〉|. Then cos(θ)>1-1τdM(p,q)cos(θ)>1-1τdM(p,q).

The third lemma concerns self-avoidance of MM.

Lemma 3

[4] Let MM be a submanifold of RNRN with condition number 1/τ1/τ. Let p,q∈Mp,q∈M be two points such that p-q2=dp-q2=d. Then for all d≤τ/2d≤τ/2, the geodesic distance dM(p,q)dM(p,q) is bounded by dM(p,q)≤τ-τ1-2d/τdM(p,q)≤τ-τ1-2d/τ.

From  Lemma 3 we have an immediate corollary.

Corollary 1

Let MM be a submanifold of RNRN with condition number 1/τ1/τ. Let p,q∈Mp,q∈M be two points such that p-q2=dp-q2=d. If d≤τ/2d≤τ/2, then d≥dM(p,q)-(dM(p,q))22τd≥dM(p,q)-(dM(p,q))22τ.

Footnotes

  1. A topological space is simply a set XX, together with a collection TT of subsets of XX called open sets, such that: (i) the empty set belongs to TT, (ii) XX belongs to TT, (iii) arbitrary unions of elements of TT belong to TT, and (iv) finite intersections of elements of TT belong to TT.
  2. A homeomorphism is a function between two topological spaces that is one-to-one, onto, continuous, and has a continuous inverse.

References

  1. Boothby, W. M. (2003). An Introduction to Differentiable Manifolds and Riemannian Geometry. (revised 2nd). Academic Press.
  2. Hirsch, M. W. (1976). Graduate Texts in Mathematics: Vol. 33. Differential Topology. (). Springer.
  3. Morgan, F. (1998). Riemannian Geometry: A Beginner's Guide. (2nd). A K Peters.
  4. Niyogi, P. and Smale, S. and Weinberger, S. (2004). Finding the Homology of Submanifolds with Confidence from Random Samples. [Preprint].
  5. O'Neill, B. (1997). Elementary Differential Geometry. (2nd). Harcourt Academic Press.
  6. Rahman, I. Ur and Drori, I. and Stodden, V. C. and Donoho, D. L. and Schroeder, P. (2004). Multiscale representations for manifold-valued data. [Preprint].

Content actions

Download module as:

PDF | More downloads ...

Add 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