Sign-Perturbed Sums: A New System Identification Approach for Constructing Exact Non-Asymptotic Confidence Regions in Linear Regression Models

Balázs Csanád Csáji, Marco C. Campi, Erik WeyerIEEE TSP 2015 · DOI · OpenReview

Abstract

This paper introduces Sign-Perturbed Sums (SPS), a novel method for constructing exact non-asymptotic confidence regions for parameters in linear regression models. While standard approaches rely on asymptotic theory—assuming Gaussian error distributions as sample sizes approach infinity—SPS provides rigorous guarantees for any finite sample size. The method requires only that system noise be independent and symmetric. We show that SPS regions are star-convex, centered on the least-squares estimate, and can be efficiently bounded by ellipsoidal approximations, offering a robust alternative to traditional heuristic regions in system identification.

Introduction

In system identification and machine learning, point estimates of parameters are often insufficient; practitioners require confidence regions to quantify uncertainty. Traditional methods for constructing these regions typically rely on asymptotic theory, which assumes that estimation errors follow a Gaussian distribution as the dataset size grows to infinity. However, for small or finite datasets, these heuristic regions can be misleading and lack strict theoretical guarantees.

Previous attempts to address this, such as the Leave-out Sign-dominant Correlation Regions (LSCR) method, faced challenges with multidimensional parameters or failed to ensure that the standard Least-Squares Estimate (LSE) was included within the confidence region. Sign-Perturbed Sums (SPS) addresses these gaps by providing a distribution-free method that is exact for any sample size, includes the LSE, and scales to multidimensional systems.

Methodology

The core of the SPS approach is a sign-perturbation mechanism applied to the normal equations of standard Least Squares. The process involves four primary steps:

  1. Reference Sum Definition: A "reference sum" is defined based on the prediction errors of a candidate parameter $\theta$.
  2. Sign Flipping: $m-1$ "perturbed" versions of this sum are created by randomly flipping the signs ($\pm 1$) of the terms.
  3. Statistical Ranking: If $\theta$ is the true parameter, the reference sum and the perturbed sums share the same distribution and are statistically indistinguishable.
  4. Indicator Function: A candidate $\theta$ is included in the confidence region if its reference sum ranks among the smallest $m-q$ sums. The probability that the true parameter lies within this region is exactly $1 - q/m$.

To overcome the computational "curse of dimensionality" when checking candidate parameters in high-dimensional space, the authors introduce an Ellipsoidal Outer Approximation. This convex optimization-based algorithm identifies a tight ellipsoid that encapsulates the SPS region, ensuring practical utility.

Key Results and Discussion

The authors evaluated SPS across various simulated scenarios, including second-order FIR systems, heavy-tailed (Laplacian) noise, and undermodelled systems.

Small Sample Performance

One of the most significant advantages of SPS is its reliability with small datasets. In simulations with only 25 data points, SPS regions maintained their 95% theoretical guarantee. In contrast, traditional asymptotic regions remained purely heuristic and potentially inaccurate in this regime.

95% confidence regions for a small sample size (n=25).

Convergence and Efficiency

As the sample size increases, the SPS regions align more closely with traditional optimal regions if the noise is Gaussian, yet they maintain their exactness regardless of the noise distribution. For a system with 3,200 data points, the ellipsoidal approximation was computed in approximately 23 seconds on a standard laptop, demonstrating its feasibility for real-world engineering tasks.

95% confidence regions for a larger sample size (n=400).

Conclusion

SPS represents a significant advancement in system identification by providing exact, non-asymptotic confidence regions with minimal assumptions. The method's star-convexity ensures it is well-behaved around the LSE, and the "block" strategy allows for adaptation to correlated noise. Future work will focus on extending these guarantees to closed-loop systems where inputs depend on past noise, a non-trivial challenge for current exact methods.

Summary updated

Abstract

We propose a new system identification method, called Sign-Perturbed Sums (SPS), for constructing non-asymptotic confidence regions under mild statistical assumptions. SPS is introduced for linear regression models, including but not limited to FIR systems, and we show that the SPS confidence regions have exact confidence probabilities, i.e., they contain the true parameter with a user-chosen exact probability for any finite data set. Moreover, we also prove that the SPS regions are star convex with the Least-Squares (LS) estimate as a star center. The main assumptions of SPS are that the noise terms are independent and symmetrically distributed about zero, but they can be nonstationary, and their distributions need not be known. The paper also proposes a computationally efficient ellipsoidal outer approximation algorithm for SPS. Finally, SPS is demonstrated through a number of simulation experiments.
BibTeX
@article{csaji2015sign,
  author = {Balázs Csanád Csáji and Marco C. Campi and Erik Weyer},
  title = {{Sign-Perturbed Sums: A New System Identification Approach for Constructing Exact Non-Asymptotic Confidence Regions in Linear Regression Models}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  doi = {10.1109/tsp.2014.2369000},
}
Figure