Mar 28, 2015

Discreteness and Sparsity

Discrete signals may be sparse, whereas sparse signals may not be discrete.

Let us consider the following signal:
   x = [1,1,-1,1,-1,-1,1,1];
This is a discrete signal generated from an alphabet {1,-1}. This is obviously not sparse, but if we transform this into
   x - 1 = [0,0,-2,0,-2,-2,0,0]
we have a sparse signal. Also,
   x + 1 = [2,2,0,2,0,0,2,2]
is sparse. Let's adapt this idea to discrete signal reconstruction.

Discrete Signal Reconstruction  
Find the original n-dimensional discrete signal x over a finite alphabet
   X = {r1,r2,...,rL}
with its probability distribution
   P(rj) = pj,   0 < pj <1,   pp+ ... + p= 1
from incomplete linear measurements
   y = Ax
where A is an m-times-n matrix (m < n).

In this problem, each vector x - rj is sparse, and hence its ell-1 norm may be small if the probability pj is large. This observation leads to optimization with the sum of absolute values (SOAV):

  minimize   p1||x - r1||1 + p2||x - r2||1 +...+ pL||x - rL||1
  subject to   y = Ax

Let's apply this to binary-valued image reconstruction. The following is a 37x37-pixel binary image disturbed by random Gaussian noise.

Then we transform this into frequency-domain data via discrete Fourier transform (DFT), and then randomly down-sample rows to generate half-size data. Then apply the SOAV optimization to reconstruct the original binary image. The following is the result.

For comparison, we also use the basis pursuit (BP) that minimizes the ell-1 norm of x instead of the sum of absolute values. The following is the result of BP:

This is quite bad since BP only uses the property of sparsity in the original image while the SOAV approach takes the discreteness into account.

If you are interested in this work, please see the original paper:
M. Nagahara, Discrete Signal Reconstruction by Sum of Absolute Values, IEEE Signal Processing Letters, vol. 22 no. 10, pp. 1575-1579, Oct 2015 (to appear)
PDF can be downloaded from here and the MATLAB codes are available here.

Sep 7, 2014

Nice restaurants in Cape Town

IFAC world congress 2014 was held at Cape Town International Convention Centre (CTICC), Cape Town, South Africa. I attended this congress in this summer and enjoyed restaurants around CTICC. Today's post is on nice restaurants around CTICC that I recommend to go.

If you stay near CTICC, then basically Waterfront gives you nice restaurants. I went to this restaurant twice, because they offer quite nice seafoods. Also, this restaurant has a great view of the table mountain from tables outside (see the picture above).

This restaurant is also situated in Waterfront. Nice seafoods and wines. In particular, I recommend KingKlipone of the most popular eating fish in South Africa.

Daniel, a friend of mine, invited 18 people including me to this restaurant. Meat is absolutely nice, in fact, this was the best meat I've ever had. At the time, I met Song from Hong Kong, who is also a friend of Daniel, and a reader of this blog! Amazing!! This restaurant is located in Sea Point, which approximately five minutes' drive from CTICC.

Bon appetit!

Aug 21, 2014

Maximum Hands-Off Control

Sparsity is also important in control systems.

In particular, sparse control, called hands-off control, is proposed for saving energy and reducing CO2 emissions in control systems. For example, a hybrid vehicle, Toyota Prius (displayed above), uses this control. The internal combustion engine is stopped (control = zero; sparse control) when the vehicle is at a stop or the speed is lower than a preset threshold, and the electric motor is alternatively used. See also Hands-off Control as Green Control.

