Fast Orthogonal Projection Based on Kronecker Product
Venue
International Conference on Computer Vision (ICCV) (2015)
Publication Year
2015
Authors
Xu Zhang, Felix X. Yu, Ruiqi Guo, Sanjiv Kumar, Shengjin Wang, Shih-Fu Chang
BibTeX
Abstract
We propose a family of structured matrices to speed up orthogonal projections for
high-dimensional data commonly seen in computer vision applications. In this, a
structured matrix is formed by the Kronecker product of a series of smaller
orthogonal matrices. This achieves O(dlogd) computational complexity and O(logd)
space complexity for d-dimensional data, a drastic improvement over the standard
unstructured projections whose computational and space complexities are both
O(d^2). We also introduce an efficient learning procedure for optimizing such
matrices in a data dependent fashion. We demonstrate the significant advantages of
the proposed approach in solving the approximate nearest neighbor (ANN) image
search problem with both binary embedding and quantization. Comprehensive
experiments show that the proposed approach can achieve similar or better accuracy
as the existing state-of-the-art but with significantly less time and memory.
