SPARSELY-PACKETIZED PREDICTIVE CONTROL BY
ORTHOGONAL MATCHING PURSUIT ∗MASAAKI NAGAHARA† , DANIEL E. QUEVEDO‡ , AND JAN ØSTERGAARD§
Key words. Packetized predictive control, networked control, sparse representation, compressedsensing, orthogonal matching pursuit
AMS subject classifications. 37N35, 47N70, 49J15, 49M20, 93C41, 93D20
Abstract. We study packetized predictive control, known to be robust against packet dropoutsin networked systems. To obtain sparse packets for rate-limited networks, we design control packets
via an ℓ0 optimization, which can be effectively solved by orthogonal matching pursuit. Our formulation ensures asymptotic stability of the control loop in the presence of bounded packet dropouts.

1. Packetized Predictive Control. Let us consider the following discretetime, LTI plant model with a scalar input:x(k + 1) = Ax(k) + Bu(k),k ∈ N0 ,x(0) = x0 ,(1.1)

where x(k) ∈ Rn and u(k) ∈ R for k ∈ N0 . We assume that (A, B) is reachable. We
are interested in a networked control architecture where the controller communicateswith the plant actuator through an erasure channel, see Fig. 1.1. This channel introduces bounded packet-dropouts. In packetized predictive control (PPC), as described,e.g., in [4, 2] at each time instant k, the controller uses the state x(k) of the plant(1.1) to calculate and send a control packet of the form() [ () ()()]⊤u x(k) , u0 x(k) , u1 x(k) , . . . , uN −1 x(k)
∈ RN

(1.2)

to the plant input node.
To achieve robustness against packet dropouts, buffering is used. To be more
specific, suppose that at time instant k the data packet u(x(k)) defined in (1.2) issuccessfully received at the plant input side. Then, this packet is stored in a buffer,overwriting its previous contents. If the next packet, u(x(k +1)), is dropped, then theplant input u(k +1) is set to u1 (x(k)), the second element of u(x(k)). The subsequentelements of u(x(k)) are then successively used until some control packet u(x(k + ℓ)),ℓ ≥ 2, is successfully received, i.e., no dropout occurs.
2. Sparse Control Packet Design for Asymptotic Stability. In the PPC
method discussed above, control packets u(x(k)) are transmitted at each time k ∈ N0
through an erasure channel. It is often the case that the bandwidth of the channel
is limited, and hence one has to compress control packets to a smaller data size.
To achieve an efficient compression of packets, we adopt a technique developed incompressed sensing [1] that considers the sparsity of a signal (or a vector). A sparse
vector contains many 0-valued elements and can be highly compressed by only coding∗ This research was supported in part under the MEXT (Japan) Grant-in-Aid for Young Scientists(B) No. 22760317, and also Australian Research Council’s Discovery Projects funding scheme (projectnumber DP0988601).
† Graduate School of Informatics, Kyoto University, Kyoto, 606-8501, Japan;
e-mail:nagahara@ieee.org‡ School of Electrical Engineering & Computer Science, The University of Newcastle, NSW 2308,
Australia; e-mail:dquevedo@ieee.org§ Department of Electronic Systems, Aalborg University, Denmark; e-mail: janoe@ieee.org

u(k)u(x(k))
Controller

Bufferx(k)PlantFig. 1.1. Networked Control System with PPC

its few nonzero components. Based on this notion, in [2] we presented a sparsityinducing ℓ1 /ℓ2 optimization for PPC which gives practical stability, i.e., existenceof a bounded invariant set. In the present work, we embellish the approach of [2]by showing how to find sparse control packets u(x(k)) ensuring that the networked
system with bounded packet dropouts is asymptotically stable. For this, we propose
to design the control packets via the following sparsity-promoting optimization:u(x(k)) , arg min ∥u∥0 subject to ∥xN |k ∥2P +u∈RNN−1∑∥xi|k ∥2Q ≤ x(k)⊤ W x(k),

(2.1)

i=0

where ∥u∥0 is the number of the nonzero elements in u = [u0 , u1 , . . . , uN −1 ]⊤ andx0|k = x, xi+1|k = Axi|k + Bui , i = 0, 1, . . . , N − 1.

(2.2)

In (2.2), N is the horizon length, taken here equal to the buffer size. The matrix
Q > 0 is a design parameter which allows one to shape the response of the plantstate components; P > 0 and W > 0 are chosen such that the feedback system is
asymptotically stable, as indicated in Theorem 2.1 below. To state our subsequent
results, we introduce the matrices Φ, Υ and Q̄ by
B0... 0A
 AB A2 B... 0Φ,
