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.
Abstract: Many signal processing and machine learning applications are built from evaluating a kernel on pairs of signals, e.g. to assess the similarity of an incoming query to a database of known signals.