Sign-Perturbed Sums (SPS) with Instrumental Variables for the Identification of ARX Systems - Extended Version

Valerio Volpe, Balázs Csanád Csáji, Algo Carè, Erik Weyer, Marco C. Campi

Abstract

We propose a generalization of the recently developed system identification method called Sign-Perturbed Sums (SPS). The proposed construction is based on the instrumental variables estimate and, unlike the original SPS, it can construct non-asymptotic confidence regions for linear regression models where the regressors contain past values of the output. Hence, it is applicable to ARX systems, as well as systems with feedback. We show that this approach provides regions with exact confidence under weak assumptions, i.e., the true parameter is included in the regions with a (user-chosen) exact probability for any finite sample. The paper also proves the strong consistency of the method and proposes a computationally efficient generalization of the previously proposed ellipsoidal outer-approximation. Finally, the new method is demonstrated through numerical experiments, using both real-world and simulated data.

Introduction

In system identification, obtaining a point estimate of a system's parameters is often insufficient for safety-critical or high-precision applications. Instead, researchers require confidence regions that quantify the uncertainty of these estimates. Traditional statistical methods typically rely on asymptotic theory, where confidence intervals are only guaranteed to be accurate as the sample size approaches infinity.

This paper introduces a generalized version of the Sign-Perturbed Sums (SPS) method that utilizes Instrumental Variables (IV) to identify parameters in Auto-Regressive with eXogenous input (ARX) systems. While the original SPS method provided exact confidence regions for exogenous systems, it struggled with ARX models where regressors are inherently correlated with past noise. The proposed IV-SPS framework bridges this gap, providing confidence regions with exact probability for any finite sample size, even in systems involving feedback.

Methodology

The IV-SPS Framework

The core innovation lies in integrating Instrumental Variables into the SPS algorithm. By using instruments—variables correlated with the system data but independent of the noise—the authors simplify the mathematical challenges posed by the feedback loops in ARX systems.

The algorithm operates through three primary steps:

  1. Reference and Perturbed Sums: A "reference sum" is constructed from observed data. Simultaneously, $m-1$ "perturbed sums" are generated by randomly flipping the signs of terms using Rademacher variables (±1).
  2. Indicator Function: A parameter $\theta$ is included in the confidence region if its reference sum is not an outlier relative to the distribution of the perturbed sums.
  3. Ellipsoidal Approximation: To avoid the computational burden of grid-searching the parameter space, the authors developed a method to find an ellipsoidal outer bound of the confidence region. This is achieved through Semi-Definite Programming (SDP), allowing for efficient calculation in polynomial time.
Confidence regions for an ARX system, showing the exact SPS region and its ellipsoidal outer approximation.

Experimental Evaluation

The method was validated using both simulated and real-world datasets:

  • Simulated ARX System: A first-order ARX model with $n=25$ data points and Laplacian noise was used to verify the theoretical "exactness" of the confidence regions against known ground truth.
  • Real-World Photovoltaic Data: Using data from an "E+Grid" microgrid prototype, the authors modeled hourly energy production as an ARX(5, 4) system. This test demonstrated the method's robustness in scenarios where the underlying system may not perfectly match the mathematical model and noise characteristics are unknown.

Key Results and Discussion

Theoretical and Empirical Accuracy

The paper provides a formal proof that the probability of the true parameter being contained within the constructed region is exactly $1 - q/m$, where $q$ and $m$ are user-defined integers. Empirical results from the solar data experiment, targeting a 90% confidence level, remained remarkably consistent with theoretical predictions across 1,000 Monte Carlo trials.

Empirical confidence levels for varying sample sizes, demonstrating the method's accuracy near the 90% target.

Consistency and Efficiency

The authors established the strong consistency of the method, proving that as the data volume increases, the confidence region shrinks and converges to the true parameter. Furthermore, the use of the ellipsoidal approximation ensures that these complex regions can be calculated efficiently using standard convex optimization toolboxes like CVX.

Conclusion and Future Work

IV-SPS represents a significant advancement in non-asymptotic system identification. By requiring only weak assumptions—such as independent noise with a symmetric distribution—it offers a robust alternative to Gaussian-dependent methods.

However, some challenges remain. While the regions are asymptotically bounded with probability 1, there is no absolute theoretical guarantee of boundedness for every finite sample. Additionally, the choice of instrumental variables significantly impacts the shape and tightness of the confidence regions. Future research will explore the trade-offs between computational simplicity and the optimization of instrument choice to produce the tightest possible regions.

Summary updated

Abstract

We propose a generalization of the recently developed system identification method called Sign-Perturbed Sums (SPS). The proposed construction is based on the instrumental variables estimate and, unlike the original SPS, it can construct non-asymptotic confidence regions for linear regression models where the regressors contain past values of the output. Hence, it is applicable to ARX systems, as well as systems with feedback. We show that this approach provides regions with exact confidence under weak assumptions, i.e., the true parameter is included in the regions with a (user-chosen) exact probability for any finite sample. The paper also proves the strong consistency of the method and proposes a computationally efficient generalization of the previously proposed ellipsoidal outer-approximation. Finally, the new method is demonstrated through numerical experiments, using both real-world and simulated data.
BibTeX
@inproceedings{volpe2015sign,
  author = {Valerio Volpe and Balázs Csanád Csáji and Algo Carè and Erik Weyer and Marco C. Campi},
  title = {{Sign-Perturbed Sums (SPS) with Instrumental Variables for the Identification of ARX Systems - Extended Version}},
  booktitle = {CDC},
  year = {2015},
  doi = {10.1109/cdc.2015.7402519},
}
Figure