Conference proceeding
An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
Proceedings of Machine Learning Research, Vol.37
International Conference on Machine Learning (Lille, France, 07/07/2015 - 07/09/2015)
2015
Abstract
In this paper, we consider the problem of column subset selection. We present a novel analysis of the spectral norm reconstruction for a simple randomized algorithm and establish a new bound that depends explicitly on the sampling probabilities. The sampling dependent error bound (i) allows us to better understand the tradeoff in the reconstruction error due to sampling probabilities, (ii) exhibits more insights than existing error bounds that exploit specific probability distributions, and (iii) implies better sampling distributions. In particular, we show that a sampling distribution with probabilities proportional to the square root of the statistical leverage scores is better than uniform sampling, and is better than leverage-based sampling when the statistical leverage scores are very nonuniform. And by solving a constrained optimization problem related to the error bound with an efficient bisection search we are able to achieve better performance than using either the leverage-based distribution or that proportional to the square root of the statistical leverage scores. Numerical simulations demonstrate the benefits of the new sampling distributions for low-rank matrix approximation and least square approximation compared to state-of-the art algorithms.
Details
- Title: Subtitle
- An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
- Creators
- Tianbao YangLijun ZhangRong JinShenghuo Zhu
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research, Vol.37
- Conference
- International Conference on Machine Learning (Lille, France, 07/07/2015 - 07/09/2015)
- Language
- English
- Date published
- 2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259418502771
Metrics
5 Record Views