July 17, 2013, Zurich, Switzerland

Tutorial Session on Sparse and low-rank representation methods in control, estimation and system identification

Organizer: Bo Wahlberg, KTH Royal Institute of Technology, Sweden

Tutorial abstract: This tutorial gives an introduction on how to apply convex optimization methods to select sparse or low-rank representations to problems in control, estimation and system identification. This is an very active area of research with a lot of recent exciting contributions. The basic idea is to use convex relaxation as a heuristic for solving certain combinatorial optimization problems. The main focus of the tutorial will be on extension of using the $l_1$-norm as a substitute for the so-called $l_0$-norm in order to penalize the number of non-zero elements (sparseness) in a parameter vector. The $l_1$-norm regularization concept leads to a vast family of well-known sparse estimation methods in computational statistics, including total variation denoising, basis pursuit and the lasso method. The field of compressed sensing is very much based on the idea of $l_1$-norm regularization, and under which conditions this relaxation works. The corresponding convex relaxation for rank-constrained optimization problems is the nuclear norm, that is the sum of the absolute values of the singular values of a matrix.

The application of the $l_1$-norm or the nuclear norm penalty in control and estimation of dynamical systems is more recent with a huge range of possible applications. An approach is to extend standard quadratic cost functions, like in LQ and MPC control or Kalman filtering, with penalty terms that stress certain structure, such as sparsity or rank, constraints. For example, the nuclear norm can be used to include rank constraints, for example that the rank of the impulse response Hankel matrix equals the system order, and has very interesting application in system identification.

The tutorial is divided into three parts. The first lecture will give a tutorial on convex optimization algorithms sparse and low-rank representations that can handle very large problems. The second lecture concerns applications of “sparse method” in control of distributed systems. The third lecture will give a survey of using sparse and low-rank representation methods in system identification.

Speakers & Affiliations

Mihailo R. Jovanovic

Department of Electrical and Computer Engineering

University of Minnesota, Minneapolis, USA

E-mail: mihailo@umn.edu

Cristian R. Rojas

Department of Electrical Engineering and ACCESS

KTH Royal Institute of Technology, Stockholm, Sweden

E-mail: cristian.rojas@ee.kth.se

Bo Wahlberg

Department of Electrical Engineering and ACCESS

KTH Royal Institute of Technology, Stockholm, Sweden

E-Mail: bo.wahlberg@ee.kth.se

Lieven Vandenberghe

Department of Electrical Engineering

University of California, Los Angeles, USA

E-mail: vandenbe@ee.ucla.edu

Lecture 1: Convex optimization algorithms for sparse and low-rank representations

Lecturer: Lieven Vandenberghe, UCLA, USA

SlidesLV

Abstract: Convex methods for computing sparse or low-rank representations and their extensions typically require the minimization of the sum of a differentiable function (for example, a quadratic error term) and a simple nondifferentiable function (for example, a structure-promoting norm). A wide variety of algorithms has been proposed for this purpose. The lecture will give an introduction to algorithms based on dual decomposition, proximal mappings, and operator splitting. This includes proximal gradient methods, the alternating direction method of multipliers (ADMM), and other popular methods. After presenting some elements of convex analysis, we will discuss three general classes of algorithms: the proximal point algorithm, the forward-backward iteration, and the Douglas-Rachford splitting algorithm, applied to the primal, dual, or primal-dual optimality conditions. The algorithms will be illustrated with nuclear norm minimization problems arising in system identification.

Lecture 2: Sparsity-promoting optimal control of distributed systems

Lecturer: Mihailo Jovanovic, University of Minnesota, USA

SlidesMJ

Abstract: This tutorial is about design of feedback gains that achieve a desirable tradeoff between quadratic performance of distributed systems and controller sparsity. Our approach consists of two steps. First, we identify sparsity patterns of the feedback gains by incorporating sparsity-promoting penalty functions into the optimal control problem, where the added terms penalize the number of communication links in the distributed controller. Second, we optimize feedback gains subject to structural constraints determined by the identified sparsity patterns. In the first step, the sparsity structure of feedback gains is identified using the alternating direction method of multipliers, a powerful algorithm well-suited to large optimization problems. This method alternates between promoting the sparsity of the controller and optimizing the closed-loop performance, which allows us to exploit the structure of the corresponding objective functions. In particular, we take advantage of the separability of the sparsity-promoting penalty functions to decompose the minimization problem into sub-problems that can be solved analytically. Even though the standard quadratic performance index is in general a nonconvex function of the feedback gain, we identify classes of convex problems that arise in the design of sparse undirected networks. In this case, the corresponding synthesis problem can be formulated as a semidefinite program, implying that the globally optimal sparse controller can be computed efficiently. Several examples are provided to demonstrate the effectiveness of the developed approach and the accompanying software LQRSP (which is available at www.ece.umn.edu/users/mihailo/software/lqrsp/).

Lecture 3: Sparse and low-rank representation methods in system identification

Lecturers: Cristian Rojas and Bo Wahlberg, KTH Royal Institute of Technology, Sweden

SlidesCR and SlidesBW

Abstract: Since the 90's, sparsity has been playing an important role in several aspects of statistics, machine learning and signal processing, among other fields. In this talk, we will focus on some specific connections of sparsity to important problems in system identification. In particular, the problem of sparse estimation will be seen in the context of model structure selection, where $l_1$ regularization becomes a handy tool for overcoming the curse of dimensionality in model selection (when the number of candidate model structures is large) and for imposing prior knowledge, thus delivering parsimonious models. Then, the so-called nuclear norm relaxation, a convex surrogate of the rank function, corresponding to the $l_1$ norm of the singular values of a matrix, will be used for subspace-like identification and for the estimation of structured systems. Finally, we will discuss the use of $l_1$ regularization for change point detection. These techniques unfortunately are not fool-proof, so we will discuss some conditions under which these sparsity-inducing methods might fail and when they can be more safely used.