PaperlayerView exact revision on arXiv

Source-linked AI summary

Circulant Binary Embedding

Felix X. Yu, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang

arXiv:1405.3162v1stat.MLcs.LG

TL;DR

High-dimensional binary embedding needs long codes, but conventional methods incur prohibitive computation and storage costs. The paper introduces CBE, which uses circulant projections, FFT computation, and time-frequency alternating optimization for data-dependent learning. It reports better performance at fixed time and much faster computation without performance degradation at a fixed number of bits.

  • Problem

    High-dimensional binary embedding requires long codes, while conventional projection methods incur O(d^2) computation and storage costs.

  • Method

    CBE projects data with a circulant matrix using FFT-based computation and learns data-dependent projections through time-frequency alternating optimization.

  • Results

    The proposed method improves results at fixed time and provides much faster computation with no performance degradation for a fixed number of bits.

  • Takeaways & Limitations

    CBE enables long binary codes for very high-dimensional data with O(d log d) time and O(d) space complexity.

  • Takeaways & Limitations

    Randomized CBE does not use the underlying data distribution, motivating the learned data-dependent projection variant.

Abstract

from arXiv · show

Binary embedding of high-dimensional data requires long codes to preserve the discriminative power of the input space. Traditional binary coding methods often suffer from very high computation and storage costs in such a scenario. To address this problem, we propose Circulant Binary Embedding (CBE) which generates binary codes by projecting the data with a circulant matrix. The circulant structure enables the use of Fast Fourier Transformation to speed up the computation. Compared to methods that use unstructured matrices, the proposed method improves the time complexity from $\mathcal{O}(d^2)$ to $\mathcal{O}(d\log{d})$, and the space complexity from $\mathcal{O}(d^2)$ to $\mathcal{O}(d)$ where $d$ is the input dimensionality. We also propose a novel time-frequency alternating optimization to learn data-dependent circulant projections, which alternatively minimizes the objective in original and Fourier domains. We show by extensive experiments that the proposed approach gives much better performance than the state-of-the-art approaches for fixed time, and provides much faster computation with no performance degradation for fixed number of bits.

1. Introduction

High-dimensional binary embedding requires long codes, but conventional projection methods become impractical because their computation and storage scale quadratically with input dimensionality. CBE addresses this bottleneck with circulant projections and FFT-based computation, while learning data-dependent projections through time-frequency alternating optimization.

  • Motivation: Long binary codes are needed to preserve performance on high-dimensional data, where the required number of bits is O(d).Binary embedding aims to approximate input distances with Hamming distance for efficient learning and retrieval.
  • Motivation: Existing data-dependent binary coding methods face O(d^2) computation and storage costs, making O(d)-bit codes impractical for very high-dimensional inputs.For d ∼1M, such projections would require terabytes of memory.
  • Prior approaches and CBE: Bilinear coding reduces costs to O(d^1.5) time and O(d) space, but CBE further reduces time complexity by imposing a circulant structure on the projection matrix.The circulant structure enables FFT-based projection.
  • CBE contribution: CBE has O(d log d) time and O(d) space complexity for generating long binary codes.These complexities improve on unstructured projection methods for high-dimensional data.
  • CBE contribution: The proposed time-frequency alternating optimization learns data-dependent circulant projections by alternating objective optimization in the original and frequency domains.This optimization is introduced to adapt the projection to the training data efficiently.
  • Empirical outcome: The experiments report better performance at fixed time and faster computation without performance degradation at fixed code length compared with state-of-the-art methods.The comparison includes bilinear coding and other structured or unstructured approaches.

2. Circulant Binary Embedding (CBE)

Circulant Binary Embedding generates binary codes with a circulant projection, reducing storage and computation through FFT-based convolution. For k<d, the code uses the first k bits of the d-bit embedding.

  • Circulant projection: A circulant projection matrix is defined by a single vector r, reducing its storage requirement to O(d).The matrix is written as R = circ(r).
  • Code construction: CBE applies random sign flipping before projecting x and binarizes the result as h(x) = sign(Rx).The k-bit code is the first k elements of the resulting d-bit embedding.
  • Complexity: CBE has space complexity O(d) and time complexity O(d log d) for d-dimensional data.The space bound follows from storing one defining row or column, while the time bound follows from FFT-based computation.
  • FFT computation: Cirant convolution can be computed through DFT and IDFT, whose FFT implementations reduce projection time to O(d log d).The frequency-domain operation uses a Hadamard product equivalent to convolution in the original domain.
  • Code length: For k-bit CBE with k<d, only the first k bits of h(x) are retained.This extracts the requested code length from the full d-bit embedding.

3. Randomized Circulant Binary Embedding