. . . , Q, P }.
..
..
..  , Υ ,  ..  , Q̄ , blockdiag{Q,..
| {z }. .
.
.
. N −1
AN −1 B AN −2 B . . . B
ANTheorem 2.1 (Asymptotic Stability). Assume that the number of consecutive
packet-dropouts is uniformly bounded by N . Suppose the matrices P , Q, and W arechosen by the following procedure:i. Choose Q > 0 arbitrarily.
ii. Solve the following Riccati equation to obtain P > 0:
P = A⊤ P A − A⊤ P B(B ⊤ P B)−1 B ⊤ P A + Q.

(2.3)

iii. Compute the constants ρ ∈ [0, 1) and c > 0 via
ρ , 1 − λmin (QP −1 ), c ,{}1 − ρN⊤−1max λmax Φ⊤,i P Φi (Φ Q̄Φ)1−ρ iwhere Φi is the i-th column of matrix Φ.
iv. Choose a matrix E such that 0 < E < (1 − ρ)P/c.
v. Set W := P − Q + E.
Then for any choice of the control vector from the feasible set of the optimization (2.1)(which includes the sparsest control packets u(x(k))), the networked control system is
asymptotically stable, that is, limk→∞ x(k) = 0.

Sparsity ||u(k)||02−norm of the state x(k)01010OMPL1/L2 (i)L1/L2 (ii)
Vector size

98−1010||u(k)||0||x(k)||27−20

1065−30

104OMP
L1/L2 (i)L1/L2 (ii)320102030

4050
k60708090

1000102030

4050
k60708090100(a) Performance ∥x(k)∥2(b) Sparsity ∥u(x(k))∥0Fig. 4.1. Results by OMP (solid) and ℓ1 /ℓ2 optimization (dash)3. Orthogonal Matching Pursuit. The optimization (2.1) can be rewritten
as follows:()u x(k) , arg min ∥u∥0 subject to ∥Gu − Hx(k)∥22 ≤ x(k)⊤ W x(k),(3.1)
u∈RN

where G , Q̄1/2 Φ and H , −Q̄1/2 Υ. To solve this combinatorial optimization,
we adopt an iterative greedy algorithm called Orthogonal Matching Pursuit (OMP)[3]. The algorithm is very simple and significantly faster than exhaustive search.
Moreover, OMP always gives a vector in the feasible set of the optimization (2.1), andhence the networked control system will be asymptotically stable by Theorem 2.1.
4. Example. To show the effectiveness of the proposed method, we run 500
simulations with a fixed 4-th order unstable plant (the poles are −1.4396, 1.0808 ±0.6664i, and 0.0220). The packet size N is 10. We generate a packet dropout at eachtime k with dropout probability 1/2 (if there have been N − 1 consecutive dropouts,
we set the next dropout probability to be 0, i.e., the dropout process is Markovian).
Figure 4.1 compares averaged results of the proposed method with that of [2]. Twoplots (i) and (ii) are displayed for the method of [2], with different design parameters
for sparsity. We can see that the OMP control exhibits asymptotic (even exponential)
stability, whereas the ℓ1 /ℓ2 method of [2] is only practically stable. The ℓ1 /ℓ2 method
produces much sparser vectors as in (i) than the OMP formulation, but the systemdoes is not asymptotically stable even if one relaxes the sparsity constraint in the ℓ1 /ℓ2
optimization as in (ii). In fact, it is proved in [2] that if the controlled plant is unstable,
asymptotic stability is impossible by the ℓ1 /ℓ2 method. The reason is that the ℓ1 /ℓ2
method amounts to considering a fixed upper bound for the inequality constraint in(2.1) or (3.1) instead of time-varying x(k)⊤ W x(k). This leads to 0-valued control
vector when ∥x(k)∥2 is sufficiently small (note that u = 0 is the sparsest vector among
all vectors).
REFERENCES[1] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, 52-4, pp. 1289–1306, Apr. 2006.
[2] M. Nagahara and D. E. Quevedo, “Sparse representations for packetized predictive networkedcontrol,” in IFAC 18th World Congress, Aug. 2011, pp. 84–89.
[3] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, “Orthogonal matching pursuit,” in Proc. the27th Annual Asilomar Conf. on Signals, Systems and Computers, Nov. 1993, pp. 40–44.
[4] D. E. Quevedo and D. Nešić, “Input-to-state stability of packetized predictive control over unreliable networks affected by packet-dropouts,” IEEE Trans. Autom. Control, 56-2, pp.
370–375, Feb. 2011.