Abstract: Random embedding techniques, such as random Fourier features, are widely used to sketch initial data to a new, kernelised feature space. In this work, we leverage a specific property of random rank-one projection operators, the sign product embedding, to approximate a quadratic polynomial kernel using the scalar product of a pair asymmetric vector embeddings, with one taking only binary values. We demonstrate empirically that the approximated kernel compares favourably to the initial one on toy binary classification examples.