Dec 25, 2013

Sparsity-Related Researches in IEEE CDC 2013


The most important conference on controlIEEE Conference on Decision and Control (CDC) 2013, was held in this month, Dec 10-13, in Florence, Italy. Of course, I was there.

Foods are good, wines excellent, Duomo gorgeous, bazaar funny, I fully enjoyed my stay!

By the way,  I found papers related to sparsity in control including my paper:

Maximum Hands-Off Control and L1 Optimality
M. Nagahara, Kyoto Univ.
D. E. Quevedo, The Univ. of Newcastle
D. Nesic, Univ. of Melbourne
Abstract: In this article, we propose a new paradigm of control, called a maximum hands-off control. A hands-off control is defined as a control that has a much shorter support than the horizon length. The maximum hands-off control is the minimum support (or sparsest) control among all admissible controls. We first prove that a solution to an L1-optimal control problem gives a maximum hands-off control, and vice versa. This result rationalizes the use of L1 optimality in computing a maximum hands-off control. The solution has in general the "bang-off-bang" property, and hence the control may be discontinuous. We then propose an L1/L2-optimal control to obtain a continuous hands-off control. Examples are shown to illustrate the effectiveness of the proposed control method.

Graphical FPGA Design for a Predictive Controller with Application to Spacecraft Rendezvous
E. N. Hartley, Univ. of Cambridge
J. M. Maciejowski, Univ. of Cambridge
Abstract: A reconfigurable field-programmable gate array (FPGA)-based predictive controller based on Nesterov's fast gradient method is designed using Simulink and converted to VHDL using Mathworks' HDL Coder. The implementation is verified by application to a spacecraft rendezvous and capture scenario, with communication between the FPGA and a simulation of the relative dynamics occuring over Ethernet. For a problem with 120 decision variables and 240 constraints, computation times of 0.95 ms are achieved with a clock rate of 50 MHz, corresponding to a speed up of more than 2000 over running the algorithm directly on a MicroBlaze microprocessor implemented on the same FPGA.

Sparse Control Using Sum-Of-Norms Regularized Model Predictive Control
S. K. Pakazad, Linköping Univ.
H. Ohlsson, Linköping Univ.
L. Ljung, Linkoping Univ.
Abstract: Some control applications require the use of piecewise constant or impulse-type control signals, with as few changes as possible. So as to achieve this type of control, we consider the use of regularized model predictive control (MPC), which allows us to impose this structure through the use of regularization. It is then possible to regulate the trade-off between control performance and control signal characteristics by tuning the so-called regularization parameter. However, since the mentioned trade-off is only indirectly affected by this parameter, its tuning is often unintuitive and time-consuming. In this paper, we propose an equivalent reformulation of the regularized MPC, which enables us to configure the desired trade-off in a more intuitive and computationally efficient manner. This reformulation is inspired by the so-called varepsilon-constraint formulation of multi-objective optimization problems and enables us to quantify the trade-off, by explicitly assigning bounds over the control performance.

Near-Ideal Behavior of a Modified Elastic Net Algorithm
M. Vidyasagar, The Univ. of Texas at Dallas
Abstract: In this paper it is shown that a modification of the Elastic Net algorithm (MEN) exhibits near ideal behavior in the following sense: Suppose the input to the algorithm is a vector of known sparsity index but unknown locations for the nonzero components. Then the output error of the algorithm is bounded by a universal constant times the error achieved by an oracle that knows not just the sparsity index but also the locations of the nonzero components. This result generalizes an earlier result of Candes and Plan on the near ideal behavior of the LASSO algorithm.

Sparse Networked Control of Input Constrained Linear Systems
H. Kong, The Univ. of Newcastle
G. C. Goodwin, Univ. of Newcastle
M. Seron, The Univ. of Newcastle
Abstract: In networked control, there is often an incentive to communicate only what is absolutely necessary to achieve the desired performance goals. This is true of both the downlink (between a control base station and actuators) and the uplink (between the sensors and base station). Here we present a possible solution to this problem based on a singular value decomposition (SVD) of the Hessian of the quadratic performance index generally considered in Model Predictive Control (MPC). The singular vectors are employed to generate an orthonormal basis function expansion of the unconstrained solution to the finite horizon optimal control problem. These are pre-loaded into each actuator and each sensor. On the downlink, the actuators are informed in real-time about which basis functions they should use. On the uplink, after a “burn in period”, the sensors need only communicate when their response departs from that pre-calculated for the given basis functions. We show that this strategy facilitates sparse communication in both the downlink and uplink. We also show that the strategy can be modified so that input constraints are satisfied. The proposed results are illustrated by an example.

