Source-linked AI summary
Subspace System Identification via Weighted Nuclear Norm Optimization
Anders Hansson, Zhang Liu, Lieven Vandenberghe
TL;DR
Subspace identification relies on low-rank approximations, but nuclear-norm heuristics can be suboptimal and lack theoretical effectiveness analysis. This paper combines nuclear-norm optimization with standard subspace-identification weights, instrument variables, and ADMM. Experiments on random systems and DaISy benchmarks show improved validation fit and smaller optimization problems.
Problem
Nuclear-norm heuristics offer structured low-rank approximation for subspace identification, but can be very suboptimal and lack theoretical effectiveness analysis.
Method
The method optimizes a weighted nuclear norm over an output sequence, using measured data to define instrument variables and weights while solving with ADMM.
Results
Weighted formulations improve validation-data fit across random and DaISy examples, with CVA weights performing best in the reported comparisons.
Takeaways & Limitations
Weights improve fit and reduce optimization-problem size, while ADMM contributes to speedup compared with earlier interior-point implementations.
Abstract
from arXiv · showhide
We present a subspace system identification method based on weighted nuclear norm approximation. The weight matrices used in the nuclear norm minimization are the same weights as used in standard subspace identification methods. We show that the inclusion of the weights improves the performance in terms of fit on validation data. As a second benefit, the weights reduce the size of the optimization problems that need to be solved. Experimental results from randomly generated examples as well as from the Daisy benchmark collection are reported. The key to an efficient implementation is the use of the alternating direction method of multipliers to solve the optimization problem.
I. INTRODUCTION
Subspace identification uses efficient low-rank matrix algorithms and can incorporate weights, but lacks guaranteed estimation efficiency and makes model-order selection difficult. The paper improves a nuclear-norm approach by combining weighted optimization with instrument variables.
- Weighted subspace methods use QR and singular value decomposition for low-rank approximations while accommodating colored noise.
- Nuclear norm minimization preserves linear matrix structure and combines naturally with convex regularization and constraints.
- Nuclear-norm identification can be very suboptimal, and its effectiveness for identification lacks theoretical analysis.
- The proposed instrument-variable nuclear-norm approach improves validation fit in more than 90% of cases versus 84% without instrument variables.Instrument variables also reduce optimization dimension and improve solution speed.
- The paper presents subspace identification, nuclear-norm heuristics, an ADMM solver, and experimental evaluation in successive sections.
II. SUBSPACE IDENTIFICATION
The method estimates a linear state-space model from observed inputs and outputs by constructing structured data matrices, projecting out inputs, and applying weighted variants of subspace identification. Instrument variables address colored-noise bias, while weighting also changes computational dimension.
- The target is a linear discrete-time state-space model whose system matrices are estimated from observed input and output sequences.
- Subspace identification constructs output and input block Hankel matrices and, for output noise, projects the output matrix onto the nullspace of the input block.
- An SVD of the projected matrix estimates system order and provides a low-rank approximation used to determine A, B, C, and D.
- Instrument variables modify the matrix construction to avoid biased estimates when noise is colored.
- Weighting changes the dimension of the matrix used in nuclear-norm minimization, with instrument-variable and CVA variants typically producing the smallest matrices.When no weighting is used, the dimension is r × 2s; without instrument variables, it is r × N, and s is typically much smaller than N.
III. NUCLEAR NORM OPTIMIZATION
The paper formulates identification as a weighted nuclear-norm approximation over an output sequence, retaining affine dependence by fixing instruments and weights from measured data. This extends earlier nuclear-norm subspace identification while preserving a fidelity penalty to measurements.
- The nuclear norm is the sum of a matrix’s singular values and serves as a convex heuristic for low-rank approximation.
- Earlier work applied nuclear-norm optimization to subspace system identification through a regularized approximation problem [LV09a].
- The optimization variable is a new output sequence whose Hankel matrix defines G(y), while measured outputs and inputs remain fixed elsewhere.
- The proposed extension minimizes the weighted nuclear norm of ˆG using instrument variables and matrix weights while penalizing deviation from measured outputs.Measured outputs define the instrument variable and weights so that ˆG remains affine in the optimization variable y.
IV. ADMM ALGORITHM
The paper formulates weighted nuclear norm identification as a regularized convex problem and solves it with ADMM, using singular value thresholding and adaptive implementation improvements.
- IV. ADMM ALGORITHM: The linear mapping is affine, A(x) = A1x1 + A2x2 + ··· + Anxn, with x ∈ R^n and output matrix dimensions p × q.These dimensions define the matrix-valued constraint used by the optimization problem.
- IV. ADMM ALGORITHM: ADMM solves the regularized nuclear norm problem by alternating minimizations over x and X with a dual-variable update.The formulation minimizes ||X||_* plus quadratic regularization subject to A(x) − X = B.
- IV. ADMM ALGORITHM: The nuclear-norm variable X is updated through singular value thresholding, while the x-update uses the adjoint operator and matrix M.M is defined by Mx = Aadj(A(x)).
- IV. ADMM ALGORITHM: Stopping uses primal and dual residuals together with primal and dual tolerances, including relative and absolute tolerance parameters.The paper gives example values ϵrel = 10^-3 and ϵabs = 10^-6.
- IV. ADMM ALGORITHM: Adaptive penalty updates improve convergence, and a proximal quadratic term can avoid the inverse involving C + tM.The suggested parameters include µ = 10 and τ = 2.
- IV. ADMM ALGORITHM: Figure 1 reports typical ADMM convergence for a randomly generated problem with p = q = 200 and n = 600.The algorithm is summarized in Table II.
V. EVALUATION
The evaluation preprocesses measured outputs with weighted nuclear norm optimization before standard n4sid identification, then compares validation-data fit against a baseline. Random-model experiments and the DaISy collection provide the evaluation settings, with CVA-based comparisons shown in Figure 2.
- V. EVALUATION: Weighted nuclear norm preprocessing modifies the output sequence before standard n4sid post-processing, producing solutions for different weightings and instrument-variable choices.The baseline is standard n4sid without nuclear-norm preprocessing.
- V. EVALUATION: Validation fit is computed on data distinct from identification data, averaging fits across outputs and selecting the best of 20 logarithmically spaced regularization values.The tested λ values span 2 × 10^-3 to 10^3, with r = s = 15 during preprocessing.
- V. EVALUATION: The experiments include randomly generated state-space models and the DaISy collection of input-output data from real systems.The evaluation presents random models first and the DaISy collection afterward.
- V. EVALUATION: Figure 2 compares validation fits from the CVA-based nuclear norm method against the baseline solution in a scatter plot.The cited passage identifies the comparison but does not provide cell values or a stated winner.
A. Randomly generated models
Randomly generated single-input-single-output systems were evaluated across varying state dimensions, input scales, and signal-to-noise conditions. Weighted nuclear-norm approaches were compared with a baseline using validation-data fit and system-order differences.
- A. Randomly generated models: More than 10% of cases achieved significantly better validation fit with the CVA-based nuclear-norm method, with no significantly worse cases reported.The comparison covered 156 randomly generated examples; the table reports percentages of cases outperforming the baseline.
- A. Randomly generated models: The experiments used 156 randomly generated examples spanning state dimensions 4–20 and input scales σ from 2 to 10.Identification and validation lengths were 300 and 1500, respectively, with white Gaussian input and noise.
- A. Randomly generated models: When CVA-based nuclear-norm fit improved, the identified order was often unchanged or increased by one state, and was more commonly higher than lower.The histogram includes only cases where the nuclear-norm approach achieved better fit.
B. Examples from the DaISy collection
Ten DaISy benchmark problems were evaluated by splitting each single input-output sequence into identification and validation segments. CVA weights achieved the highest average fit and led on half of the examples.
- B. Examples from the DaISy collection: The evaluation split each benchmark sequence into initial identification data and subsequent validation data, with stability enforced in n4sid.The benchmark set contained ten examples, and the MATLAB settings also estimated the direct term D.
- B. Examples from the DaISy collection: CVA weights achieved the highest fit in 5 of 10 examples and also had the highest average fit, with negative NONE fit on example 4 excluded from averaging.IVM and NOINSTR had the next-highest average fit, while MOESP and unweighted NONE performed less well on average.
- B. Examples from the DaISy collection: NOINSTR on example 3 and CVA on example 9 exceeded the second-highest fit by at least 6%.These were the clearest example-specific improvements reported for the benchmark collection.
VI. CONCLUSIONS
The paper presents weighted nuclear-norm optimization for subspace system identification and reports improved validation fit from using weights. The weights also reduce optimization size, while ADMM improves implementation speed over earlier interior-point methods.
- VI. CONCLUSIONS: Weighted nuclear-norm optimization improves validation-data fit while reducing the size of the optimization problems.The weights are those used in standard subspace identification methods.
- VI. CONCLUSIONS: ADMM contributes to the speedup compared with previous interior-point implementations.Future work will tailor ADMM further to this application.