[ammai2016] Iterative Quantization: A Procrustean Approach to Learning Binary Codes

Date: March 17th, 2016

Title: Iterative Quantization: A Procrustean Approach to Learning Binary Codes

Author: Yunchao Gong and Svetlana Lazebnik

Novelties:

1. Introduce a way to rotate the data and preserve the locality structure.

Contributions:

This paper introduces a better way to do binary codes called ITQ.
To judge whether a method is good or not, it considers three constraints: the length of the code, the Hamming distance between similar images, and the efficiency.
The ITQ method can perform on unsupervised data embeddings (PCA) and supervised data embedding (CCA), that is, this method can work on any projection.

Technical Summarizes:

For unsupervised part, they first do dimensionality reduction with PCA and make our data zero-centered.

If we simply do binary coding on PCA aligned data, the result might look like (a), which split the cluster into two different parts. ITQ will rotate it first like (c) to put the dots in the same cluster into same code.
That is, we should find a rotation with smaller quantization loss:

B is the target coding matrix, contains n codes with length c, V is the projected data, and R starts with a random initialization c by c matrix.
Then there are two steps to do cyclically: "Fix R and update B" and "Fix B and update R."

1. Fix R and update B:
This step wants to minimize Q(B,R), that is to say, it wants to maximizing:

Where the V with tilde denotes VR. Then they can get B=sgn(VR).

2. Fix B and update R:
R can be calculated with B and SVD method.

Experiments:

The unsupervised datasets are subsets of the Tiny Image dataset. The first is a version of CIFAR dataset, the second is a larger subset. The images of these datasets are 32 x 32 pixels.

They evaluate these by nearest neighbor search and average precision of top 500 ranked image for each query.

By compare with other methods with mAPs, the PCA-ITQ method performs very well.

Then they perform ITQ on dataset with CCA and shows CCA-ITQ on clean dataset is better than baseline, and CCA-ITQ on noisy dataset is way better than PCA-ITQ.