- Dimensionality Reduction Using Error-Correcting Codes
- Project Year:
2022
- REU Student (s):
Lakshay Patel | University of California-Berkeley CA
- Student 1 Institution:
University of California-Berkeley
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
Computer Science
- Project Abstract:
The Johnson-Lindenstrauss lemma shows that for any n points in Rd and ε>0, there is a map into O(\log(n)ε-2)-dimensional Euclidean space that distorts the pair-wise ℓ2 distances of S by a multiplicative factor of at most (1+ε). This result is known to be optimal for ℓ2, whereas our understanding of dimensionality reduction in Hamming space is far from complete. In this project, we looked for dimensionality reduction methods in Hamming space, with a focus on an approach using the 7-4-3 Hamming code.
