Convergence Analysis of an Empirical Eigenfunction-Based Ranking Algorithm with Truncated Sparsity

Abstract EN

We study an empirical eigenfunction-based algorithm for ranking with a data dependent hypothesis space.

The space is spanned by certain empirical eigenfunctions which we select by using a truncated parameter.

We establish the representer theorem and convergence analysis of the algorithm.

In particular, we show that under a mild condition, the algorithm produces a satisfactory convergence rate as well as sparse representations with respect to the empirical eigenfunctions.