Volume 2, Issue 4
Solving the $k$-Sparse Eigenvalue Problem with Reinforcement Learning

Li Zhou, Lihao Yan, Mark A. Caprio, Weiguo Gao & Chao Yang

CSIAM Trans. Appl. Math., 2 (2021), pp. 697-723.

Published online: 2021-11

Export citation
  • Abstract

We examine the possibility of using a reinforcement learning (RL) algorithm to solve large-scale eigenvalue problems in which the desired the eigenvector can be approximated by a sparse vector with at most $k$ nonzero elements, where $k$ is relatively small compare to the dimension of the matrix to be partially diagonalized. This type of problem arises in applications in which the desired eigenvector exhibits localization properties and in large-scale eigenvalue computations in which the amount of computational resource is limited. When the positions of these nonzero elements can be determined, we can obtain the $k$-sparse approximation to the original problem by computing the eigenvalue of a $k×k$ submatrix extracted from $k$ rows and columns of the original matrix. We review a previously developed greedy algorithm for incrementally probing the positions of the nonzero elements in a $k$-sparse approximate eigenvector and show that the greedy algorithm can be improved by using an RL method to refine the selection of $k$ rows and columns of the original matrix. We describe how to represent states, actions, rewards and policies in an RL algorithm designed to solve the $k$-sparse eigenvalue problem and demonstrate the effectiveness of the RL algorithm on two examples originating from quantum many-body physics.

  • Keywords

Large-scale eigenvalue problem, quantum many-body problem, eigenvector localization, reinforcement learning, approximate $Q$-learning, stochastic sampling, high performance computing.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-2-697, author = { and Li Zhou and and 21498 and and Li Zhou and and Lihao Yan and and 21499 and and Lihao Yan and and Mark A. Caprio and and 21500 and and Mark A. Caprio and and Weiguo Gao and and 21501 and and Weiguo Gao and Chao and Yang and and 21502 and and Chao Yang}, title = {Solving the $k$-Sparse Eigenvalue Problem with Reinforcement Learning}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2021}, volume = {2}, number = {4}, pages = {697--723}, abstract = {

We examine the possibility of using a reinforcement learning (RL) algorithm to solve large-scale eigenvalue problems in which the desired the eigenvector can be approximated by a sparse vector with at most $k$ nonzero elements, where $k$ is relatively small compare to the dimension of the matrix to be partially diagonalized. This type of problem arises in applications in which the desired eigenvector exhibits localization properties and in large-scale eigenvalue computations in which the amount of computational resource is limited. When the positions of these nonzero elements can be determined, we can obtain the $k$-sparse approximation to the original problem by computing the eigenvalue of a $k×k$ submatrix extracted from $k$ rows and columns of the original matrix. We review a previously developed greedy algorithm for incrementally probing the positions of the nonzero elements in a $k$-sparse approximate eigenvector and show that the greedy algorithm can be improved by using an RL method to refine the selection of $k$ rows and columns of the original matrix. We describe how to represent states, actions, rewards and policies in an RL algorithm designed to solve the $k$-sparse eigenvalue problem and demonstrate the effectiveness of the RL algorithm on two examples originating from quantum many-body physics.

}, issn = {2708-0579}, doi = {https://doi.org/10.4208/csiam-am.2020-0220}, url = {http://global-sci.org/intro/article_detail/csiam-am/19989.html} }
TY - JOUR T1 - Solving the $k$-Sparse Eigenvalue Problem with Reinforcement Learning AU - Li Zhou , AU - Lihao Yan , AU - Mark A. Caprio , AU - Weiguo Gao , AU - Yang , Chao JO - CSIAM Transactions on Applied Mathematics VL - 4 SP - 697 EP - 723 PY - 2021 DA - 2021/11 SN - 2 DO - http://doi.org/10.4208/csiam-am.2020-0220 UR - https://global-sci.org/intro/article_detail/csiam-am/19989.html KW - Large-scale eigenvalue problem, quantum many-body problem, eigenvector localization, reinforcement learning, approximate $Q$-learning, stochastic sampling, high performance computing. AB -

We examine the possibility of using a reinforcement learning (RL) algorithm to solve large-scale eigenvalue problems in which the desired the eigenvector can be approximated by a sparse vector with at most $k$ nonzero elements, where $k$ is relatively small compare to the dimension of the matrix to be partially diagonalized. This type of problem arises in applications in which the desired eigenvector exhibits localization properties and in large-scale eigenvalue computations in which the amount of computational resource is limited. When the positions of these nonzero elements can be determined, we can obtain the $k$-sparse approximation to the original problem by computing the eigenvalue of a $k×k$ submatrix extracted from $k$ rows and columns of the original matrix. We review a previously developed greedy algorithm for incrementally probing the positions of the nonzero elements in a $k$-sparse approximate eigenvector and show that the greedy algorithm can be improved by using an RL method to refine the selection of $k$ rows and columns of the original matrix. We describe how to represent states, actions, rewards and policies in an RL algorithm designed to solve the $k$-sparse eigenvalue problem and demonstrate the effectiveness of the RL algorithm on two examples originating from quantum many-body physics.

Li Zhou, Lihao Yan, Mark A. Caprio, Weiguo Gao & Chao Yang. (2021). Solving the $k$-Sparse Eigenvalue Problem with Reinforcement Learning. CSIAM Transactions on Applied Mathematics. 2 (4). 697-723. doi:10.4208/csiam-am.2020-0220
Copy to clipboard
The citation has been copied to your clipboard