Randomized CBE samples the circulant vector from a standard normal distribution, but its dependent circulant projections complicate variance analysis. Simulations compare its distance variance with independent projections, while random sign flipping is required for projection norm preservation.

  • Randomized construction: Randomized CBE generates the entries of r independently from N(0, 1).This defines the randomized, data-independent version of the circulant projection.
  • Projection dependence: Because circulant variants of r share the same distribution, each projection has the same distribution when r is sampled from N(0, 1).The rows are nevertheless not independent because they are generated from the same circulant vector.
  • Distance variance: For independent projections, increasing the number of bits lowers normalized Hamming-distance variance and makes it approach its expected value.The normalized Hamming distance therefore approximately preserves the angle between points in that comparison.
  • Variance comparison: Figure 1 compares analytical variance for independent bits with sample variance for circulant bits across angle θ and bit count k; the two curves overlap.The caption identifies angle between points and number of bits as the varying quantities.
  • Projection distortion: Random sign flipping is necessary before circulant projection because an all-one input can otherwise collapse to a repeated inner product and lose norm preservation.Johnson–Lindenstrauss-type results do not extend to distortion introduced by binarization.
  • Data dependence: Randomized CBE does not use the underlying data distribution, motivating data-dependent learning to reduce projection and binarization distortions.The paper introduces learned circulant projections as the next step.

4. Learning Circulant Binary Embedding

CBE learns data-dependent circulant projections by alternating between binary-code updates in the input domain and projection updates in the frequency domain. The optimization reduces redundancy while preserving efficient computation for both d-bit and k<d-bit codes.

  • Objective: The learning objective minimizes binarization distortion while encouraging uncorrelated projection rows to reduce redundancy in the learned code.For an orthogonal projection matrix, the redundancy penalty vanishes; circulant matrices are generally not orthogonal.
  • Alternating optimization: The optimization is combinatorial and seeks a local solution by alternately fixing the projection vector r and binary code matrix B.With fixed r, B is optimized in the input domain; with fixed B, r is optimized in the frequency domain.
  • Frequency-domain update: DFT-based optimization represents the circulant projection in the frequency domain, where r is solved and recovered through the inverse DFT.The method uses Parseval’s theorem and the diagonalization of circulant matrices by the DFT matrix to formulate the frequency-domain objective.
  • Frequency-domain update: The frequency-domain subproblems are fourth-order polynomials whose objective is nonincreasing after each optimization step.One-variable subproblems have closed-form solutions, while two-variable subproblems use gradient descent to find local minima.
  • Fewer-bit codes: For k<d bits, the method uses a temporal cut-off heuristic that sets later binary-code columns to zero while retaining O(nd log d) optimization cost.The cut-off avoids the non-decomposable frequency-domain objective introduced by right multiplication with P_k.

5. Experiments

Experiments evaluate CBE on high-dimensional retrieval and classification tasks, comparing fixed-time and fixed-bit performance with full and bilinear projections. CBE provides stronger fixed-time recall, similar fixed-bit performance with much faster computation, and no classification degradation.

  • Experimental setup: Experiments use Flickr-25600 and ImageNet datasets with 10,000 training instances, 500 queries, and recall@1-100 based on 10-nearest-neighbor ground truth.Comparisons include randomized and learned CBE and bilinear embeddings, plus LSH and other full-projection methods.
  • Computational cost: CBE has O(d log d) projection time, while full and bilinear projection methods have O(kd); measured runtimes are roughly characterized by d^2 : d : 5d log d.The comparison uses a single 2.9GHz CPU core, with errors within 10%; empty table cells indicate memory needs above 24GB.
  • Retrieval: At fixed code-generation time, CBE yields much better recall than competing methods, including when using randomized projections.The fixed-time comparison gives all methods the same code-generation time as CBE.
  • Retrieval: At fixed code length, CBE-rand has nearly the same performance as LSH while running hundreds of times faster, and CBE variants outperform bilinear variants while being 2-3 times faster.These comparisons are reported across the high-dimensional retrieval experiments.
  • Classification: On ImageNet-25600 classification, CBE has much faster computation without performance degradation compared with LSH or bilinear codes.The same-dimensional binary codes are reported as 32 times more space efficient than the original single-float features.
  • Low-dimensional comparison: On Flickr-2048, CBE-opt performs better or equivalently than other techniques except ITQ, while the performance gap narrows as the number of bits increases.ITQ is described as scaling poorly with d, with O(d^3) complexity.

6. Semi-supervised Extension

The CBE formulation incorporates labeled similar and dissimilar pairs through an additional objective term. This semi-supervised extension is optimized with the same time-frequency alternating procedure and improves averaged AUC on ImageNet-25600.

  • Semi-supervised objective: Labeled similar and dissimilar pairs are incorporated by adding an objective term to the CBE formulation.The extension uses pairwise information during learning.
  • Semi-supervised objective: The additional term minimizes distances for similar pairs and maximizes distances for dissimilar pairs.M denotes similar instances and D denotes dissimilar instances.
  • Results: The semi-supervised extension improves averaged AUC by 2% on ImageNet-25600 compared with the non-semi-supervised version.Optimization replaces M in the original objective with M+µA.

7. Conclusion

The paper proposes circulant binary embedding for long codes on very high-dimensional data. Its time-frequency optimization achieves linear space and near-linear time complexity while maintaining performance against more expensive approaches and improving accuracy at fixed time.

  • Conclusion: Circulant binary embedding generates long codes for very high-dimensional data.The method is designed for settings where other approaches may be impractical.
  • Conclusion: O(d log d) time and O(d) space complexity enable efficient embedding compared with O(d^2) or O(d^1.5) approaches.The conclusion reports no performance degradation on real-world data relative to these more expensive methods.
  • Conclusion: For fixed time, the proposed method achieves significant accuracy gains, with potential application to ultra-high-dimensional data around d ∼100M.The conclusion states that no other methods are applicable at that scale.
Loading 1405.3162v1…