TL;DR
This paper introduces and analyzes "nonnegative input" induced norms ($L_p^+$) for linear systems, which are crucial for understanding systems with inherent positivity constraints (like those found in biological or economic models). The authors develop novel computational methods for both upper and lower bounds of these norms, offering tighter performance guarantees and stability analyses for systems with nonnegative signals.
What Problem Does This Paper Address?
In control theory, the $L_p$ induced norm is a fundamental tool for assessing system stability and performance. It quantifies how much a system amplifies input signals to produce output signals. However, many real-world systems, such as those involving biological processes, economic models, or neural networks with ReLU activation functions, inherently deal with nonnegative inputs and outputs. The standard $L_p$ norm doesn't fully capture the behavior of these systems.
This paper addresses the need for a more specialized norm, the $L_p^+$ induced norm, which specifically considers nonnegative input signals. While the $L_2^+$ norm has shown promise for analyzing nonlinear systems with nonnegative outputs (like ReLU networks), its exact computation for linear systems is notoriously difficult. This paper aims to bridge this gap by providing practical methods to compute upper and lower bounds for these $L_p^+$ norms, thereby enabling more accurate stability and performance analyses for a broader class of systems.
Methods
The authors employ a multi-pronged approach:
- Copositive Programming for Upper Bounds: To tackle the difficulty of computing the $L_2^+$ induced norm, they introduce a method based on copositive programming. This involves using "copositive multipliers" to capture the nonnegativity of input signals. By constructing a sequence of increasingly complex copositive programs (and their tractable semidefinite programming relaxations), they derive monotonically non-increasing sequences of upper bounds for the $L_2^+$ norm.
- Uniform Infimum Analysis for Lower Bounds: To understand how much smaller the $L_p^+$ norm can be compared to the standard $L_p$ norm, they analyze the uniform infimum of the ratio $||G||_{p^+}/||G||_p$ over a broad class of linear systems. This provides a baseline lower bound applicable to any linear system.
- Semi-Infinite Programming for System-Specific Lower Bounds: For a given linear system, the uniform infimum might be too conservative. The authors develop a method to compute tighter lower bounds by reducing the problem to a semi-infinite programming problem. This involves constructing specific nonnegative input signals and analyzing the system's frequency response.
- Positive Filters: A key technique for improving the upper bound computations involves introducing positive filters. These filters are designed to preserve the nonnegativity of signals and are incorporated into the system's dynamics, allowing for more refined analysis.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and numerical examples generated from randomly constructed matrices representing linear systems.
Key Insights and Ideas
- The $L_p^+$ norm is a tighter measure: For systems with nonnegative inputs, the $L_p^+$ induced norm provides a more accurate assessment of input-output behavior and stability than the standard $L_p$ norm. This is because it accounts for the inherent constraints on the signals.
- Copositive programming unlocks upper bounds: The introduction of copositive multipliers and programming offers a systematic way to derive upper bounds for the $L_2^+$ norm, which was previously a significant challenge.
- A universal lower bound exists: The analysis of the uniform infimum reveals that for any stable linear system, the $L_p^+$ norm is at least a certain fraction (specifically, $1/\sqrt{2}$ for $p=2$) of the standard $L_p$ norm. This provides a fundamental limit on how much the $L_p^+$ norm can be smaller.
- System-specific lower bounds are achievable: While the uniform infimum is a general bound, the authors show how to compute tighter, system-specific lower bounds, which are crucial for evaluating the accuracy of the upper bounds.
- Relevance to ReLU networks: The $L_2^+$ norm is particularly important for analyzing the stability of systems involving ReLU activation functions, as these functions inherently produce nonnegative outputs. The methods developed can directly inform the stability analysis of such neural network-based systems.
Key Results
- Theorem 1 & 2: Provide a method for computing upper bounds of the $L_2^+$ induced norm using copositive programming and positive filters. The effectiveness of increasing filter degrees is demonstrated, leading to monotonically non-increasing upper bounds.
- Theorem 3: Establishes the uniform infimum of the ratio $||G||_{p^+}/||G||_p$ for stable linear systems, showing that $||G||_{p^+} \ge \frac{1}{\sqrt{2}} ||G||_p$ for $p=2$.
- Theorem 4, 5, 6, & 7: Develop effective methods for computing system-specific lower bounds for the $L_2^+$ induced norm, which are shown to be strictly greater than the uniform infimum in many cases, especially for single-input systems.
- Numerical Examples: Demonstrate the practical application of the methods, showing how the computed upper and lower bounds can lead to definitive conclusions about system properties (e.g., comparing reduced-order models) and stability (e.g., for ReLU-feedback systems) that are not possible with standard $L_2$ norm analysis.
Limitations and Future Work
- Computational Complexity: While the methods provide valuable bounds, the computational burden of copositive programming can be significant, especially for higher-dimensional systems. The authors note that the exact computation of COPs is NP-hard.
- Accuracy Guarantees: The paper acknowledges that while numerical examples illustrate the effectiveness of the proposed bounds, there are no theoretical guarantees for the accuracy of these bounds. Quantitatively evaluating this accuracy is identified as an important future research direction.
- Generalization to Time-Varying Systems: The theoretical results for the uniform infimum are shown to be valid even for time-varying and noncausal systems, suggesting potential avenues for extending the computational methods.
- Broader Application of Copositive Multipliers: The authors suggest that further research into the effectiveness of copositive multipliers in static and dynamical nonlinear system analysis is warranted.
Summary updated