Theoretical Analysis of Null Foley-Sammon Transform and its Implications

Null Foley-Sammon Transform (NFST) has received increasing attention in the machine learning and pattern recognition literature. NFST finds a discriminative nullspace where all samples of the same class get mapped into a single point. It has a closed form solution and is free of parameters to tune. NFST has been leveraged in many areas including novelty detection, person or vehicle re-identification and achieved state-of-the-art results. Motivated from its attractive properties and its effectiveness in wide range of applications, in this paper we focus on the theoretical analysis of NFST. In previous literature, NFST was shown to exist in small sample size (SSS) case. We first prove that NFST can exist in non-SSS case also, under certain conditions. Thereby, we extend the domain of applicability of NFST to a more general case. Secondly, we perform analysis of the singular points of NFST, revealing important insights on their identities and existence. Thirdly, we show the theoretical relation between NFST of SSS data and NFST of the non-SSS data obtained by PCA. Fourthly, we show that this theoretical relation can be exploited to obtain an efficient algorithm for computing NFST on high dimensional SSS data. Finally, we perform extensive experiments to validate our theoretical analysis.