Generating compact representations of high-dimensional data

A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

• receiving a plurality of high-dimensional data items;
• generating a circulant embedding matrix for the high-dimensional data items, wherein the circulant embedding matrix is a matrix that is fully specified by a single vector, and wherein generating the circulant embedding matrix comprises learning each element of the single vector that fully specifies the circulant embedding matrix, comprising:
• receiving a training data matrix which represents a set of training data;
• determining a binary matrix by computing a binary map of the product of the training data matrix and an initial circulant embedding matrix;
• and
• optimizing an objective function that is dependent on the circulant embedding matrix, the training data matrix, and the binary matrix such that a distortion due to binarization and correlation between the rows of the circulant embedding matrix are minimized;
• for each high-dimensional data item, generating a compact representation of the high-dimensional data item, comprising:
• computing a product of the circulant embedding matrix and the high dimensional data item by performing a circular convolution of the single vector that fully specifies the circulant embedding matrix and the high dimensional data item using a Fast Fourier Transform (FFT);
• generating a compact representation of the high dimensional data item by computing a binary map of the computed product;
• and
• providing the compact representations of the high-dimensional data items in place of the high-dimensional data items as input to a machine learning system.

A non-transitory computer storage medium encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

• receiving a plurality of high-dimensional data items;
• generating a circulant embedding matrix for the high-dimensional data items, wherein the circulant embedding matrix is a matrix that is fully specified by a single vector, and wherein generating the circulant embedding matrix comprises learning each element of the single vector that fully specifies the circulant embedding matrix, comprising:
• receiving a training data matrix which represents a set of training data;
• determining a binary matrix by computing a binary map of the product of the training data matrix and an initial circulant embedding matrix;
• and
• optimizing an objective function that is dependent on the circulant embedding matrix, the training data matrix, and the binary matrix such that a distortion due to binarization and correlation between the rows of the circulant embedding matrix are minimized;
• for each high-dimensional data item, generating a compact representation of the high-dimensional data item, comprising:
• computing a product of the circulant embedding matrix and the high dimensional data item by performing a circular convolution of the single vector that fully specifies the circulant embedding matrix and the high dimensional data item using a Fast Fourier Transform (FFT);
• generating a compact representation of the high dimensional data item by computing a binary map of the computed product;
• and
• providing the compact representations of the high-dimensional data items in place of the high-dimensional data items as input to a machine learning system.