Generating gradients in the energy landscape using rectified linear type cost functions for efficiently solving 0/1 matrix factorization in Simulated Annealing
This work addresses a computational bottleneck for researchers or practitioners using Simulated Annealing in matrix factorization, but it is incremental as it builds on existing annealing techniques.
The paper tackles the problem of solving 0/1 matrix factorization efficiently in Simulated Annealing by addressing energy landscapes with many plateaus, proposing a method using rectified linear type cost functions to apply gradients and update them during search, with numerical experiments confirming effectiveness on noise-free artificial and real data.
The 0/1 matrix factorization defines matrix products using logical AND and OR as product-sum operators, revealing the factors influencing various decision processes. Instances and their characteristics are arranged in rows and columns. Formulating matrix factorization as an energy minimization problem and exploring it with Simulated Annealing (SA) theoretically enables finding a minimum solution in sufficient time. However, searching for the optimal solution in practical time becomes problematic when the energy landscape has many plateaus with flat slopes. In this work, we propose a method to facilitate the solution process by applying a gradient to the energy landscape, using a rectified linear type cost function readily available in modern annealing machines. We also propose a method to quickly obtain a solution by updating the cost function's gradient during the search process. Numerical experiments were conducted, confirming the method's effectiveness with both noise-free artificial and real data.