Randomized numerical linear algebra for generalized linear models with big datasets

Abstract

Data scientific questions face the fundamental trade-off between complexity, generalizability and computational feasibility. The need for quick estimation and evaluation of a vast amount of statistical models has given rise to a plethora of new and innovative algorithms in the field of randomized numerical linear algebra (RandNLA). They intend to decrease effective running time by approximating exact solutions. One commonly allows for some e-"slack" in order to make use of powerful subspace embedding ideas such as the Johnson-Lindenstrauss transform (JLT). In this way, one is able to significantly reduce the dimensionality of the problem, while preserving a substantial amount of the original structure. Petros Drineas and Michael Mahoney have been applying these ideas to a range of problems such as solving linear systems of equations (over-and under-constrained), matrix completion and low-rank matrix approximation.

Les qüestions científiques de dades afronten el compromís fonamental entre complexitat, generalizabilitat i viabilitat computacional. La necessitat d'una ràpida estimació i avaluació d'una gran quantitat de models estadístics ha donat lloc a una infinitat d'algorismes nous i innovadors en el camp de l'àlgebra lineal numèrica aleatòria (RandNLA). Tenen la intenció de disminuir el temps d'execució efectiu mitjançant l'aproximació de solucions exactes. Un comunament permet una mica de "descentralització" per a fer ús d'idees incrustantes potents de subespacio com la transformació Johnson-Lindenstrauss (JLT). D'aquesta manera, es pot reduir significativament la dimensionalitat del problema, tot conservant una quantitat substancial de l'estructura original. Petros Drineas i Michael Mahoney han estat aplicant aquestes idees a una sèrie de problemes com la solució de sistemes lineals d'equacions (sobre i subterfugis), la finalització de la matriu i la aproximació a la matriu de baix rang.