LEARNING APPROACH FOR FAST APPROXIMATE MATRIX FACTORIZATIONS

Efficiently computing an (approximate) orthonormal basisand low-rank approximation for the input data X plays acrucial role in data analysis. One of the most efficient al-gorithms for such tasks is the randomized algorithm, whichproceeds by computing a projection XA with a random pro-jection matrix A of much smaller size, and then computingthe orthonormal basis as well as low-rank factorizations ofthe tall matrix XA. While a random matrix A is thede factochoice, in this work, we improve upon its performance byutilizing a learning approach to find an adaptive projectionmatrix A from a set of training data. We derive a closed-formformulation for the gradient of the training problem, enablingus to use efficient gradient-based algorithms. We also extend this approach for learning structured projection matrix,such as the sketching matrix that performs as selecting a fewnumber of representative columns from the input data. Ourexperiments on both synthetical and real data show that bothlearned dense and sketch projection matrices outperform therandom ones in finding the approximate orthonormal basisand low-rank approximations.