An Optimization Network for Matrix Inversion

Ju-Seog Jang, Soo-Young Lee, Sang-Yung ShinNeurIPS 1987

TL;DR This foundational 1988 paper introduces an analog neural network based on the Hopfield model, specifically designed to perform matrix inversion and solve linear equations. By framing matrix inversion as an energy minimization problem, the authors demonstrate a hardware-efficient approach that offers massive parallelism, high-speed convergence, and surprising robustness against hardware imperfections.

The Challenge of Matrix Inversion

Matrix inversion is a fundamental operation in science and engineering, but it is computationally expensive. Standard digital algorithms, such as Gauss-Jordan elimination, scale at $O(n^3)$ and are typically executed sequentially.

In the late 1980s, researchers explored "collective computation"—using interconnected analog processors to solve complex tasks faster than traditional CPUs. The core challenge addressed in this paper is whether the dissipative dynamics of a neural network (where a physical system naturally "settles" into a state of minimum energy) can be harnessed to find the inverse of a matrix $A$ or solve the simultaneous equation $Ax=b$ in real-time.

Methods: Inversion via Optimization

The authors adapt the Hopfield neural network model to the task of mathematical optimization. Their approach follows a physics-based methodology:

  1. Energy Function Construction: They define a set of energy functions ($E_k$) where the global minimum (zero) corresponds exactly to the elements of the inverse matrix $V = A^{-1}$.
  2. Gradient Descent Dynamics: The network is designed such that the time derivative of the neurons' input voltages follows the negative gradient of the energy function. Essentially, the circuit "rolls down the hill" of the energy hyperspace until it reaches the bottom.
  3. Hardware Implementation: Unlike a digital simulation, the authors built an actual electronic circuit using analog processors (neurons), summers, and integrators.
  4. Coupling Coefficients: They pre-calculate coupling coefficients ($T_{ij}$) based on the input matrix $A$. Interestingly, $T_{ij}$ is independent of which column of the inverse is being calculated, allowing the same hardware to be reused efficiently.
Analog neural network circuit diagram for matrix inversion.

Key Insights

  • Inversion as Optimization: The breakthrough concept is treating an algebraic identity ($AV=I$) as a topological landscape where the correct answer is the lowest point. This allows the system to rely on physics-based convergence rather than step-by-step algorithmic logic.
  • Robustness to Component Variation: A significant finding is that the exact "shape" or steepness of the neurons' activation functions ($g_{ik}$) does not affect the final accuracy for nonsingular matrices. It only alters the speed at which the network converges. This is vital for analog hardware, where manufacturing variances mean no two transistors or resistors are perfectly identical.
  • Handling Singular Matrices: Standard digital algorithms often fail or require complex branching logic when a matrix is singular (non-invertible). This neural network naturally converges to a "least-squares" optimal solution, providing the best possible approximation without crashing.
  • Reusable Interconnects: Because the coupling matrix $T$ is derived from $A^T A$, the same set of hardware connections can be used to solve for every column of the inverse matrix, significantly reducing the required hardware complexity.

Experimental Results

The network converges to a solution within a few "characteristic time constants" of the circuit. In an analog system, this is near-instantaneous compared to digital iterations. Furthermore, the authors argue that while standard methods take $O(8n^3/3)$ operations, their approach only requires $O(n^3/2)$ operations to set up the coupling coefficients, after which the physics of the circuit takes over.

To validate the theory, the authors tested a $3 \times 3$ matrix using their hardware implementation. The hardware output matched the calculated inverse $A^{-1}$ with high fidelity (e.g., a theoretical value of 1.00 was measured as 0.99).

Oscilloscope traces showing the hardware output voltages corresponding to the calculated inverse matrix.

Limitations and Future Work

Despite its speed, the approach has inherent limitations:

  • Analog Precision: Calculation accuracy is limited by the nature of analog computation, including thermal noise, component tolerances, and measurement limits. It cannot replace high-precision double-floating-point digital math for applications requiring exactness.
  • Scaling the Interconnects: For a matrix of size $n$, the system requires $n^2$ interconnections. For very large matrices, wiring this electronically becomes a severe physical bottleneck. The authors suggest that optoelectronic devices—using light to represent connections—could be the key to scaling this architecture to larger systems.
  • Setup Cost: While the network solves the problem rapidly once initialized, calculating the $T_{ij}$ coefficients still requires an initial matrix-matrix multiplication, which remains a computational prerequisite.

Summary updated

BibTeX
@inproceedings{jang1987optimization,
  author = {Ju-Seog Jang and Soo-Young Lee and Sang-Yung Shin},
  title = {{An Optimization Network for Matrix Inversion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1987},
}
Figure