Efficient error and variance estimation for randomized matrix computations

• URL: http://arxiv.org/abs/2207.06342v5
• Date: Tue, 01 Oct 2024 22:19:14 GMT
• Title: Efficient error and variance estimation for randomized matrix computations
• Authors: Ethan N. Epperly, Joel A. Tropp,
• Abstract summary: This paper proposes a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr"om approximation.
• Score: 0.7366405857677227
• License:
• Abstract: Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr\"om approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices.

Related papers

• An In-Depth Examination of Risk Assessment in Multi-Class Classification Algorithms [10.008264048021076]
  We numerically analyze the performance of different methods in solving the risk-assessment problem. Our conformal prediction based approach is model and data-distribution agnostic, simple to implement, and provides reasonable results.
  arXiv  Detail & Related papers  (2024-12-05T14:03:16Z)
• Robust Non-parametric Knowledge-based Diffusion Least Mean Squares over Adaptive Networks [12.266804067030455]
  The proposed algorithm leads to a robust estimation of an unknown parameter vector in a group of cooperative estimators. Results show the robustness of the proposed algorithm in the presence of different noise types.
  arXiv  Detail & Related papers  (2023-12-03T06:18:59Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Algorithme EM r\'egularis\'e [0.0]
  This paper presents a regularized version of the EM algorithm that efficiently uses prior knowledge to cope with a small sample size. Experiments on real data highlight the good performance of the proposed algorithm for clustering purposes.
  arXiv  Detail & Related papers  (2023-07-04T23:19:25Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  Current algorithms are designed using the block coordinate descent method or the proximal point algorithm. We propose a novel algorithm based on the two-metric projection method, incorporating a carefully designed search direction and variable partitioning scheme. Experimental results on synthetic and real-world datasets demonstrate that our proposed algorithm provides a significant improvement in computational efficiency compared to the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-12-03T14:39:10Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  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.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• A Robust Matching Pursuit Algorithm Using Information Theoretic Learning [37.968665739578185]
  A new OMP algorithm is developed based on the information theoretic learning (ITL) The experimental results on both simulated and real-world data consistently demonstrate the superiority of the proposed OMP algorithm in data recovery, image reconstruction, and classification.
  arXiv  Detail & Related papers  (2020-05-10T01:36:00Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.