Max-plus statistical leverage scores
The statistical leverage scores of a complex matrix $A\in\mathbb{C}^{n\times d}$ record the degree of alignment between col$(A)$ and the coordinate axes in $\mathbb{C}^n$. These score are used in random sampling algorithms for solving certain numerical linear algebra problems. In this paper we present a max-plus algebraic analogue for statistical leverage scores. We show that max-plus statistical leverage scores can be used to calculate the exact asymptotic behavior of the conventional statistical leverage scores of a generic matrices of Puiseux series and also provide a novel way to approximate the conventional statistical leverage scores of a fixed or complex matrix. The advantage of approximating a complex matrices scores with max-plus scores is that the max-plus scores can be computed very quickly. This approximation is typically accurate to within an order or magnitude and should be useful in practical problems where the true scores are known to vary widely.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
ALEVS: Active Learning by Statistical Leverage Sampling
Active learning aims to obtain a classifier of high accuracy by using fewer label requests in comparison to passive learning by selecting effective queries. Many active learning methods have been developed in the past tw…
Active LearningBinary ClassificationInformativenessActive Learning Methods based on Statistical Leverage Scores
In many real-world machine learning applications, unlabeled data are abundant whereas class labels are expensive and scarce. An active learner aims to obtain a model of high accuracy with as few labeled instances as poss…
Active LearningFast Statistical Leverage Score Approximation in Kernel Ridge Regression
Nystr\"om approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems through sub-sampling the n-by-n empirical kernel matrix appearing in the objective function. However, the per…
regressionAn Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
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 th…
A statistical perspective of sampling scores for linear regression
In this paper, we consider a statistical problem of learning a linear model from noisy samples. Existing work has focused on approximating the least squares solution by using leverage-based scores as an importance sampli…
regression