clusterv (version 1.1.1)

JL.predict.dim: Dimension of the subspace or the distortion predicted according to the Johnson Lindenstrauss lemma

Description

Functions to compute the dimension of the subspace or the distortion predicted by the Johnson Lindenstrauss lemma.

Usage

JL.predict.dim(n, epsilon = 0.5)
JL.predict.dim.multiple(n, epsilon = 0.5, t = 10)
JL.predict.distortion(n, dim = 10)

Value

the corresponding dimension of the subspace or the \(\epsilon\) value of the \(1+\epsilon\) max. expansion (distortion)

Arguments

n

cardinality of the data

epsilon

distortion (0 < epsilon <= 0.5)

t

number of multiple projections

dim

dimensionality of the projected subspace

Author

Giorgio Valentini

Details

JL.predict.dim predicts the dimension of random projection we need to obtain a given distortion according to JL lemma: $$ d = 4 * \frac{\log{n}}{ \epsilon^2}$$ where \(d\) is the dimension of the random projection, \(n\) the cardinality of the data and \(1+\epsilon\) the theoretical distortion (maximum expansion) induced by the randomized projection into the d-dimensional subspace.

JL.predict.dim.multiple predicts the dimension of random projection we need to obtain a given distortion according to JL lemma when t multiple projections are performed: $$ d = 4 * \frac{\log{n} + \log{t}}{ \epsilon^2}$$ where \(d\) is the dimension of the random projection, \(n\) the cardinality of the data and \(1+\epsilon\) the theoretical distortion (maximum expansion) induced by the randomized projection into the d-dimensional subspace.

JL.predict.distortion predicts the distortion of a random projection for a given subspace dimension according to JL lemma $$ \epsilon = \sqrt{\frac{4 * \log{n}} {d}}$$ where \(d\) is the dimension of the random projection, \(n\) the cardinality of the data and \(1+\epsilon\) the theoretical distortion (maximum expansion) induced by the randomized projection into the d-dimensional subspace.

References

W.Johnson, J.Lindenstrauss, Extensions of Lipshitz mapping into Hilbert space, in: Conference in modern analysis and probability, Vol. 26 of Contemporary Mathematics, Amer. Math. Soc., 1984, pp. 189--206.

See Also

Plus.Minus.One.random.projection, norm.random.projection,

Achlioptas.random.projection, random.subspace

Examples

# dimension of the projected space that we need to obtain a theoretical 1.5 distortion 
# (max. expansion), when 20 data examples are available.
d <- JL.predict.dim(n=20, epsilon = 0.5)
# dimension of the projected space that we need to obtain a theoretical 1.2 distortion 
#(max. expansion), when 20 data examples are available, and 10 random projections
d <- JL.predict.dim.multiple(n=20, epsilon = 0.5, t = 10)
# distortion 1+epsilon that is obtained with 30 examples and a random projection 
# in a 100-dimensional subspace
epsilon <- JL.predict.distortion(n=30, dim = 100)