Revisiting Nearest Neighbors from a Sparse Signal Approximation View

A Google TechTalk, presented by Sarath Shekkizhar, 2023-07-10 Google Algorithms Seminar ABSTRACT: Neighborhood and graph construction is fundamental in data analysis and machine learning. k-nearest neighbor (kNN) and epsilon-neighborhood methods are the most commonly used methods for this purpose due to their computational simplicity. However, the interpretation and the choice of parameter k/epsilon, though receiving much attention over the years, still remains ad hoc. In this talk, I will present an alternative view of neighborhoods where I demonstrate that neighborhood definitions are sparse signal approximation problems. Specifically, we will see that (1) kNN and epsilon-neighborhood approaches are sub-optimal thresholding-based representations; (2) an improved and efficient definition based on basis pursuits exists, namely, non-negative kernel regression (NNK); and (3) selecting orthogonal signals for sparse approximation corresponds to the selection of neighbors that are not geometrically redundant. NNK neighborhoods are adaptive, sparse, and exhibit superior performance in graph-based signal processing and machine learning. We will then discuss a k-means like algorithm where we leverage the polytope geometry and sparse coding view of NNK for data summarization and outlier detection. I will conclude by discussing a graph framework for an empirical understanding of deep neural networks (DNN). The developed graph metrics characterize the input-output geometry of the embedding spaces induced in DNN and provide insights into the similarities and differences between models, their invariances, and their generalization and transfer learning performances. Bio: Sarath Shekkizhar received his bachelor’s (Electronics and Communication) and double master’s (Electrical Engineering, Computer Science) degrees from the National Institute of Technology, Tiruchirappalli, India, and the University of Southern California (USC), Los Angeles, USA, respectively. He recently graduated from Antonio Ortega’s group with his doctoral degree in Electrical and Computer Engineering at USC. He is the recipient of the IEEE best student paper award at ICIP 2020 and was named a Rising Star in Signal Processing at ICASSP 2023. His research interests include graph signal processing, non-parametric methods, and machine learning.