Towards Faster Matrix Diagonalization with Graph Isomorphism Networks and the AlphaZero Framework

• URL: http://arxiv.org/abs/2407.00779v1
• Date: Sun, 30 Jun 2024 17:45:01 GMT
• Title: Towards Faster Matrix Diagonalization with Graph Isomorphism Networks and the AlphaZero Framework
• Authors: Geigh Zollicoffer, Kshitij Bhatta, Manish Bhattarai, Phil Romero, Christian F. A. Negre, Anders M. N. Niklasson, Adetokunbo Adedoyin,
• Abstract summary: We introduce innovative approaches for accelerating the Jacobi method for matrix diagonalization. We examine the potential of utilizing scalable architecture between different-sized matrices.
• Score: 1.0051474951635875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce innovative approaches for accelerating the Jacobi method for matrix diagonalization, specifically through the formulation of large matrix diagonalization as a Semi-Markov Decision Process and small matrix diagonalization as a Markov Decision Process. Furthermore, we examine the potential of utilizing scalable architecture between different-sized matrices. During a short training period, our method discovered a significant reduction in the number of steps required for diagonalization and exhibited efficient inference capabilities. Importantly, this approach demonstrated possible scalability to large-sized matrices, indicating its potential for wide-ranging applicability. Upon training completion, we obtain action-state probabilities and transition graphs, which depict transitions between different states. These outputs not only provide insights into the diagonalization process but also pave the way for cost savings pertinent to large-scale matrices. The advancements made in this research enhance the efficacy and scalability of matrix diagonalization, pushing for new possibilities for deployment in practical applications in scientific and engineering domains.

Related papers

• Accelerating Matrix Diagonalization through Decision Transformers with Epsilon-Greedy Optimization [1.0051474951635875]
  This paper recasts matrix diagonalization as a sequential decision-making problem and applies the power of Decision Transformers (DTs) Our approach determines optimal pivot selection during diagonalization with the Jacobi algorithm, leading to significant speedups compared to the traditional max-element Jacobi method.
  arXiv  Detail & Related papers  (2024-06-23T18:56:46Z)
• 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)
• Matrix Diagonalization as a Board Game: Teaching an Eigensolver the Fastest Path to Solution [2.239917051803692]
  Matrix diagonalization is at the cornerstone of numerous fields of scientific computing. We show how reinforcement learning, using the AlphaZero framework, can accelerate Jacobi matrix diagonalizations. Our findings highlight the opportunity to use machine learning as a promising tool to improve the performance of numerical linear algebra.
  arXiv  Detail & Related papers  (2023-06-16T03:31:58Z)
• Sufficient dimension reduction for feature matrices [3.04585143845864]
  We propose a method called principal support matrix machine (PSMM) for the matrix sufficient dimension reduction. Our numerical analysis demonstrates that the PSMM outperforms existing methods and has strong interpretability in real data applications.
  arXiv  Detail & Related papers  (2023-03-07T23:16:46Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Symplectic decomposition from submatrix determinants [0.0]
  An important theorem in Gaussian quantum information tells us that we can diagonalise the covariance matrix of any Gaussian state via a symplectic transformation. Inspired by a recently presented technique for finding the eigenvectors of a Hermitian matrix from certain submatrix eigenvalues, we derive a similar method for finding the diagonalising symplectic from certain submatrix determinants.
  arXiv  Detail & Related papers  (2021-08-11T18:00:03Z)
• Projection techniques to update the truncated SVD of evolving matrices [17.22107982549168]
  This paper considers the problem of updating the rank-k truncated Singular Value Decomposition (SVD) of matrices subject to the addition of new rows and/or columns over time. The proposed framework is purely algebraic and targets general updating problems. Results on matrices from real applications suggest that the proposed algorithm can lead to higher accuracy.
  arXiv  Detail & Related papers  (2020-10-13T13:46:08Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)
• 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)
• Controllable Orthogonalization in Training DNNs [96.1365404059924]
  Orthogonality is widely used for training deep neural networks (DNNs) due to its ability to maintain all singular values of the Jacobian close to 1. This paper proposes a computationally efficient and numerically stable orthogonalization method using Newton's iteration (ONI) We show that our method improves the performance of image classification networks by effectively controlling the orthogonality to provide an optimal tradeoff between optimization benefits and representational capacity reduction. We also show that ONI stabilizes the training of generative adversarial networks (GANs) by maintaining the Lipschitz continuity of a network, similar to spectral normalization (
  arXiv  Detail & Related papers  (2020-04-02T10:14:27Z)

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.