Intrinsic dimension
Encyclopedia
In signal processing
of multidimensional signals, for example in computer vision
, the intrinsic dimension of the signal describes how many variables are needed to represent the signal. For a signal of N variables, its intrinsic dimension M satisfies 0 ≤ M ≤ N.
Usually the intrinsic dimension of a signal relates to variables defined in a Cartesian coordinate system. In general, however, it is also possible to describe the concept for non-Cartesian coordinates, for example, using polar coordinates.
for some one-variable function g which is not constant. This means that f varies, in accordance to g, with the first variable or along the first coordinate. On the other hand, f is constant with respect to the second variable or along the second coordinate. It is only necessary to know the value of one, namely the first, variable in order to determine the value of f. Hence, it is a two-variable function but its intrinsic dimension is one.
A slightly more complicated example is
f is still intrinsic one-dimensional, which can be seen by making a variable transformation
which gives
Since the variation in f can be described by the single variable y1 its intrinsic dimension is one.
For the case that f is constant, its intrinsic dimension is zero since no variable is needed to describe variation. For the general case, when the intrinsic dimension of the two-variable function f is neither zero or one, it is two.
In the literature, functions which are of intrinsic dimension zero, one, or two are sometimes referred to as i0D, i1D or i2D , respectively.
If for some M-variable function g and M × N matrix A is it the case that
then the intrinsic dimension of f is M.
The intrinsic dimension is a characterization of f, it is not an unambiguous characterization of g nor of A. If the above relation is satisfied for some f, g, and A, it must also be satisfied for the same f and g′ and A′ given by
where B is a non-singular M × M matrix, since
for all x in R2. If F is the Fourier transform of f (both are two-variable functions) it must be the case that
Here G is the Fourier transform of g (both are one-variable functions), δ is the Dirac impulse function and m is a normalized vector in R2 perpendicular to n. This means that F vanishes everywhere except on a line which passes through the origin of the frequency domain and is parallel to m. Along this line F varies according to G.
Its Fourier transform F can then be described as follows:
is applied to the coordinates of the N-variable function f to produce the M variables which are necessary to represent every value of f. This means that f is constant along lines, planes, or hyperplanes, depending on N and M.
In a general case, f has intrinsic dimension M is there exist M functions a1, a2, ..., aM and an M-variable function g such that
A simple example is transforming a 2-variable function f to polar coordinates:
For the general case, a simple description of either the point sets for which f is constant or its Fourier transform is usually not possible.
and image processing
and captures the idea of local image regions which contain lines or edges. The analysis of such regions has a long history, but it was not until a more formal and theoretical treatment of such operations began that the concept of intrinsic dimension was established, even though the name has varied.
For example, the concept which here is referred to as a image neighborhood of intrinsic dimension 1 or i1D neighborhood is called 1-dimensional by Knutsson (1982), linear symmetric by Bigün & Granlund (1987) and simple neighborhood in Granlund & Knutsson (1995).
The term intrinsic dimension was coined by Bennett (1965).
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
of multidimensional signals, for example in computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
, the intrinsic dimension of the signal describes how many variables are needed to represent the signal. For a signal of N variables, its intrinsic dimension M satisfies 0 ≤ M ≤ N.
Usually the intrinsic dimension of a signal relates to variables defined in a Cartesian coordinate system. In general, however, it is also possible to describe the concept for non-Cartesian coordinates, for example, using polar coordinates.
Example
Let f(x1, x2) be a two-variable function (or signal) which is of the form- f(x1,x2) = g(x1)
for some one-variable function g which is not constant. This means that f varies, in accordance to g, with the first variable or along the first coordinate. On the other hand, f is constant with respect to the second variable or along the second coordinate. It is only necessary to know the value of one, namely the first, variable in order to determine the value of f. Hence, it is a two-variable function but its intrinsic dimension is one.
A slightly more complicated example is
- f(x1,x2) = g(x1 + x2)
f is still intrinsic one-dimensional, which can be seen by making a variable transformation
- x1 + x2 = y1
- x1 - x2 = y2
which gives
- f(y1,y2) = g(y1)
Since the variation in f can be described by the single variable y1 its intrinsic dimension is one.
For the case that f is constant, its intrinsic dimension is zero since no variable is needed to describe variation. For the general case, when the intrinsic dimension of the two-variable function f is neither zero or one, it is two.
In the literature, functions which are of intrinsic dimension zero, one, or two are sometimes referred to as i0D, i1D or i2D , respectively.
Formal definition
For an N-variable function f, the set of variables can be represented as an N-dimensional vector x:- f=f(x) where x=(x1, x2, ..., xN)
If for some M-variable function g and M × N matrix A is it the case that
- for all x; f(x)=g(Ax),
- M is the smallest number for which the above relation between f and g can be found,
then the intrinsic dimension of f is M.
The intrinsic dimension is a characterization of f, it is not an unambiguous characterization of g nor of A. If the above relation is satisfied for some f, g, and A, it must also be satisfied for the same f and g′ and A′ given by
- g′(y)=g(By)
- A′=B-1 A
where B is a non-singular M × M matrix, since
- f(x)=g′(A′x)=g(BA′x)=g(Ax)
The Fourier transform of functions of low intrinsic dimension
An N variable function which has intrinsic dimension M < N has a characteristic Fourier transform. Intuitively, since this type of function is constant along one or several dimensions its Fourier transform must appear like an impulse (the Fourier transform of a constant) along the same dimension in the frequency space.A simple example
Let f be a two-variable function which is i1D. This means that there exists a normalized vector n in R2 and a one-variable function g such that- f(x) = g(nTx)
for all x in R2. If F is the Fourier transform of f (both are two-variable functions) it must be the case that
- F(u)= G(nTu) · δ(mTu)
Here G is the Fourier transform of g (both are one-variable functions), δ is the Dirac impulse function and m is a normalized vector in R2 perpendicular to n. This means that F vanishes everywhere except on a line which passes through the origin of the frequency domain and is parallel to m. Along this line F varies according to G.
The general case
Let f be an N-variable function which has intrinsic dimension M, that is, there exists an M-variable function g and M × N matrix A such that- f(x)=g(Ax) for all x.
Its Fourier transform F can then be described as follows:
- F vanishes everywhere except for a subspace of dimension M
- The subspace M is spanned by the rows of the matrix A
- In the subspace, F varies according to G the Fourier transform of g
Generalizations
The type of intrinsic dimension described above assumes that a linear transformationLinear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...
is applied to the coordinates of the N-variable function f to produce the M variables which are necessary to represent every value of f. This means that f is constant along lines, planes, or hyperplanes, depending on N and M.
In a general case, f has intrinsic dimension M is there exist M functions a1, a2, ..., aM and an M-variable function g such that
- f(x) = g(a1(x),a2(x),...,aM(x)) for all x
- M is the smallest number of functions which allows the above transformation
A simple example is transforming a 2-variable function f to polar coordinates:
- f(x1,x2) = g((x12 + x22)1/2), f is i1D and is constant along any circle centered at the origin
- f(x1,x2) = g(arctan(x2 / x1)), f is i1D and is constant along all rays from the origin
For the general case, a simple description of either the point sets for which f is constant or its Fourier transform is usually not possible.
Applications and history
The case of a two-variable signal which is i1D appears frequently in computer visionComputer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
and image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
and captures the idea of local image regions which contain lines or edges. The analysis of such regions has a long history, but it was not until a more formal and theoretical treatment of such operations began that the concept of intrinsic dimension was established, even though the name has varied.
For example, the concept which here is referred to as a image neighborhood of intrinsic dimension 1 or i1D neighborhood is called 1-dimensional by Knutsson (1982), linear symmetric by Bigün & Granlund (1987) and simple neighborhood in Granlund & Knutsson (1995).
The term intrinsic dimension was coined by Bennett (1965).
See also
- DimensionDimensionIn physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
- Fractal dimensionFractal dimensionIn fractal geometry, the fractal dimension, D, is a statistical quantity that gives an indication of how completely a fractal appears to fill space, as one zooms down to finer and finer scales. There are many specific definitions of fractal dimension. The most important theoretical fractal...
- Topological dimension
- Hausdorff dimensionHausdorff dimensionthumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...