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.

Compressed Sensing: Theory and Applications

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.

Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing

M. Elad (Author)

Springer, August, 2010.

ISBN-13: 978-1441970107
My comment: A nice introduction to sparse representation in signal and image processing.

A Wavelet Tour of Signal Processing: The Sparse Way

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!

A Mathematical Introduction to Compressive Sensing

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.

Fixed-Point Algorithms for Inverse Problems in Science and Engineering

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)

Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity

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.

Enjoy!

A related blog entry is here.

MIT's Visual Microphone System

I can understand the theory, but the technology is quite unbelievable!
See Your Candy Wrappers are Listening.

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 L¹ 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.

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 (t₁, y₁),..., (t_n,y_n) 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/s² 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.

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:

Compressed sensing for communication systems

Compressed sensing: a new trend in control

Recent papers on compressed sensing for control systems

Compressed sensing meets control systems

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

Optimal Design of Delta-Sigma Modulators

Control theory sometimes gives a powerful tool for solving problems in signal processing. LMI (Linear Matrix Inequality) is one of them. Today, I'd like to introduce my paper (preprint PDF) on LMI application to delta-sigma modulation:

M. Nagahara and Y. Yamamoto, Frequency Domain Min-Max Optimization of Noise-Shaping Delta-Sigma Modulators, IEEE Trans. on Signal Processing, Vol. 60, No. 6, pp. 2828-2839, 2012.

What is delta-sigma modulation? The Wikipedia entry reads:

Delta-sigma (ΔΣ; or sigma-delta, ΣΔ) modulation is a method for encoding analog signals into digital signals or higher-resolution digital signals into lower-resolution digital signals. The conversion is done using error feedback, where the difference between the two signals is measured and used to improve the conversion. The low-resolution signal typically changes more quickly than the high-resolution signal and it can be filtered to recover the high-resolution signal with little or no loss of fidelity. 

To filter out the quantization noise from low-resolution quickly-changing signals, it is essential to push away the quantization noise out of the frequency band of the original signal. In other words, it should be sufficiently attenuated the noise transfer function (NTF) from the quantization noise to the modulator output (before the lowpass filter).

Although a delta-sigma modulator ia a highly nonlinear system, designing is a linear problem like filter design; shape the frequency response of NTF.

Conventionally, NTF is shaped such that the squared norm of the magnitude (i.e., H² norm) of NTF on the frequency band of interest. As I noted in my past entry that an H²-based system shows very nice performance for almost all frequencies but is fragile for a frequency, say f₀ [Hz] (see the picture below).

To avoid this, we introduced the H^∞ norm to uniformly attenuate the magnitude on a frequency band. A difficulty is that this problem is not a standard H^∞ problem since it does not optimize over the whole frequency band [0,π) but on a subset [0,Ω), Ω<π. You cannot use the standard hinfsyn
command in MATLAB. How to solve it?

The solver is found in control theory, generalized KYP (GKYP) lemma. This solves our problem via LMI (linear matrix inequality).

The picture below shows two plots: the Bode magnitude plot of NTF designed by GKYP (red line) and by H²-based zero optimization (blue line). The magnitude by GKYP is uniformly attenuated over the low frequency range, while that by H² shows peaks in this band. The difference between the two maximal magnitudes at the frequency ω = π/32 is approximately 11.2 (dB), and the difference at low frequencies is about 12.4 (dB).

The paper is available here.
MATLAB codes are available here.
GKYP for signal processing is also discussed in this article.

A related blog entry is here.

Beyond Shannon with your iPhone

I posted an entry about beyond-Shannon signal reconstruction by H ^∞ optimization. Based on this method, an iPhone application, FANTABIT, has been designed and recently released. The iTunes page says

Automatically upgrade your flat, compressed iTunes music library into rich sounding music with the FANTABIT player!

Listen to your iTunes library with in full dynamic range using the FANTABIT audio enhancing technology and player. This high quality music player is for discerning audiophiles who are tired of listening to uninspiring, compressed music. Install the FANTABIT player and your iTunes music library is instantly converted.

Audiophiles can take full advantage of expensive listening equipment (high-end cables, speakers, headphones, etc.,) to listen to the fully restored music and sounds from their iTunes library using the FANTABIT player. FANTABIT allows you to take full advantage of your system, immersing yourself in the richness of your favorite music.

Compressed sensing (CS) is another beyond-Shannon method, which, to my knowledge, has not been applied to such real-time audio. This is mostly due to the computational cost of optimization in CS reconstruction. Actually, the H^∞ reconstruction requires just up-sampling and filtering, which is much faster than CS.


Related entries:
Beyond Shannon: infinity versus zero
Zero, one, and infinity in compressed sensing

Causality in signal processing

Often, signal processing theorems give a non-causal filter. For example, see the following paper:

M. Unser, A. Aldroubi, and M. Eden,
B-spline Signal Processing: Part II---Efficient Design and Applications,
Signal Processing, IEEE Transactions on , vol.41, no.2, pp.834-848, Feb 1993

