Achlioptas.random.projection: Achlioptas random projection

In clusterv: Assessment of Cluster Stability by Randomized Maps

Achlioptas random projection

Description

Random projections to a lower dimension subspace with the Achlioptas' projection matrix. The projection is performed using a projection matrix R s.t. Prob(R[i,j]=sqrt(3))=Prob(R[i,j]=-sqrt(3)=1/6; Prob(R[i,j]=0)=2/3

Usage

Achlioptas.random.projection(d = 2, m, scaling = TRUE)

Arguments

d	subspace dimension
m	data matrix (rows are features and columns are examples)
scaling	if TRUE (default) scaling is performed

Details

Achlioptas random projections are represented by d'\times d matrices P = 1/\sqrt{d'} (r_{ij}), where r_{ij} are chosen in \{-\sqrt{3},0,\sqrt{3}\}, such that Prob(r_{ij} = 0) = 2/3, Prob(r_{ij} = \sqrt{3}) = Prob(r_{ij} = -\sqrt{3}) = 1/6. In this case also we have E[r_{ij}] = 0 and Var[r_{ij}] = 1 and the Johnson-Lindenstrauss lemma holds.

Value

data matrix (dimension d x ncol(m)) of the examples projected in a d-dimensional random subspace

Author(s)

Giorgio Valentini [e-mail]

References

D.Achlioptas, Database-friendly random projections., in: Proc. ACM Symp. on the Principles of Database Systems, Contemporary Mathematics, 2001, pp. 274-281.

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, random.subspace

Examples

# Achlioptas random projection from a 1000 dimensional space to a 50-dimensional subspace
m <- matrix(runif(10000), nrow=1000)
m.p <- Achlioptas.random.projection(d = 50, m, scaling = TRUE)
# Achlioptas random projection from a 10000 dimensional space to a 1000-dimensional subspace
m <- matrix(rnorm(500000), nrow=5000)
m.p <- Achlioptas.random.projection(d = 1000, m, scaling = TRUE)
# The same as above without scaling
m <- matrix(rnorm(500000), nrow=5000)
m.p <- Achlioptas.random.projection(d = 1000, m, scaling = FALSE)

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