Estimating leverage scores via rank revealing methods and randomization
We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms. We first develop a set of fast novel algorithms for rank estimation, column subset selection and least squares preconditioning. We then describe the design and implementation of leverage score estimators based on these primitives. These estimators are also effective for rank deficient input, which is frequently the case in data analytics applications. We provide detailed complexity analyses for all algorithms as well as meaningful approximation bounds and comparisons with the state-of-the-art. We conduct extensive numerical experiments to evaluate our algorithms and to illustrate their properties and performance using synthetic and real world data sets.
Code (1)
Tasks
Dimensionality ReductionSimilar Papers 제목 키워드 기반
The ICML 2023 Ranking Experiment: Examining Author Self-Assessment in ML/AI Peer Review
We conducted an experiment during the review process of the 2023 International Conference on Machine Learning (ICML), asking authors with multiple submissions to rank their papers based on perceived quality. In total, we…
Multivariate Conformal Prediction using Optimal Transport
Conformal prediction (CP) quantifies the uncertainty of machine learning models by constructing sets of plausible outputs. These sets are constructed by leveraging a so-called conformity score, a quantity computed using …
Conformal PredictionPredictionImproving Relevance Quality in Product Search using High-Precision Query-Product Semantic Similarity
Ensuring relevance quality in product search is a critical task as it impacts the customer’s ability to find intended products in the short-term as well as the general perception and trust of the e-commerce system in the…
Re-RankingSemantic SimilaritySemantic Textual SimilarityHow to Estimate Model Transferability of Pre-Trained Speech Models?
In this work, we introduce a "score-based assessment" framework for estimating the transferability of pre-trained speech models (PSMs) for fine-tuning target tasks. We leverage upon two representation theories, Bayesian …
Generalized Leverage Scores: Geometric Interpretation and Applications
In problems involving matrix computations, the concept of leverage has found a large number of applications. In particular, leverage scores, which relate the columns of a matrix to the subspaces spanned by its leading si…