Similarity-Preserving Binary Signature for Linear Subspaces


  • Jianqiu Ji Tsinghua University
  • Jianmin Li Tsinghua University
  • Shuicheng Yan National University of Singapore
  • Qi Tian University of Texas at San Antonio
  • Bo Zhang Tsinghua University



linear subspace, binary signature


Linear subspace is an important representation for many kinds of real-world data in computer vision and pattern recognition, e.g. faces, motion videos, speeches. In this paper, first we define pairwise angular similarity and angular distance for linear subspaces. The angular distance satisfies non-negativity, identity of indiscernibles, symmetry and triangle inequality, and thus it is a metric. Then we propose a method to compress linear subspaces into compact similarity-preserving binary signatures, between which the normalized Hamming distance is an unbiased estimator of the angular distance. We provide a lower bound on the length of the binary signatures which suffices to guarantee uniform distance-preservation within a set of subspaces. Experiments on face recognition demonstrate the effectiveness of the binary signature in terms of recognition accuracy, speed and storage requirement. The results show that, compared with the exact method, the approximation with the binary signatures achieves an order of magnitude speed-up, while requiring significantly smaller amount of storage space, yet it still accurately preserves the similarity, and achieves high recognition accuracy comparable to the exact method in face recognition.




How to Cite

Ji, J., Li, J., Yan, S., Tian, Q., & Zhang, B. (2014). Similarity-Preserving Binary Signature for Linear Subspaces. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).