What Investors and AI Researchers Can Learn from Low-Rank Optimization

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

E. Low Rank Approximation for Portfolio Optimization

Low-rank matrices can arise during the construction of securities portfolios in financial analytics. Specifically, the optimal portfolio is the solution to a model-dependent quadratic unconstrained mixed optimization (QUMO) problem. Under an equal-weighting constraint, which we will explain below, this transforms into a quadratic unconstrained binary optimization (QUBO) problem that SPIMs can solve. Portfolio optimization involves creating an investment portfolio that balances risk and return. The objective is to allocate assets yi optimally to maximize expected returns µ while minimizing risk φ. In modern portfolio theory, this problem is formulated in the Markowitz mean-variance optimization model [43– 45] with the objective function:

For a quadratic unconstrained continuous optimization problem, if the coupling matrix is positive semi-definite as the covariance matrix is, then the problem is convex for any linear field term. However, for QUBO problems, even if S and hence J is positive semi-definitive, the problem is not necessarily easy to solve. The reason is that the binary constraint makes the feasible region discrete, not convex, which is why QUBO problems are generally NP-hard. SPIMs derive a temporal advantage over classical computing due to optical hardware implementing fast and energy-efficient computation. This is particularly crucial in high-frequency trading, where optimal portfolios must be calculated over microseconds to minimize latency in placing orders [54, 55].

F. Low-Rank Matrices in Restricted Boltzmann Machines

In Section III A, we mentioned that the minimum rank of a weighted complete bipartite graph is 2. The restricted Boltzmann machine (RBM) [56, 57] is a computational model naturally defined on complete bipartite graphs. Thus, it is sensible to consider encoding low-rank approximations of RBMs within the SPIM paradigm.

Previous studies have shown that RBMs can provide good results when trained with low-rank approximations for collaborative filtering [58]. Recent advancements have explored low-rank approximations in unrestricted Boltzmann machines (UBMs). Notably, UBMs trained on Spatial Photonic Ising Machine (SPIM) based optical hardware have demonstrated promising results. This novel approach leverages the computational power of optical systems for machine learning tasks, offering significant performance improvements [25].

Although UBMs might offer greater modeling flexibility due to their unrestricted connectivity, they suffer significant computational downsides. Each step in the UBM training algorithm involves navigating a complex energy landscape, leading to inefficient convergence. This inefficiency is particularly problematic for large-dimensional datasets, where training time and computational resources can become prohibitively high [25].

In contrast, RBMs can be framed as minimal rank problems. Their bipartite nature simplifies the training process and reduces computational complexity, making them more practical for SPIM applications. The training efficiency of RBMs was significantly enhanced by Hinton’s method of minimizing contrastive divergence, which simplified the optimization of these models [57]. This minimal rank framework suggests that RBMs can be trained more efficiently, so they are often preferred for collaborative filtering and feature learning tasks. The theoretical foundations of harmony theory, laid out by Smolensky in 1986 [56], underpin the information processing capabilities of both RBMs and UBMs.

In general, RBMs, exhibiting lower computational demands, are valuable tools in machine learning. Recent research demonstrating the efficacy of low-rank UBMs on SPIM hardware [25] indicates that low-rank RBMs could be a promising direction for future applications of SPIM devices.

x