An Efficient Algorithm for a Bounded Errors-in-Variables Model

Shiv Chandrasekaran, Gene H. Golub, Ming Gu, Ali H. SayedSIAM J. Matrix Anal. Appl 1999 · DOI

TL;DR

This paper introduces a novel algorithm for parameter estimation in "errors-in-variables" models, where both the data and the model itself can have uncertainties. The key innovation is a method that explicitly accounts for bounded uncertainties in the model parameters, leading to a closed-form solution derived from a secular equation. This approach offers a more robust and less conservative alternative to existing methods like Total Least Squares when dealing with such bounded errors.

What Problem Does This Paper Address?

Parameter estimation is a fundamental task in many scientific and engineering disciplines. A common challenge is the presence of "errors-in-variables" (EIV) models, where not only the measurements (the right-hand side of a linear system) but also the coefficients of the model (the matrix A in Ax=b) are subject to uncertainty. Traditional least-squares methods assume errors only in the measurements. Total Least Squares (TLS) extends this by allowing errors in both the matrix A and the vector b, but it can sometimes lead to overly conservative results by excessively modifying the known parts of the model. This paper addresses the limitation of TLS by introducing a formulation that incorporates an a priori bound on the magnitude of the perturbation to the model matrix A. This allows for a more controlled and potentially less conservative estimation when the uncertainty in A is known to be bounded.

Methods

The authors propose a new optimization problem that minimizes the residual norm subject to a bound on the perturbation to the matrix A. The core of their approach involves:

  • Geometric Interpretation: The problem is first given a geometric interpretation, which helps in understanding the nature of the solution.
  • Equivalent Minimization Problem: The original problem is reformulated into an equivalent minimization problem that involves an "indefinite" metric.
  • Secular Equation: A closed-form solution is derived, which hinges on finding the positive root of a specific secular (nonlinear) equation. This equation arises from the optimization process.
  • Singular Value Decomposition (SVD): The Singular Value Decomposition of the matrix A plays a crucial role in both the theoretical derivation and the practical computation of the solution.
  • Hessian Analysis: The positivity of the Hessian matrix at critical points is analyzed to identify candidates for local minima, ultimately leading to the global minimizer.

The method is presented as an efficient algorithm, with a computational complexity of O(mn² + n³), where n is the smaller matrix dimension.

Datasets

Not discussed in the paper. The paper focuses on the theoretical development of an algorithm for a general linear system with bounded errors-in-variables.

Key Insights and Ideas

  • Bounded Uncertainty is Key: Explicitly incorporating a bound on the perturbation to the model matrix (||δA||₂ ≤ η) leads to a more refined estimation than methods that only bound the overall correction.
  • Secular Equation as the Core: The problem's solution is elegantly tied to finding a root of a derived secular equation, which acts as a "regularization" parameter.
  • Trade-off Between Conservatism and Accuracy: The proposed method offers a way to balance the conservatism of TLS with the need for accurate parameter estimation when uncertainties are bounded.
  • Connection to Robust Estimation: The approach shares similarities with robust estimation techniques (like H∞ filtering) but provides a direct way to handle bounded disturbances.
  • Uniqueness and Degeneracy: The paper carefully analyzes conditions under which a unique solution exists and identifies degenerate cases where the problem might not have a meaningful solution.

Key Results

The paper provides a constructive algorithm for solving the bounded errors-in-variables problem. The main result is a closed-form solution for the parameter vector $\hat{x}$ that is obtained by:

  1. Computing the SVD of the matrix A.
  2. Formulating and solving a secular equation to find a parameter $\alpha$.
  3. Using $\alpha$ to compute $\hat{x}$ via a formula involving A, its SVD, and the vector b.

The algorithm is shown to have a computational complexity of O(mn² + n³). The paper also establishes necessary and sufficient conditions for the existence of a unique solution, relating them to the singular values of A and the input vector b.

Limitations and Future Work

  • Degenerate Cases: The paper acknowledges degenerate cases where the fundamental condition for non-degeneracy is violated, leading to non-unique or ill-posed problems. While these are discussed, the primary focus is on the non-degenerate scenario.
  • Multiple Singular Values: The paper addresses the case of multiple singular values, but the discussion on how to handle them is more complex and relies on techniques similar to the non-multiple case.
  • Extensions: The authors suggest several avenues for future work, including:
  • Weighted versions of the problem with uncertainties in weight matrices.
  • Cases with multiplicative uncertainties.
  • Applications to filtering theory.
  • Further exploration of estimation and control problems with bounded uncertainties.

Summary updated

BibTeX
@article{chandrasekaran1999efficient,
  author = {Shiv Chandrasekaran and Gene H. Golub and Ming Gu and Ali H. Sayed},
  title = {{An Efficient Algorithm for a Bounded Errors-in-Variables Model}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {1999},
  doi = {10.1137/s0895479896304678},
}

Loading related content...

Figure