**European
Control Conference 2013
**

**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

**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

**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

**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.