Low-Rank Approximation of Random Coupling Matrices

Table of Links

I. Introduction

II. Spim Performance, Advantages and Generality

III. Inherently Low Rank Problems

A. Properties of Low Rank Graphs

B. Weakly NP-Complete Problems and Hardware Precision Limitation

C. Limitation of Low Rank Matrix Mapping

IV. Low Rank Approximation

A. Decomposition of Target Coupling Matrix

B. How Fields Influence Ran

C. Low Rank Approximation of Coupling Matrices

D. Low-Rank Approximation of Random Coupling Matrices

E. Low Rank Approximation for Portfolio Optimization

F. Low-Rank Matrices in Restricted Boltzmann Machines

V. Constrained Number Partitioning Problem

A. Definition and Characteristics of the Constrained Number Partitioning Problem

B. Computational Hardness of Random CNP Instances

VI. Translation Invariant Problems

A. “Realistic” Spin Glass

B. Circulant Graphs

VII. Conclusions, Acknowledgements, and References

D. Low-Rank Approximation of Random Coupling Matrices

Figure 1 compares the quality of solutions obtained using varying values of K and L. Figures 1(a) and (b) show results from the low-rank, limited-precision approximation of a random 1000-vertex unweighted connectivity graph, where each pair of vertices has an equal probability of being connected or unconnected. Figures 1(c) and (d) show results from a sparse 3-regular random graph, where each vertex is connected to 3 other random vertices. From Figs. 1(a) and (c), we observe that the quality of solutions obtained from 8-bit precision approximations is indistinguishable from solutions obtained from full-precision calculations, regardless of the rank of the approximate coupling matrix. This suggests that SPIM can still find highly accurate approximate solutions to

Ising problems with both dense and sparse coupling matrices, even with limited precision.

This observation is further supported by Figs. 1(b) and (d). It can be seen that with at least 6 bits of precision, SPIM can find low-energy solutions comparable to those found by full-precision machines using the same algorithm. However, the loss of accuracy is more pronounced in dense graphs than in sparse graphs.

highly dependent on the rank of the approximated coupling matrix. In both dense and sparse graphs, the energy of the approximate solution increases rapidly as the rank of the approximate coupling matrix decreases. Therefore, for a general random matrix, the precision of the Mattis-type matrices is not a significant factor in the quality of the approximate solution, but the rank of the approximate matrix is. The dependence on rank is likely to limit the efficiency of SPIM hardware on random Ising problems because the computation of Ising energy contributions from each rank-1 component by SPIM must be time-multiplexed, leading to much longer computation times per iteration.

In Section IV E, we discuss a practical application in finance where a low-rank matrix can often approximate the matrix in question, making it suitable for implementhe matrix in question, making it suitable for implementation in SPIM hardware.