Low Rank Approximation. Algorithms, Implementation, Applications

Application domains such as systems and control, signal processing, machine learning, computational geometry, recommendation systems, etc. typically have their own separate research communities usually with little overlap. Many of the problems solved can however be seen as a linear approximation problem. So explicitly or implicitly, there is a linear map (a matrix) involved that should be approximated by a simpler one (i.e., one of lower rank).

After some introductory chapter exploring the field, in a first part, the fundamental aspects of different models (chapter 2), algorithms (chapter 3) and applications (chapter 4) are discussed. In a second part, some generalizations complete the picture further: dealing with missing data, centering, and constraints (chapter 5), nonlinear static data modeling (chapter 6) and fast modeling of slow processes (chapter 7).

In chapter 2, distinction is made between several models. The map can be described by giving the null-space (kernel) of the matrix, or its range (image), or some input-output relation (with or without state-variables in between). Also describing and computing or fixing the complexity (e.g., ranks), the structure involved (often (block-)Hankel or Toeplitz matrices), and deciding whether or not one wants to recover it exactly or approximately (there may be noise involved) is part of this chapter.

The algorithms are discussed in chapter 3. These describe the computational (numerical) techniques that are needed. Of course singular value decomposition (SVD) is an essential tool here. However, this is only suboptimal when structure is involved (e.g. truncating a SVD of a Hankel is not Hankel anymore). More complex optimisation methods are often needed.

In the 4th chapter all this is applied in problems from systems and control, and signal processing. Here we find the classical items such as model reduction, system identification, system realization, observability and controllability, etc.

The first generalization of chapter 5 involves missing data, or more generally, a weight can be associated to each data-item that is given. If the item is missing, it gets a weight zero. Centering means that e.g., an average can be subtracted from the data. This seems a trivial modification, but it affects the implementation and the particular methods involved. On an abstract level, it means that your model is not in some subspace, but in an affine model set. Another problem is a complex linear least squares problem $Axe^{i\phi}≈b$ with real $x$ and $\phi$, but complex $A$. Finally a problem of low rank factorisation for a structured matrix is discussed. For each of these, a computational algorithm is proposed and some simulation results are shown.

The nonlinear modeling of chapter 6 is of a geometric flavour. Given some data points, one wants to fit these with curves selected from a nonlinear model set, which is e.g., a set of curves described by multivariate polynomials. The low rank approximation refers to reducing the degree of these polynomials.

The last chapter deals with slowly varying dynamical systems where e.g., the system evolves from some initial condition, to some stationary state. Measurements of the transient evolution are given and the goal is to derive the parameters of the system (and hence predict the final state). The model of the system can be known (but not its parameters) or it may depend on many environmental influences that it is essentially unknown.

Because of its interdisciplinary nature, the approach to some of the problems and the connection to related problems may come as a surprise. In that sense the book is certainly innovating. The connections (or at least some of them) have been slumbering in the back of my mind, but I never came about it to think it over more deeply. And here it is! It is a book I wish I had written myself.

Another feature of the book is the many chunks of matlab code that one can find throughout the text. There is not an appendix with complete listings of matlab programs, but instead, the little pieces found throughout can be pieced together in a modular way to provide a code that solves the problem. It is using the noweb system for literate programming, that is a system that may either extract machine code or nicely printable documentation for the source text. An Octave version of the code is promised to be available on the book's web page, but I could not find it (yet) on March 1, 2012.

Let me finally mention that the list of references is organized per chapter, and is preceded with notes guiding you through them. Even with the degree of abstraction, the book is basically practically oriented. There are some proofs, but they are never dull or long-winding. The book is an addition to but not a replacement of courses in the applied fields mentioned above. Knowledge of linear algebra and matlab are prerequisites. A good assimilation requires solving exercises. A list of problems is provided in an appendix. Some require proofs while others ask for computational experiments, or even small projects.

A. Bultheel (Leuven)
Book details

Seen from a unifying approach of approximating a complicated linear relation by a simpler (lower rank) one, the book treads many different problems from systems theory, control, image and signal processing, data reduction, machine learning, computer vision etc. This encompasses the different models that can be chosen, but also the different solution methods and algorithms up to and including a matlab implementation.



79.95 € (net)

User login