Two Iterative Algorithms for Computing the Singular Value Decomposition from Input/Output Samples

Terence D. SangerNeurIPS 1993

Introduction

This paper introduces two neural-network-inspired iterative algorithms designed to compute the Singular Value Decomposition (SVD) of a system without requiring prior knowledge of the system's internal matrix. By observing only input/output pairs, these algorithms can "learn" the underlying structure of a linear system. This capability makes them highly suitable for real-time control and signal processing in unknown or dynamically changing environments.

The Problem: SVD for "Black Box" Systems

The Singular Value Decomposition is a cornerstone of linear algebra, widely used to invert matrices, reduce noise, and identify the most important "modes" of a system. Traditionally, computing an SVD requires full access to the matrix in question.

However, in fields like robotics or biological motor control, systems often operate as a "black box" (a plant). We can observe the inputs ($u$) and the outputs ($y$), but the internal matrix $P$ remains unknown. While algorithms exist to find eigenvectors for symmetric matrices from sample data, this paper tackles a significantly harder challenge: finding the SVD for arbitrary, non-square, and unknown matrices using only sample input/output data.

Proposed Methods

The author proposes two distinct iterative approaches to solve this problem:

1. Double Generalized Hebbian Algorithm (DGHA)

This approach uses two coupled difference equations. The first part employs the Generalized Hebbian Algorithm (GHA) to find the left singular vectors by analyzing the autocorrelation of the outputs ($y$). The second part uses an orthogonalized version of the Widrow-Hoff LMS rule to find the right singular vectors.

Essentially, DGHA attempts to invert the system by training two separate linear networks ($N$ and $G$) such that their combination approximates the inverse of the plant.

Architecture of the Double Generalized Hebbian Algorithm (DGHA) using GHA update rules.

2. Orthogonal Asymmetric Encoder (OAE)

This method frames the task as a variation of a neural network "encoder" problem. It uses Backpropagation to train a three-layer network to approximate the forward mapping of the plant ($u \to y$) through a narrow "bottleneck" layer.

The "orthogonal" aspect comes from a specific constraint that forces the hidden units to be uncorrelated. This ensures that the network doesn't just learn any arbitrary mapping, but specifically extracts the singular vectors in order of importance.

Architecture of the Orthogonal Asymmetric Encoder (OAE) utilizing Backpropagation.

Key Insights: Output-Driven vs. Mapping-Driven

A critical distinction between the two algorithms lies in how they process information:

  • DGHA is "output-driven." It learns based on the variance of the output $y$. While this makes it fast, it is also vulnerable; if the output contains significant noise that didn't originate from the input, DGHA will mistakenly attempt to model that noise.
  • OAE is "mapping-driven." It specifically looks for the relationship between $u$ and $y$. Because it only models the part of the output that can be predicted by the input, it is naturally robust to additive output noise.

The iterative nature of both algorithms also suggests biological plausibility—they could serve as models for how animals learn to control their limbs or process sensory information without a pre-programmed mathematical model of their bodies.

Experimental Results

The algorithms were tested using synthetic experimental setups featuring randomly selected $3 \times 3$ and $10 \times 10$ plant matrices ($P$). To test robustness, the author also introduced 50% additive noise (SNR of 1.0) to the outputs.

  • Convergence: Both algorithms successfully converged to the correct singular vectors. In simulations, the "Diagonalization Score" (a measure of error) dropped significantly within a few hundred samples.
  • Noise Robustness: The OAE algorithm proved highly effective even with 50% additive noise. It successfully ignored the random noise and extracted the underlying linear transformation between input and output.
  • Efficiency: Unlike some previous methods that required learning one component at a time, the OAE allows all singular value components to be learned simultaneously in parallel.

Limitations and Future Work

While promising, the methods have distinct limitations. The author explicitly notes that DGHA performs poorly if the system has significant "uncontrollable modes" or autonomous noise, as it cannot distinguish between system-generated output and external interference.

Furthermore, while iterative, the OAE requires a backpropagation-style update and a specific multiplication by $S^{-2}$ to compute a true plant inverse, which might introduce computational overhead in certain hardware implementations. Finally, the current paper focuses strictly on linear systems; extending these sample-based SVD concepts to non-linear manifolds remains a broader challenge for future research.

Summary updated

BibTeX
@inproceedings{sanger1993two,
  author = {Terence D. Sanger},
  title = {{Two Iterative Algorithms for Computing the Singular Value Decomposition from Input/Output Samples}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure