Reduced Heteroscedasticity Linear Regression for Nyström Approximation

Hao Yang, Jianxin WuIJCAI 2013 · OpenReview

Abstract

The Nystrom method is a well known sampling based low-rank matrix approximation approach. It is usually considered to be originated from the numerical treatment of integral equations and eigendecomposition of matrices. In this paper, we present a novel point of view for the Nystrom approximation. We show that theoretically the Nystrom method can be regraded as a set of point-wise ordinary least square linear regressions of the kernel matrix, sharing the same design matrix. With the new interpretation, we are able to analyze the approximation quality based on the fulfillment of the homoscedasticity assumption and explain the success and deficiency of various sampling methods. We also empirically show that positively skewed explanatory variable distributions can lead to heteroscedasticity. Based on this discovery, we propose to use non-symmetric explanatory functions to improve the quality of the Nystrom approximation with almost no extra computational cost. Experiments show that positively skewed datasets widely exist, and our method exhibits good improvements on these datasets.
BibTeX
@inproceedings{yang2013reduced,
  author = {Hao Yang and Jianxin Wu},
  title = {{Reduced Heteroscedasticity Linear Regression for Nyström Approximation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=Sy-fkBfOZB},
}

Loading related content...

Figure