Fast Orthogonal Projection Based on Kronecker Product

Citations Over TimeTop 10% of 2015 papers

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). The proposed structured matrices are applicable to a number of application domains, and are faster and more compact than other structured matrices used in the past. 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. We find that the orthogonality plays a very important role in solving ANN problem, since the random orthogonal Kronecker projection has already provided promising performance. 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.

Related Papers

• → Hierarchical Kronecker tensor-product approximations(2005)118 cited
• → Hierarchical Kronecker tensor-product approximations(2005)11 cited
• → Derivatives of Kronecker Products Themselves Based on Kronecker Products and Matrix Calculus(2012)
• → Functional-matrix theory for the general linear electrical network. Part 5: Use of Kronecker products and Kronecker sums(1969)
• → Kronecker Product of Tensors and Hypergraphs: Structure and Dynamics(2023)