Class-specific   nonlinear discriminant analysis is a popular method to achieve nonlinear data   projections which have been found to outperform linear ones with a large   extend in face verification problem. Being a two-step process formed by an   eigenanalysis step and a kernel regression step, the approximate class-specific   kernel spectral regression method (ACS-KSR) may suffer from heavily   computational overhead in practice, especially for large-sample data. The low-rank   approximation is an efficient approach to reduce the high computational cost   of the algorithms involving large-scale kernel matrix. In this paper, we   propose two randomized approximate algorithms based on ACS-KSR method. The   main contribution of our work is four-fold. Firstly, we present a modified   model of target matrix in the eigenanalysis step and provide two methods for   quickly solving this model by exploiting the structure of scatter matrices.   Secondly, we show that numerical low-rank property of Gaussian kernel matrix   (and Laplacian kernel matrix) from a theoretical point of view, and determine   a practical target rank required in the randomized process. Thirdly, based on   this numerical low-rank property of Gaussian kernel matrix, in kernel regression   step, we provide a fixed-rank modified Nystr\"{o}m method and establish   a probabilistic error bound on the algorithm. Finally, to avoid explicitly   forming the kernel matrix and to further reduce the computational overhead, we   propose a randomized block Kaczmarz algorithm with multiple right-hand sides   for solving the kernel regression problem. The convergence of the algorithm   is established. Comprehensive numerical experiments are performed to show the   effectiveness and efficiency of the proposed randomized algorithms.

会议网址：https://meeting.tencent.com/s/0HHeF1o4ZSPJ

会议ID：456 923 924

会议密码：201024