BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions

• URL: http://arxiv.org/abs/2505.12289v1
• Date: Sun, 18 May 2025 08:04:05 GMT
• Title: BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions
• Authors: Kingsley Yeon, Promit Ghosal, Mihai Anitescu,
• Abstract summary: In many large-scale applications, the matrices involved are too large to store or access in full, making a single mat-vec product infeasible.<n>We introduce Subblock SLQ, a variant of BOLT that operates only on small principal submatrices.<n>We provide theoretical guarantees and demonstrate strong empirical performance across a range of high-dimensional settings.
• Score: 2.4578723416255754
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient matrix trace estimation is essential for scalable computation of log-determinants, matrix norms, and distributional divergences. In many large-scale applications, the matrices involved are too large to store or access in full, making even a single matrix-vector (mat-vec) product infeasible. Instead, one often has access only to small subblocks of the matrix or localized matrix-vector products on restricted index sets. Hutch++ achieves optimal convergence rate but relies on randomized SVD and assumes full mat-vec access, making it difficult to apply in these constrained settings. We propose the Block-Orthonormal Stochastic Lanczos Quadrature (BOLT), which matches Hutch++ accuracy with a simpler implementation based on orthonormal block probes and Lanczos iterations. BOLT builds on the Stochastic Lanczos Quadrature (SLQ) framework, which combines random probing with Krylov subspace methods to efficiently approximate traces of matrix functions, and performs better than Hutch++ in near flat-spectrum regimes. To address memory limitations and partial access constraints, we introduce Subblock SLQ, a variant of BOLT that operates only on small principal submatrices. As a result, this framework yields a proxy KL divergence estimator and an efficient method for computing the Wasserstein-2 distance between Gaussians - both compatible with low-memory and partial-access regimes. We provide theoretical guarantees and demonstrate strong empirical performance across a range of high-dimensional settings.

Related papers

• Rigorous Maximum Likelihood Estimation for Quantum States [2.5782420501870296]
  Existing quantum state tomography avoids rigorous termination of limited scalability due to their high computation and memory demands.<n>In this paper, we address these limitations by reforming a matrix by a factor.<n>We show that our method can demonstrate a laptop-of-the-art solution to state-of-the-art problems in under 5 hours.
  arXiv  Detail & Related papers  (2025-06-19T23:18:50Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  Non-stationary multi-block bilevel optimization problems involve $mgg 1$ lower level problems and have important applications in machine learning. We aim to achieve three properties for our algorithm: a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ samples for each sampled block per-iteration; and (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator.
  arXiv  Detail & Related papers  (2023-05-30T04:10:11Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  We show that the first optimality gap of the proposed algorithm decays at the rate of the expected loss for various methods under nontens dependent data setting. We obtain first convergence point for various methods under nontens dependent data setting.
  arXiv  Detail & Related papers  (2022-01-05T15:17:35Z)
• Learning a Compressive Sensing Matrix with Structural Constraints via Maximum Mean Discrepancy Optimization [17.104994036477308]
  We introduce a learning-based algorithm to obtain a measurement matrix for compressive sensing related recovery problems. Recent success of such metrics in neural network related topics motivate a solution of the problem based on machine learning.
  arXiv  Detail & Related papers  (2021-10-14T08:35:54Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm [0.3867363075280543]
  Recovery of an unknown sparse signal from a few of its projections is the key objective of compressed sensing. Existing block sparse recovery algorithms like BOMP make the assumption of uniform block size and known block boundaries. This paper proposes a two step procedure, where the first stage is a coarse block location identification stage. The second stage carries out finer localization of a non-zero cluster within the window selected in the first stage.
  arXiv  Detail & Related papers  (2020-08-18T17:00:55Z)
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data [0.0]
  smoothness of the subdiagonals of the Cholesky factor of large covariance matrices is closely related to the degrees of nonstationarity of autoregressive models for time series and longitudinal data. We propose an algorithm for sparse estimation of the Cholesky factor which decouple row-wise.
  arXiv  Detail & Related papers  (2020-07-22T02:38:16Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

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.