Variance-component based sparse signal reconstruction and model selection

K. Qiu and A. Dogandžić

**
** *I**EEE Trans. Signal Processing*, vol. 58, pp. 2935-2952, Jun. 2010.

**Abstract:
**We propose a variance-component probabilistic model for sparse signal reconstruction and model selection. The
measurements follow an underdetermined linear model, where the unknown regression vector (signal) is sparse or
approximately sparse and noise covariance matrix is known up to a constant. The signal is composed of two disjoint
parts: a part with significant signal elements and the complementary part with insignificant signal elements that have
zero or small values. We assign distinct variance components to the candidates for the significant signal elements
and a single variance component to the rest of the signal; consequently, the dimension of our model’s parameter
space is proportional to the assumed sparsity level of the signal. We derive a generalized maximum likelihood
(GML) rule for selecting the most efficient parameter assignment and signal representation that strikes a balance
between the accuracy of data fit and compactness of the parameterization. We prove that, under mild conditions, the
GML-optimal index set of the distinct variance components

**Full paper download:**

(1.3 MB)

(also available
in the IEEE *Xplore* Digital Library.)

**Matlab code:****
** The Matlab code for the Expansion-compression Variance-component based method (ExCoV) proposed in the paper. All the
simulation results reported in the above paper can be reproduced from the package.
Please read the enclosed readme file as well. If you use this code in your research and publications, please refer to this paper.

(Version 2.1, last updated Dec. 29, 2009)

**Features of
ExCoV:
** ExCoV
is

- the measurement column vector and

- the sensing matrix (number of measurements by the length of signal)

and ExCoV will do the rest. For more details on using ExCoV and running the demo, please refer to the readme file in the package.

Compared with competing approaches, ExCoV performs particularly well in challenging scenarios where the noise is large or the number of measurements is small, see the mean squared error curves below.

**Illustrative Examples:
** The following videos show the reconstruction
progress of our
ExCoV
algorithm. The sparse signal of length 512
contains 20 randomly placed binary spikes, taking values -1 or +1
with equal probability. We took 100 noisy measurements using a
Gaussian sensing matrix with orthonormalized rows and zero-mean
white Gaussian noise with variance 10

Figs. 2 and 3 show the average MSEs of various methods ) as functions of the number of measurements *N*, for binary sparse signals (Fig. 2) and Gaussian sparse signals (Fig. 3). The simulated sparse signals have length 512 containing 20 randomly placed non-zero elements. The sensing matrix is Gaussian with orthonormalized rows and the measurement noise is white Gaussian with mean zero and variance 10^{-5}. To reproduce Figs. 2 and 3, please download version 2.0 of the code and run the simulation according to the readme file.

We demonstrate the reconstruction of the Shepp-Logan phantom of size 128 by 128 in Fig. 4 (a) from tomographic projections. The elements of the measurements are 2-D discrete Fourier transform (DFT) coefficients of the phantom image in Fig. 4 (a) sampled over a star-shaped domain, as illustrated in Fig.4 (b). We use Haar wavelet as the sparsifying basis and the effective sensing matrix for the sparse wavelet coefficients is a composition of selected rows of 2-D DFT matrix specified by the star shape in Fig.4 (b) and the inverse Haar wavelet matrix. Fig.4 (c)-(f) present the reconstructed images from the 30 radial lines given in Fig.4 (b) by filtered back-projection, normalized IHT, GPSR and approximate ExCoV, respectively. In Fig. 5, we vary the number of radial lines from 26 to 43, and, consequently, the measurement ratio N/m from 0.19 to 0.31. The codes for this tomographic imaging example have been included in the Version 2.1 package.

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

**Follow-up work:****
**Zhilin Zhang conducted additional simulation experiments that include comparison with ExCoV.