On Compressive Ensemble Induced Regularisation: How Close is the Finite Ensemble Precision Matrix to the Infinite Ensemble?

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Colleges, School and Institutes


Averaging ensembles of randomly oriented low-dimensional projections of a singular co-variance represent a novel and attractive means to obtain a well-conditioned inverse, which only needs access to random projections of the data. However, theoretical analyses so far have only been done at convergence, implying good properties for ‘large-enough’ ensembles. But how large is ‘large enough’? Here we bound the expected difference in spectral norm between the finite ensemble precision matrix and the infinite ensemble, and based on this we give an estimate of the required ensemble size to guarantee the approximation
error of the finite ensemble is below a given tolerance. Under mild assumptions, we find that for any given tolerance, the ensemble only needs to grow linearly in the original data dimension. A technical ingredient of our analysis is to upper bound the spectral norm of a matrix-variate T, which we then employ in conjunction with specific results from random matrix theory regarding the estimation of the covariance of random matrices.


Original languageEnglish
Title of host publicationProceedings of 28th International Conference on Algorithmic Learning Theory (ALT 2017)
Publication statusAccepted/In press - 24 Jul 2017
Event28th International Conference on Algorithmic Learning Theory (ALT 2017) - Kyoto, Japan
Duration: 15 Oct 201717 Oct 2017

Publication series

NameProceedings of Machine Learning Research
ISSN (Electronic)1938-7228


Conference28th International Conference on Algorithmic Learning Theory (ALT 2017)


  • Ensemble learning, Compressive learning, Random matrix theory, Matrix- variate T