Recently, it has been proved that the sparsest (or L0 optimal) control among all admissible controls is L1 optimal (see L0/L1 Equivalence in Optimal Control). Based on this, hands-off control is extended to feedback control in
M. Nagahara, D. E. Quevedo, D. Nesic, Maximum Hands-Off Control: A Paradigm of Control Effort Minimization, IEEE Transactions on Automatic Control, Vol. 61, No. 4, 2016 (to appear) (PDF is here).
The abstract reads:
In this paper, 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 short support per unit time. The maximum hands-off control is the minimum support (or sparsest) per unit time among all controls that achieve control objectives. For finite horizon control, we show the equivalence between the maximum hands-off control and L1-optimal control under a uniqueness assumption called normality. This result rationalizes the use of L1 optimality in computing a maximum hands-off control. We also propose an L1/L2-optimal control to obtain a smooth hands-off control. Furthermore, we give a self-triggered feedback control algorithm for linear time-invariant systems, which achieves a given sparsity rate and practical stability in the case of plant disturbances. An example is included to illustrate the effectiveness of the proposed control.
A MATLAB code for the simulation is available here.


Aug 14, 2014

Textbooks on Compressed Sensing

Today, I'd like to list textbooks on compressed sensing and related topics.
This list is far from complete, but I believe this helps a beginner take the first step.

Y. C. Eldar and G. Kutyniok (Editors),
Cambridge University Press, June, 2012
ISBN-13: 978-1107005587
My comment: The introduction chapter (Chapter 1) is especially nice.

M. Elad (Author)
Springer, August, 2010.
ISBN-13: 978-1441970107
My comment: A nice introduction to sparse representation in signal and image processing.

S. Mallat (Author)
Academic Press, 3rd edition, December, 2008.
ISBN-13: 978-0123743701
My comment: Read this book and be a master of wavelet. You can!

S. Foucart and H. Rauhut (Authors)
Birkhäuser, August, 2013.
ISBN-13: 978-0817649470
My comment: If you are interested in the theory of compressed sensing, this book will be of help.

H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, H. Wolkowicz (Editors)
Springer, June, 2011.
ISBN-13: 978-1441995681
My comment: This book gives you fancy methods to solve sparse optimizations (e.g. L1/L2 optimization)

J.-L. Starck, F. Murtagh, and J. M. Fadili (Authors)
Cambridge University Press, May 2010.
ISBN-13: 978-0521119139
My comment: Sparsity has many applications in image and signal processing.


A related blog entry is here.

Jul 30, 2014

Sparse Packetized Predictive Control for Networked Control over Erasure Channels

A new paper on sparsity-based control has been published:

M. Nagahara, D. E. Quevedo, and J. Ostergaard,
Sparse Packetized Predictive Control for Networked Control over Erasure Channels,
IEEE Transactions on Automatic Control, vol. 59, no. 7, pp. 1899-1905, July 2014. 

PDF can be downloaded from arxiv.

The abstract reads:
We study feedback control over erasure channels with packet-dropouts. To achieve robustness with respect to packet-dropouts, the controller transmits  data packets   containing plant input predictions, which minimize a finite horizon cost function. To reduce the data size of packets, we propose to adopt sparsity-promoting optimizations, namely, ell-1/ell-2 and  ell-2-constrained ell-0 optimizations,  for which efficient algorithms exist. We show 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.
A corresponding blog post is here.

Jul 24, 2014

L1 Control Theoretic Smoothing Splines

The control theoretic spline is a bridge between control and signal processing, as mentioned in a previous blog post. This technique is extended to robust and sparse splines via L1 optimality:
M. Nagahara and C. F. Martin,
L1 Control Theoretic Smoothing Splines,
IEEE Signal Processing Letters, 2014. (accepted)
The robustness is against outliers in data, while the sparsity is for representation of a curve with smaller number of parameters.
The abstract reads
In this paper, we propose control theoretic smoothing splines with L1 optimality for reducing the number of parameters that describes the fitted curve as well as removing outlier data. A control theoretic spline is a smoothing spline that is generated as an output of a given linear dynamical system. Conventional design requires exactly the same number of base functions as given data, and the result is not robust against outliers. To solve these problems, we propose to use L1 optimality, that is, we use the L1 norm for the regularization term and/or the empirical risk term. The optimization is described by a convex optimization, which can be efficiently solved via a numerical optimization software. A numerical example shows the effectiveness of the proposed method.
The MATLAB codes are available here.
PDF is here.