NDLI: Hashing with Generalized Nyström Approximation

Content Provider	IEEE Xplore Digital Library
Author	Jeong-Min Yun Saehoon Kim Seungjin Choi
Copyright Year	2012
Abstract	Hashing, which involves learning binary codes to embed high-dimensional data into a similarity-preserving low-dimensional Hamming space, is often formulated as linear dimensionality reduction followed by binary quantization. Linear dimensionality reduction, based on maximum variance formulation, requires leading eigenvectors of data covariance or graph Laplacian matrix. Computing leading singular vectors or eigenvectors in the case of high-dimension and large sample size, is a main bottleneck in most of data-driven hashing methods. In this paper we address the use of generalized Nystrom method where a subset of rows and columns are used to approximately compute leading singular vectors of the data matrix, in order to improve the scalability of hashing methods in the case of high-dimensional data with large sample size. Especially we validate the useful behavior of generalized Nystrom approximation with uniform sampling, in the case of a recently-developed hashing method based on principal component analysis (PCA) followed by an iterative quantization, referred to as PCA+ITQ, developed by Gong and Lazebnik. We compare the performance of generalized Nystrom approximation with uniform and non-uniform sampling, to the full singular value decomposition (SVD) method, confirming that the uniform sampling improves the computational and space complexities dramatically, while the performance is not much sacrificed. In addition we present low-rank approximation error bounds for generalized Nystrom approximation with uniform sampling, which is not a trivial extension of available results on the non-uniform sampling case.
Starting Page	1188
Ending Page	1193
File Size	293169
Page Count	6
File Format	PDF
ISBN	9781467346498
ISSN	15504786
DOI	10.1109/ICDM.2012.22
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-12-10
Publisher Place	Belgium
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Principal component analysis Binary codes Vectors Approximation error Approximation algorithms Quantization uniform sampling CUR decomposition hashing generalized Nystrom approximation pseudoskeleton approximation
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hashing with generalized nyström approximation.

Efficient binary codes for extremely high-dimensional data

Clusterability Analysis and Incremental Sampling for Nyström Extension Based Spectral Clustering

Improving CUR Matrix Decomposition and Nyström Approximation via Adaptive Sampling (2013)

Improving cur matrix decomposition and the nyström approximation via adaptive sampling.

A DEIM Induced CUR Factorization

Improved binary codes for efficient content-based image retrieval

Learning Binary Codes for Hashing via Feature Decomposition

K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes

Hashing with Generalized Nyström Approximation

Similar Documents

Hashing with generalized nyström approximation.

Efficient binary codes for extremely high-dimensional data

Clusterability Analysis and Incremental Sampling for Nyström Extension Based Spectral Clustering

Improving CUR Matrix Decomposition and Nyström Approximation via Adaptive Sampling (2013)

Improving cur matrix decomposition and the nyström approximation via adaptive sampling.

A DEIM Induced CUR Factorization

Improved binary codes for efficient content-based image retrieval

Learning Binary Codes for Hashing via Feature Decomposition

K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes

Hashing with Generalized Nyström Approximation