Cool. The plots are fun. The way gaussian spots project into spinning chains is very educational about entropy.
For full Random Projection, a lame random number generator (java.lang.Random) will generate a higher standard deviation than a high-quality one like MurmurHash. On Fri, Jul 1, 2011 at 5:25 PM, Ted Dunning <[email protected]> wrote: > Here is R code that demonstrates what I mean by stunning (aka 15 significant > figures). Note that I only check dot products here. From the fact that the > final transform is orthonormal we know that all distances are preserved. > > # make a big random matrix with rank 20 >> a = matrix(rnorm(20000), ncol=20) %*% matrix(rnorm(20000), nrow=20); >> dim(a) > [1] 1000 1000 > # random projection >> y = a %*% matrix(rnorm(30000), ncol=30); > # get basis for y >> q = qr.Q(qr(y)) >> dim(q) > [1] 1000 30 > # re-project b, do svd on result >> b = t(q) %*% a >> v = svd(b)$v >> d = svd(b)$d > # note how singular values drop like a stone at index 21 >> plot(d) >> dim(v) > [1] 1000 30 > # finish svd just for fun >> u = q %*% svd(b)$u >> dim(u) > [1] 1000 30 > # u is orthogonal, right? >> diag(t(u)%*% u) > [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 > # and u diag(d) v' reconstructs a very precisely, right? >> max(abs(a-u %*% diag(d) %*% t(v))) > [1] 1.293188e-12 > > # now project a into the reduced dimensional space >> aa = a%*%v >> dim(aa) > [1] 1000 30 > # check a few dot products >> sum(aa[1,] %*% aa[2,]) > [1] 6835.152 >> sum(a[1,] %*% a[2,]) > [1] 6835.152 >> sum(a[1,] %*% a[3,]) > [1] 3337.248 >> sum(aa[1,] %*% aa[3,]) > [1] 3337.248 > > # wow, that's close. let's try a hundred dot products >> dot1 = rep(0,100);dot2 = rep(0,100) >> for (i in 1:100) {dot1[i] = sum(a[1,] * a[i,]); dot2[i] = sum(aa[1,]* > aa[i,])} > > # how close to the same are those? >> max(abs(dot1-dot2)) > # VERY > [1] 3.45608e-11 > > > > On Fri, Jul 1, 2011 at 4:54 PM, Ted Dunning <[email protected]> wrote: > >> Yes. Been there. Done that. >> >> The correlation is stunningly good. >> >> >> On Fri, Jul 1, 2011 at 4:22 PM, Lance Norskog <[email protected]> wrote: >> >>> Thanks! >>> >>> Is this true? - "Preserving pairwise distances" means the relative >>> distances. So the ratios of new distance:old distance should be >>> similar. The standard deviation of the ratios gives a rough&ready >>> measure of the fidelity of the reduction. The standard deviation of >>> simple RP should be highest, then this RP + orthogonalization, then >>> MDS. >>> >>> On Fri, Jul 1, 2011 at 11:03 AM, Ted Dunning <[email protected]> >>> wrote: >>> > Lance, >>> > >>> > You would get better results from the random projection if you did the >>> first >>> > part of the stochastic SVD. Basically, you do the random projection: >>> > >>> > Y = A \Omega >>> > >>> > where A is your original data, R is the random matrix and Y is the >>> result. >>> > Y will be tall and skinny. >>> > >>> > Then, find an orthogonal basis Q of Y: >>> > >>> > Q R = Y >>> > >>> > This orthogonal basis will be very close to the orthogonal basis of A. >>> In >>> > fact, there are strong probabilistic guarantees on how good Q is as a >>> basis >>> > of A. Next, you project A using the transpose of Q: >>> > >>> > B = Q' A >>> > >>> > This gives you a short fat matrix that is the projection of A into a >>> lower >>> > dimensional space. Since this is a left projection, it isn't quite what >>> you >>> > want in your work, but it is the standard way to phrase things. The >>> exact >>> > same thing can be done with left random projection: >>> > >>> > Y = \Omega A >>> > L Q = Y >>> > B = A Q' >>> > >>> > In this form, B is tall and skinny as you would like and Q' is >>> essentially >>> > an orthogonal reformulation of of the random projection. This >>> projection is >>> > about as close as you are likely to get to something that exactly >>> preserves >>> > distances. As such, you should be able to use MDS on B to get exactly >>> the >>> > same results as you want. >>> > >>> > Additionally, if you start with the original form and do an SVD of B >>> (which >>> > is fast), you will get a very good approximation of the prominent right >>> > singular vectors of A. IF you do that, the first few of these should be >>> > about as good as MDS for visualization purposes. >>> > >>> > On Fri, Jul 1, 2011 at 2:44 AM, Lance Norskog <[email protected]> >>> wrote: >>> > >>> >> I did some testing and make a lot of pretty charts: >>> >> >>> >> http://ultrawhizbang.blogspot.com/ >>> >> >>> >> If you want to get quick visualizations of your clusters, this is a >>> >> great place to start. >>> >> >>> >> -- >>> >> Lance Norskog >>> >> [email protected] >>> >> >>> > >>> >>> >>> >>> -- >>> Lance Norskog >>> [email protected] >>> >> >> > -- Lance Norskog [email protected]
