Abstract. We propose to use a binary random matrix with elements {0,1} to project input vectors of floating point format to output vectors of the same format but of reduced dimension. We analyze the accuracy of the estimate of scalar product, Euclidean distance, and the norm of input vectors based on output vectors. We show analytically and experimentally that the error for the proposed random projection is less than that for the ternary random matrix.

Keywords: binary random projection, decrease in dimension, estimate for the similarity of vectors.