Soft-Constrained Lasso-MPC for Robust LTI Tracking: Enlarged Feasible Region and an ISS Gain Estimate
M. Gallieri, Univ. of Cambridge
J. M. Maciejowski, Univ. of Cambridge
Abstract: This paper investigates the robustness of a soft constrained LTI MPC for set-point tracking, using an l1- regularised cost. The MPC using this type of cost (informally dubbed lasso-MPC) is suitable, for instance, for redundantly- actuated systems. This is because of its ability to select a set of preferred actuators, leaving the other ones at rest for most of the time. The proposed approach aims to recover from state constraint violation and to track a changing set-point. Nominal stability is guaranteed for all feasible references and robustness to additive uncertainties is formally characterised, under certain assumptions. In particular, sufficient conditions are given for the feasible region to be robustly invariant, this region being larger than the MPC for regulation. The closed- loop system is input-to-state stable (ISS), and a local ISS gain is computed. All results apply to stabilisable LTI systems. Results hold as well for the more common quadratic MPC, a special case of the proposed controller. 

Proximal Newton Methods for Convex Composite Optimization
P. Patrinos, IMT Inst. for Advanced Studies Lucca
A. Bemporad, IMT Inst. for Advanced Studies Lucca
Abstract: This paper proposes two proximal Newton methods for convex nonsmooth optimization problems in composite form. The algorithms are based on a new continuously differentiable exact penalty function, namely the emph{Composite Moreau Envelope}. The first algorithm is based on a standard line search strategy, whereas the second one combines the global efficiency estimates of the corresponding first-order methods, while achieving fast asymptotic convergence rates. Furthermore, they are computationally attractive since each Newton iteration requires the solution of a linear system of usually small dimension.


Dec 13, 2013

Sparse Packetized Predictive Control

As in signal processing, sparsity is also a useful concept in control systems. 

Our paper on a sparsity-based control method has been accepted to
IEEE Transactions on Automatic Control, entitled
"Sparse Packetized Predictive Control for Networked Control over Erasure Channels"

The paper can be downloaded from arxiv.

The motivation of this study is sparse representation of control data.
In networked control systems, the data packets are transmitted through communication channels whose bit-rates are limited, and the transmitted data should be represented in fewer bits.
Sparsity then gives an attractive solution to this problem.

To reduce the data size of packets, we have proposed to adopt sparsity-promoting optimizations, namely, 
  1. L1-L2 optimization
  2. L2-constrained L0 optimization

for which efficient algorithms exist (e.g., see this article).

We have shown how to design the tuning parameters to ensure (practical) stability of the resulting feedback control systems when the number of consecutive packet-dropouts is bounded.


Apr 7, 2013

Control Theoretic Spline: A bridge between control and signal processing

The spline has been widely used in signal processing, numerical computation, statistics, etc.  In particular, the smoothing spline gives a smooth curve that has the best fit to given noisy data with the following optimization:

where (t1, y1),..., (tn,yn) are given data, y(t) is the curve to be estimated, and r is the regularization parameter that specifies the trade-off between the fidelity to the data (1st term) and the smoothness of the curve (2nd term). The optimal curve is given by a linear combination of shifted cubic splines (see G. Wahba's book for details).

The smoothing spline can be rewritten in terms of control theory. We assume y(t) is the output of the double integrator for some input u(t), namely,

where "s" is the differential operator (or the symbol of the Laplace transform). Then we rewrite the optimization problem as

Then, a control theoretic spline is defined by replacing 1/s2 with a general transfer function P(s), that is

For example, you can obtain a general smoothing spline that minimizes

by solving the control theoretic spline optimization described above with

An important fact is that the optimal solution (or optimal control), u(t), is given by a linear combination of exponential functions (including polynomial functions) that are specified by the impulse response (i.e., the inverse Laplace transform) of P(s).

A control theoretic spline can be explained as drawing a curve with a robot hand modeled by P(s); see the top picture.  This illustrates that the control theoretic spline is a bridge between control and signal processing.

The original paper on control theoretic spline can be downloaded from here.
Control theoretic spline with a monotonicity constraint is discussed in this paper.
Compressive sampling approach to control theoretic spline is proposed in this paper.

See also this blog entry.

Mar 2, 2013

A User's Guide to Compressed Sensing for Communications Systems

A survey paper has been recently published, entitled A User's Guide to Compressed Sensing for Communications Systems, which I co-authored with Kazunori and Toshiyuki.

PDF is available here, and SCILAB codes here.

Compressed sensing (CS) becomes more and more popular in communications engineering.  In this paper, you can find many applications of CS to communications systems.  The summary reads
SUMMARY: This survey provides a brief introduction to compressed sensing as well as several major algorithms to solve it and its various applications to communications systems. We firstly review linear simultaneous equations as ill-posed inverse problems, since the idea of compressed sensing could be best understood in the context of the linear equations. Then, we consider the problem of compressed sensing as an underdetermined linear system with a prior information that the true solution is sparse, and explain the sparse signal recovery based on ell-1 optimization, which plays the central role in compressed sensing, with some intuitive explanations on the optimization problem. Moreover, we introduce some important properties of the sensing matrix in order to establish the guarantee of the exact recovery of sparse signals from the underdetermined system. After summarizing several major algorithms to obtain a sparse solution focusing on the ell-1 optimization and the greedy approaches, we introduce applications of compressed sensing to communications systems, such as wireless channel estimation, wireless sensor network, network tomography, cognitive radio, array signal processing, multiple access scheme, and networked control.
Enjoy CS with this guide!

Related entries:

Igor has featured our paper on his blog entry. Thank you Igor! (07/Mar/2013)