Hierarchical learning of optimal linear representations

Due to their efficiency, linear representations are widely used in appearance-based recognition. However, frequently used ones, such as PCA, ICA, and FDA, do not provide optimal performance as empirical studies have reported contradictory conclusions in the literature. To overcome this problem and provide an algorithm for finding the optimal linear representations for different applications, a Monte Carlo Markov chain based optimization algorithm was recently proposed and its effectiveness has been demonstrated on a number of datasets. By formulating the problem on Grassmann manifolds, the algorithm is computationally efficient when the image size is relatively small. When images in typical applications are used, the optimization process is time consuming. In this paper, to speed up the algorithm, we propose a hierarchical learning one. The proposed algorithm decomposes the optimization in the given image space into several stages organized according to hierarchical layers. Given an image space, first its dimension is reduced using a shrinkage matrix and the optimization is then performed in the reduced space. By expanding the obtained optimal subspace in the reduced one in a specified way, we show analytically that the performance is maintained. By applying the decomposition procedure recursively, a hierarchy of layers can be formed. This speeds up the original algorithm significantly as the search is done mainly in reduced spaces. The effectiveness of hierarchical learning is illustrated on a popular database, where the computation time is reduced by 600,000 factors compared to the original algorithm.