[apw]

The cited Weinberger article says:

  Different from random projections, the hashing-trick
  preserves sparsity and introduces no additional overhead 
  to store projection matrices.

[cscheid]

The storage of random projection matrices is puzzling, because there's a well-known trick in always building the projection matrices from a known seed. It gives you the right distribution properties, and none of the storage woes. With a sufficiently fast RNG, this could actually be faster than storing it in main memory because of cache pollution.