Low-Rank Approximation

Section 1.2 presented as a motivating example an equivalence between line fitting and rank-one approximation. Section 1.3 listed examples from different applications, where the problems reduce to low-rank approximation. This leads us to claim that “Behind every data modeling problem there is a (hidden) low-rank approximation problem.” In the rest of the book, we pose and solve multivariable linear static, dynamic linear time-invariant, and nonlinear data modeling problems in the low-rank setting. The advantage of this approach is that one algorithm (and software implementation) can be used to solve a variety of practical data modeling problems. In order to state the general data modeling problem considered in the book, we need the notions of a model, model complexity, and lack of fit between the data and a model. Therefore, first, we define rigorously the basic notion of a mathematical model. Important questions considered are: “How to represent a model by equations?” and “How to convert one representation into another one?” When two models fit the data equally well, we prefer the simpler model. For this purpose, we define the notion of model complexity. Two principles—misfit and latency—used to quantify the lack of fit between the data and a model are introduced. In a stochastic setting, the misfit principle leads to the errors-in-variables modeling problems and the latency principle leads to the static regression and dynamic ARMAX problems. In defining the notions of model, representation, and model complexity, first are considered linear static models, in which case the representation is an algebraic equation. Then, the results are extended to linear time-invariant models, in which case the model representation is a differential or difference equation. Finally, the ideas are applied to stochastic systems, i.e., systems driven by stochastic processes.

This chapter develops methods for computing the most powerful unfalsified model for the data in the model class of linear time-invariant systems. The first problem considered is a realization of an impulse response. This is a special system identification problem when the given data is an impulse response. The method presented, known as Kung’s method, is the basis for more general exact identification methods known as subspace methods. The second problem considered is computation of the impulse response from a general trajectory of the system. We derive an algorithm that is conceptually simple—it requires only a solution of a system of linear equations. The main idea of computing a special trajectory of the system from a given general one is used also in data-driven simulation and control problems (Chap. 6). The next topic is identification of stochastic systems. We show that the problem of ARMAX identification splits into three subproblems: (1) identification of the deterministic part, (2) identification of the AR-part, and (3) identification of the MA-part. Subproblems 1 and 2 are equivalent to deterministic identification problem. The last topic considered in the chapter is computation of the most powerful unfalsified model from a trajectory with missing values. This problem can be viewed as Hankel matrix completion or, equivalently, computation of the kernel of a Hankel matrix with missing values. Methods based on matrix completion using the nuclear norm heuristic and ideas from subspace identification are presented.

Data modeling using a linear static model class leads to an unstructured low-rank approximation problem. When the approximation criterion is the Frobenius norm, the problem can be solved by the singular value decomposition. In general, however, unstructured low-rank approximation is a difficult nonconvex optimization problem. Section 4.1 presents a local optimization algorithm, based on alternating projections. An advantage of the alternating projections algorithm is that it is easily generalizable to missing data, nonnegativity, and other constraints on the data. approximate modeling problem leads to structured low-rank approximation. Section 4.2 presents a variable projection algorithm for affine structured low-rank approximation. This method is well suited for problems where one dimension of the matrix is small and the other one is large. This is the case in system identification, where the small dimension is determined by the model’s complexity and the large dimension is determined by the number of samples. The alternating projections and variable projection algorithms perform local optimization. An alternative approach for structured low-rank approximation is to solve a convex relaxation of the problem. A convex relaxation based on replacement of the rank constraint by a constraint on the nuclear norm is shown in Sect. 4.3. The nuclear norm heuristic is also applicable for matrix completion (missing data estimation). Section 4.4 generalize the variable projection method to solve low-rank matrix completion and approximation problems.

This chapter reviews applications of structured low-rank approximation for 1. model reduction, 2. approximate realization, 3. output only identification (sum-of-damped-exponentials modeling), 4. harmonic retrieval, 5. errors-in-variables system identification, 6. output error system identification, 7. finite impulse response system identification (deconvolution), 8. approximate common factor, controllability radius computation, and 9. pole placement by a low-order controller. The problems occurring in these applications are special cases of the SLRA problem, obtained by choosing specific structure \(\mathscr {S}\) and rank constraint r. Moreover, the structure is of the type (S), so that the algorithm and the software, developed in Sect. 4.2.3, can be used to solve the problems.

Applied to nonlinear modeling problem, the maximum-likelihood estimation principle leads to nonconvex optimization problems and yields inconsistent estimators in the errors-in-variables setting. This chapter presents a computationally cheap and statistically consistent estimation method based on a bias correction procedure, called adjusted least squares estimation. The adjusted least squares method is applied to curve fitting (static modeling) and system identification. Section 7.1 presents a general nonlinear data modeling framework. The model class consists of affine varieties with bounded complexity (dimension and degree) and the fitting criteria are algebraic and geometric. Section 7.2 shows that the underlying computational problem is polynomially structured low-rank approximation. In the algebraic fitting method, the approximating matrix is unstructured and the corresponding problem can be solved globally and efficiently. The geometric fitting method aims to solve the polynomially structured low-rank approximation problem, which is nonconvex and has no analytic solution. The equivalence of nonlinear data modeling and low-rank approximation unifies existing curve fitting methods, showing that algebraic fitting is a relaxation of geometric fitting, obtained by removing the structural constraint. Motivated by the fact that the algebraic fitting method is efficient but statistically inconsistent, Sect. 7.3.3 proposes a bias correction procedure. The resulting adjusted least squares method yields a consistent estimator. Simulation results show that it is effective also for small sample sizes. Section 7.4 considers the class, called polynomial time-invariant, of discrete-time, single-input, single-output, nonlinear dynamical systems described by a polynomial difference equation. The identification problem is: (1) find the monomials appearing in the difference equation representation of the system (structure selection), and (2) estimate the coefficients of the equation (parameter estimation). Since the model representation is linear in the parameters, the parameter estimation by minimization of the 2-norm of the equation error leads to unstructured low-rank approximation. However, knowledge of the model structure is required and even with the correct model structure, the method is statistically inconsistent. For the structure selection, we propose to use 1-norm regularization and for the bias correction, we use the adjusted least squares method.

Centering by mean subtraction is a common preprocessing step applied before other data modeling methods are used. Section 8.1 studies different ways of combining linear data modeling by low-rank approximation with data centering. It is shown that in the basic case of approximation in the Frobenius norm and no structure, the two-step procedure of preprocessing the data by mean subtraction and low-rank approximation is optimal. In the case of approximation in either a weighted norm or with a structural constraint, the two-step procedure is suboptimal. We show modifications of the variable projection and alternating projections methods for weighted and structured low-rank approximation with centering. Section 8.2 considers an approximate rank revealing factorization problem with structural constraints on the normalized factors. Examples of structure, motivated by an application of the problem in microarray data analysis, are sparsity, nonnegativity, periodicity, and smoothness. An alternating projections algorithm is developed. Although the algorithm is motivated by a specific application in microarray data analysis, the approach is applicable to other types of structure. Section 8.3 considers the problem of solving approximately in the least squares sense an overdetermined system of linear equations with complex-valued coefficients, where the elements of the solution vector are constrained to have the same phase. This problem is reduced to a generalized low-rank matrix approximation. Section 8.4 considers a blind identification problem with prior knowledge about the input in the form of a linear time-invariant autonomous system. A special case of the problem for constant input has an application in metrology for dynamic measurement. The general problem can be viewed alternatively as a gray-box identification problem or an input estimation problem with unknown model dynamics.