Energy-Based Adaptive CUR Matrix Decomposition

Abstract

CUR decompositions are interpretable data analysis tools that express a data matrix in terms of a small number of actual columns and/or actual rows of the data matrix. One bottleneck of existing relative-error CUR algorithms lies on high computational complexity for computing important sampling probabilities. In this paper, we provide a simple yet effective framework that considers energy-based sampling algorithm. On one hand, we provide an intuitive and fast relative-error sampling algorithm for column selection problem. On the other hand, by combining the relative-error sampling algorithm with adaptive sampling algorithm we provide a novel CUR matrix approximation algorithms which is referred to as energy-based adaptive sampling algorithm. The sampling algorithm is the first adaptive relative-error CUR decomposition in the coherent sense. Specially, in each stage of our algorithm, we sample columns or rows from data matrix using sampling probabilities that are directly proportional to Euclidean norms of the columns or rows of the original data and residual matrix, respectively. Our empirical results exactly indicate that the new adaptive sampling algorithm typically achieves a good balance between computational complexity and approximate accuracy.

Keywords

• Randomized algorithm
• CUR decomposition
• subsampling
• energy sampling