Local tangent space alignment

Last updated

Local tangent space alignment (LTSA) [1] is a method for manifold learning, which can efficiently learn a nonlinear embedding into low-dimensional coordinates from high-dimensional data, and can also reconstruct high-dimensional coordinates from embedding coordinates. It is based on the intuition that when a manifold is correctly unfolded, all of the tangent hyperplanes to the manifold will become aligned. It begins by computing the k-nearest neighbors of every point. It computes the tangent space at every point by computing the d-first principal components in each local neighborhood. It then optimizes to find an embedding that aligns the tangent spaces, but it ignores the label information conveyed by data samples, and thus can not be used for classification directly.

Contents

See also

Related Research Articles

<span class="mw-page-title-main">Differential topology</span> Branch of mathematics

In mathematics, differential topology is the field dealing with the topological properties and smooth properties of smooth manifolds. In this sense differential topology is distinct from the closely related field of differential geometry, which concerns the geometric properties of smooth manifolds, including notions of size, distance, and rigid shape. By comparison differential topology is concerned with coarser properties, such as the number of holes in a manifold, its homotopy type, or the structure of its diffeomorphism group. Because many of these coarser properties may be captured algebraically, differential topology has strong links to algebraic topology.

The Nash embedding theorems, named after John Forbes Nash Jr., state that every Riemannian manifold can be isometrically embedded into some Euclidean space. Isometric means preserving the length of every path. For instance, bending but neither stretching nor tearing a page of paper gives an isometric embedding of the page into Euclidean space because curves drawn on the page retain the same arclength however the page is bent.

<span class="mw-page-title-main">Curvature</span> Mathematical measure of how much a curve or surface deviates from flatness

In mathematics, curvature is any of several strongly related concepts in geometry. Intuitively, the curvature is the amount by which a curve deviates from being a straight line, or a surface deviates from being a plane.

<span class="mw-page-title-main">Isometry</span> Distance-preserving mathematical transformation

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure".

<span class="mw-page-title-main">Nonlinear dimensionality reduction</span> Summary of algorithms for nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

<span class="mw-page-title-main">Complex manifold</span> Manifold

In differential geometry and complex geometry, a complex manifold is a manifold with an atlas of charts to the open unit disc in , such that the transition maps are holomorphic.

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension. Working in high-dimensional spaces can be undesirable for many reasons; raw data are often sparse as a consequence of the curse of dimensionality, and analyzing the data is usually computationally intractable. Dimensionality reduction is common in fields that deal with large numbers of observations and/or large numbers of variables, such as signal processing, speech recognition, neuroinformatics, and bioinformatics.

<span class="mw-page-title-main">Affine connection</span> Construct allowing differentiation of tangent vector fields of manifolds

In differential geometry, an affine connection is a geometric object on a smooth manifold which connects nearby tangent spaces, so it permits tangent vector fields to be differentiated as if they were functions on the manifold with values in a fixed vector space. Connections are among the simplest methods of defining differentiation of the sections of vector bundles.

<span class="mw-page-title-main">Holonomy</span> Concept in differential geometry

In differential geometry, the holonomy of a connection on a smooth manifold is a general geometrical consequence of the curvature of the connection measuring the extent to which parallel transport around closed loops fails to preserve the geometrical data being transported. For flat connections, the associated holonomy is a type of monodromy and is an inherently global notion. For curved connections, holonomy has nontrivial local and global features.

<span class="mw-page-title-main">3-manifold</span> Mathematical space

In mathematics, a 3-manifold is a topological space that locally looks like a three-dimensional Euclidean space. A 3-manifold can be thought of as a possible shape of the universe. Just as a sphere looks like a plane to a small enough observer, all 3-manifolds look like our universe does to a small enough observer. This is made more precise in the definition below.

Maximum Variance Unfolding (MVU), also known as Semidefinite Embedding (SDE), is an algorithm in computer science that uses semidefinite programming to perform non-linear dimensionality reduction of high-dimensional vectorial input data.

<span class="mw-page-title-main">Manifold</span> Topological space that locally resembles Euclidean space

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an -dimensional manifold, or -manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of -dimensional Euclidean space.

<span class="mw-page-title-main">Differentiable manifold</span> Manifold upon which it is possible to perform calculus

In mathematics, a differentiable manifold is a type of manifold that is locally similar enough to a vector space to allow one to apply calculus. Any manifold can be described by a collection of charts (atlas). One may then apply ideas from calculus while working within the individual charts, since each chart lies within a vector space to which the usual rules of calculus apply. If the charts are suitably compatible, then computations done in one chart are valid in any other differentiable chart.

In mathematics, a differentiable manifold of dimension n is called parallelizable if there exist smooth vector fields

<span class="mw-page-title-main">Immersion (mathematics)</span> Differentiable function whose derivative is everywhere injective

In mathematics, an immersion is a differentiable function between differentiable manifolds whose differential is everywhere injective. Explicitly, f : MN is an immersion if

In surgery theory, a branch of mathematics, the stable normal bundle of a differentiable manifold is an invariant which encodes the stable normal data. There are analogs for generalizations of manifold, notably PL-manifolds and topological manifolds. There is also an analogue in homotopy theory for Poincaré spaces, the Spivak spherical fibration, named after Michael Spivak.

In mathematics, specifically geometry and topology, the classification of manifolds is a basic question, about which much is known, and many open questions remain.

Isomap is a nonlinear dimensionality reduction method. It is one of several widely used low-dimensional embedding methods. Isomap is used for computing a quasi-isometric, low-dimensional embedding of a set of high-dimensional data points. The algorithm provides a simple method for estimating the intrinsic geometry of a data manifold based on a rough estimate of each data point’s neighbors on the manifold. Isomap is highly efficient and generally applicable to a broad range of data sources and dimensionalities.

<span class="mw-page-title-main">Differential geometry of surfaces</span> The mathematics of smooth surfaces

In mathematics, the differential geometry of surfaces deals with the differential geometry of smooth surfaces with various additional structures, most often, a Riemannian metric. Surfaces have been extensively studied from various perspectives: extrinsically, relating to their embedding in Euclidean space and intrinsically, reflecting their properties determined solely by the distance within the surface as measured along curves on the surface. One of the fundamental concepts investigated is the Gaussian curvature, first studied in depth by Carl Friedrich Gauss, who showed that curvature was an intrinsic property of a surface, independent of its isometric embedding in Euclidean space.

Manifold alignment is a class of machine learning algorithms that produce projections between sets of data, given that the original data sets lie on a common manifold. The concept was first introduced as such by Ham, Lee, and Saul in 2003, adding a manifold constraint to the general problem of correlating sets of high-dimensional vectors.

References

  1. Zhang, Zhenyue; Hongyuan Zha (2004). "Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment". SIAM Journal on Scientific Computing. 26 (1): 313–338. CiteSeerX   10.1.1.211.9957 . doi:10.1137/s1064827502419154.

Further reading