Fast Orthogonal Projection Based on Kronecker Product
The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956 · cited 7×
“This is efficient because the number of centers is usually small since the number of clusters for each subspace is always set to a small number (h = 256 in [16, 26]).”
BackgroundMethodInfluentialHamming Embedding and Weak Geometric Consistency for Large Scale Image Search
Jegou, H., Douze, M., & Schmid, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_24 · Cited by 1,901
Small codes and large image databases for recognition
Torralba, A., Fergus, R., & Weiss, Y. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587633 · Cited by 727
High-dimensional signature compression for large-scale image classification
Sanchez, J., & Perronnin, F. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995504 · Cited by 272 · cited 1×
“In practice, to achieve high recall in retrieval tasks, it is often desirable to use long codes with a large k such that k = O(d) [22, 8, 29].”
Cited by
Ham, T. J., Lee, Y., Seo, S. H., Kim, S., Choi, H., Jung, S. J., & Lee, J. W. (2021) · 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA) · doi:10.1109/isca52012.2021.00060 · Cited by 192
Compressing RNNs for IoT devices by 15-38x using Kronecker Products
Thakker, U., Beu, J., Gope, D., Zhou, C., Fedorov, I., Dasika, G., & Mattina, M. (2019) · arXiv · doi:10.48550/arxiv.1906.02876 · Cited by 30
“KPs have also been used for orthogonal projections for dimensionality reduction of input matrices (Zhang et al., 2015; Choromanski et al., 2017), which is orthogonal to the present work.”
MethodCompressing RNNs to Kilobyte Budget for IoT Devices Using Kronecker Products
Thakker, U., Fedorov, I., Zhou, C., Gope, D., Mattina, M., Dasika, G., & Beu, J. (2021) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/3440016 · Cited by 8
A Biresolution Spectral Framework for Product Quantization
Mukherjee, L., Peng, J., Ravi, S. N., & Singh, V. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00351 · Cited by 2
“Other relevant works on this topic include iterative quantization [15], distanceencoded PQ[20], tree quantization[7], inner product search quantization[48, 38], inverted multi-index quantization[4, 44], bilayer product quantization [6], hashing-quantization hybrid method called polysemous codes [12] and others [28, 30…”
BackgroundMethod
Metadata
- Authors
- Zhang, X., Yu, F. X., Guo, R., Kumar, S., Wang, S., & Chang, S.-F.
- Venue
- 2015 IEEE International Conference on Computer Vision (ICCV)
- Publisher
- IEEE
- Published
- 2015-12
- Pages
- 2929-2937
- OpenAlex
- W2197984537
- Cited by
- 43
- References
- 4
- FWCI
- 2.91
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Fast Orthogonal Projection Based on Kronecker Product. https://app.cochat.ai/papers/10.1109/iccv.2015.335
- The paper
- Zhang, X., Yu, F. X., Guo, R., Kumar, S., Wang, S., & Chang, S.-F. (2015). Fast Orthogonal Projection Based on Kronecker Product. 2015 IEEE International Conference on Computer Vision (ICCV). https://doi.org/10.1109/iccv.2015.335
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.