An efficient rank-deficient computation of the principle of relevant information

One of the main difficulties in computing information theoretic learning (ITL) estimators is the computational complexity that grows quadratically with data. Considerable amount of work has been done on computation of low rank approximations of Gram matrices without accessing all their elements. In this paper we discuss how these techniques can be applied to reduce computational complexity of Principle of Relevant Information (PRI). This particular objective function involves estimators of Renyi's second order entropy and cross-entropy and their gradients, therefore posing a technical challenge for implementation in a realistic scenario. Moreover, we introduce a simple modification to the Nyström method motivated by the idea that our estimator must perform accurately only for certain vectors not for all possible cases. We show some results on how this rank deficient decompositions allow the application of the PRI on moderately large datasets.