Vorträge in der Woche 25.08.2025 bis 31.08.2025

Mittwoch, 27.08.2025: Structured Low-Rank Approximation: Theory, Algorithms, and Applications

Prof. Ivan Markovsky (ICREA, Barcelona)

Low-rank approximation is a unifying theme in data modelling. A matrix constructed from the data being rank deficient implies that there is an exact low-complexity linear model for that data. Moreover, the rank of the data matrix corresponds to the complexity of the model. In the generic case when an exact low-complexity model does not exist, the aim is to find an model that fits the data approximately. The approach that we present is to find small (in some specified sense) perturbation of the data that renders the perturbed data exact. The exact model for the perturbed data is an optimal (in the specified sense) approximate model for the original data. The corresponding computational problem is low-rank approximation. In the numerical linear algebra literature this approach is referred to as "total least squares" and in the statistical literature as "errors-invariables modelling". Exploiting prior knowledge, i.e., adding constraints that are known to hold for the data generating system, improves the basic low-rank approximation method. This path of development leads to weighted, structured, and other constrained low-rank approximation problems. The theory and algorithms of these new classes of problems are interesting in their own right and being application driven are practically relevant. Indeed, many well known concepts and problems from systems and control, signal processing, and machine learning reduce to low-rank approximation. Generic examples in system theory are model reduction and system identification. The principal component analysis method in machine learning is equivalent to low-rank approximation, so that related dimensionality reduction, classification, and information retrieval problems can be phrased as low-rank approximation problems. Sylvester structured low-rank approximation has applications in computations with polynomials and is related to methods from computer algebra. Many low-rank approximation problems are nonconvex, so that they are difficult to solve globally and efficiently. Two major categories of solution methods are suboptimal heuristics (subspace methods and convex relaxations) and local optimization methods. The latter are broadly subdivided into alternating projections and variable projections type methods. Low-rank approximation methods are derived for large scale problems and real-time computation, as well as for dealing with missing data, exact observations, and categorical data.