A non-causal filter as above is no problem in image processing. However, in a real time system, in particular, in a feedback loop, non-causality should cause a problem of implementation. The simplest way to avoid this is truncation of the non-causal part of the filter impulse response, say, {f(n): n<0}. This absolutely degrades the filter performance, and the second simplest is to truncate {f(n): n<-N} (often with a window) and shift the residual by N.

Recently, much more sophisticated methods are proposed, via constraint least squares, which is related to H² optimization:

M. Unser and M. Eden,
FIR approximations of inverse filters and perfect reconstruction filter banks,
Signal Processing, Vol. 36, No. 2, pp. 163-174, 1994.

and via H^∞ optimization:

M. Nagahara and Y. Yamamoto,
H∞ optimal approximation for causal spline interpolation,
Signal Processing, Vol. 91, No. 2, pp. 176-184, 2011.

As I mentioned in a previous entry that H^∞ optimization leads to robustness against signal uncertainty. If you like robustness (or if you don't like risk-taking behavior), then you must choose H^∞! You can use MATLAB codes for the H^∞ design here.

H2 versus H∞

In signal processing, H² and H^∞ norms are most important measures for system performance. In this entry, I try to explain the difference between them in view of filter design.

For a stable and causal system F(z), the H² norm is defined by

This is the average (or root-mean-square) value of the magnitude of the frequency response of F(z).

On the other hand, the H^∞ norm is defined by

This is the maximum value of the magnitude of the frequency response of F(z).

Now, let us consider the following inverse-filtering problem:

Given a filter H(z), find another filter K(z) such that H(z)K(z) ≈ 1.

For this problem, we can use the above two norms.  By the H² norm, the problem is formulated as

(H2) Find stable and causal K(z) that minimizes || H(z)K(z)-1 ||₂

By the H^∞ norm, the problem is also formulated as

(Hinf) Find stable and causal K(z) that minimizes || H(z)K(z)-1 ||_∞

The difference is that (H2) tries to minimize the average magnitude of the error system H(z)K(z)-1 while (Hinf) tries to minimize the maximum magnitude.  The following picture shows an example of the two designs.

The blue line is the magnitude of the frequency response of the error H(z)K(z)-1 by the H² design. The error is very small at almost all frequencies but is very large around a frequency, say f₀. On the other hand, the red line is the error magnitude by H^∞ design, which is uniformly small since the H^∞ optimization is a minmax one that tries to make the response as flat as possible. The average value by H² is smaller than by H^∞ and the maximum value by H^∞ is smaller than by H².

By this picture, the difference is clear.

H²-designed filter shows very nice performance for almost all frequencies but is fragile for the frequency f₀. Hence, H² is the better if it is quite certain that the input signals do not contain frequency components around f₀.  On the other hand, H^∞-designed filter guarantees a certain error level for all frequencies. In other words, H^∞ optimization leads to robustness against uncertainty in the frequency components of input signals.

For details, please check this article, and matlab codes for the article.

Zero, one, and infinity in compressed sensing

I am very happy I got many comments for my first "technical" blog, where I made a question on relationship between zero and infinity norms in CS (compressed sensing).

Igor pointed out his blog entries (here and here)  in his comment.  According to the entry, an L-infinity optimization may produce a vector the elements of which are sticked to ±||x||_∞.  Applying DFT to such a vector, e.g., x=(1,1,...,1), result in a sparse vector in the Fourier domain.  This may be a simple explanation why the infinity norm is related to CS.

Mahesh and Thomas pointed out the infinity norm is also used in the Dantzig selector. This is based on the fact that L-1 (ell-1) is the dual vector space of L-infinity (ell-infinity).  This is yet another link between zero and infinity (note that L-1 is related to L-0 by so many studies on CS). This also interests me very much.

Beyond Shannon: infinity versus zero

Here is a recent paper on signal reconstruction:

Yamamoto, Y.; Nagahara, M.; Khargonekar, P.P.
Signal Reconstruction via  H-infinity Sampled-Data Control Theory—Beyond the Shannon Paradigm,
Signal Processing, IEEE Transactions on , vol.60, no.2, pp.613-625, Feb. 2012.

This paper presents a new method for signal reconstruction by leveraging sampled-data control theory. We formulate the signal reconstruction problem in terms of an analog performance optimization problem using a stable discrete-time filter. The proposed H^∞ performance criterion naturally takes inter-sample behavior into account, reflecting the energy distributions of the signal. We present methods for computing optimal solutions which are guaranteed to be stable and causal. Detailed comparisons to alternative methods are provided. We discuss some applications in sound and image reconstruction.

This paper proposes "beyond Shannon" signal reconstruction based on H^∞ norm. Recently, another "beyond Shannon" method, called compressed sensing (CS),  is widely studied in signal processing. It is interesting that in CS they use so-called 0-"norm," which is extremely-different from infinity norm.

Is there  a link between infinity and zero?


Related entries:
Beyond Shannon with your iPhone
Zero, one, and infinity in compressed sensing