New Subset Selection Algorithms for Low Rank Approximation: Offline and Online

Subset selection for the rank k approximation of an n× d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In sharp contrast, when the error measure is replaced by other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the standard offline setting. We give a number of results towards closing these gaps.