Spectral hashing
Algorithms AIMech:SpectralHashing DRAFT
An unsupervised binary-code learning algorithm that approximates a spectral similarity-preservation objective using a PCA-aligned rectangular data model and zero-thresholded single-coordinate analytic modes.
Identity Notes & Concept Scope
This is the original Weiss–Torralba–Fergus spectral hashing algorithm. Its graph-based relaxation motivates the method, while the efficient out-of-sample algorithm uses a fitted rectangular distribution instead of eigendecomposing the complete empirical graph for every query. It differs from neural semantic hashing, random-projection locality-sensitive hashing, Laplacian Eigenmaps and the later multidimensional spectral hashing formulation. The ambiguous abbreviation SH is not claimed as an exclusive alias. All 442 pinned AIO labels/scoped synonyms and 367 preceding native IDs/names/aliases were compared, with no normalized identity match. Full-checkout fixed-string searches included ignored and hidden files in both worktree and main, returning 37 lines each. All 27 unique matched contents were read: conditional-RBM source references, contrasting method descriptions, pending leads and saved review context, rather than existing candidate identities. All 45 semantic label/synonym hits and 23 exact annotated AIO nodes were inspected, alongside corresponding generated records and three complete native neighbors. Previously read contextual files were checked for byte identity. Absence is bounded to this snapshot and inspected neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
The motivation minimizes affinity-weighted squared distances between binary codes, subject to balanced bits and pairwise decorrelation; dropping the binary restriction yields low nonconstant graph-Laplacian modes. The practical algorithm first computes PCA coordinates and fits an interval [a_j,b_j] along each retained nondegenerate axis. Under its uniform-rectangle approximation, enumerate nonconstant single-axis modes with positive integer frequency m, represented in shifted coordinates by cos(m*pi*(x_j-a_j)/(b_j-a_j)). Rank these modes by their analytic eigenvalue order, equivalently increasing squared frequency (m/(b_j-a_j))^2 for a common positive bandwidth, and select the required number of bits. Exclude the constant mode and multidimensional outer-product modes. Threshold each selected function at zero to form binary codes. A new point is projected into the same PCA coordinates and evaluated by these selected functions; hash-table retrieval then compares codes within a chosen Hamming radius.
⚠️ Curated Limitations & Negative Results
- The uniform rectangular model is an approximation to the data distribution. The resulting code is not the exact optimum of the discrete balanced-partition problem or necessarily the thresholded eigenvectors of the finite empirical affinity graph.
- Equation (2) prints Y^T Y=I while retaining unscaled plus/minus-one entries. Equation (1) instead implies Y^T Y=nI for n observations; an identity normalization requires rescaled real-valued relaxed coordinates. The record preserves this distinction rather than copying the incompatible constraints.
- Equation (4) gives the interval width but omits the origin shift unless its x already denotes a shifted coordinate. The mechanism states that shift explicitly. Degenerate axes, zero-threshold ties and points outside fitted intervals require explicit numerical conventions.
- Continuous orthogonality does not guarantee empirical balance, decorrelation or independence after thresholding. Excluding outer-product modes avoids one explicit source of deterministic redundancy but does not ensure independent bits; even first and third thresholded modes on one uniform axis are correlated.
- The number of bits need not be smaller than the input dimension. Compact storage and approximate-neighbor retrieval are not a guarantee of dimension reduction, exact semantic similarity, universal retrieval accuracy or collision resistance for cryptography. No benchmark ranking, general spectral-convergence theorem or author-code behavior is certified.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:PrincipalComponentAnalysis
Principal Component Analysis
|
related_match | PCA supplies the coordinate axes used by the original spectral-hashing algorithm. This is a component relationship, not equivalence or a claim that the final nonlinear binary code is a PCA projection. The pinned PCA entry is task-scoped, and binary-code length is not necessarily lower than input dimension. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Yair Weiss, Antonio Torralba, Rob Fergus
|
primary paper
full_text
|
ID: https://papers.nips.cc/paper/2008/hash/d58072be2820e8682c0a27c0518e805e-Abstract.html
sha256:3ad2470d89ee…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T19:05:47Z
Updated: 2026-10-11T19:05:47Z
Source File:
data/curated/SpectralHashing.yaml