JL.predict.dim: Dimension of the subspace or the distortion predicted...

In clusterv: Assessment of Cluster Stability by Randomized Maps

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)

Arguments

n	cardinality of the data
epsilon	distortion (0 < epsilon <= 0.5)
t	number of multiple projections
dim	dimensionality of the projected subspace

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.

Value

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

Author(s)

Giorgio Valentini [e-mail]

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)

clusterv documentation built on June 8, 2025, 10:21 a.m.