CS:The long entry of the week in Compressive Sensing

We first today's entry with an improved summary on Fast Random Projections by Edo Liberty, then we have several papers and finally a PhD studentship position.

Complexity of Unconstrained L2-Lp Minimization by Xiaojun Chen, Dongdong Ge, Zizhuo Wang, Yinyu Ye. The abstract reads:

We consider the unconstrained L2-Lp minimization: find a minimizer of kAx−bk22+λkxkppfor given A ∈ Rm×n, b ∈ Rm and parameters λ > 0, p ∈ [0, 1). This problem has been studied extensively in variable selection and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the L2-Lp problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function k · kpp. In this paper, we show that the Lq-Lp minimization problem is strongly .NP-hard for any p ∈ [0, 1) and q ≥ 1, including its smoothed version. On the other hand,we show that, by choosing parameters (p, λ) carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.

Photoacoustic image reconstruction based on Bayesian compressive sensing algorithm by Mingjian Sun, Naizhang Feng, Yi Shen, Jiangang Li, Liyong Ma, and Zhenghua Wu. The abstract reads:

The photoacoustic tomography (PAT) method, based on compressive sensing (CS) theory, requires that, for the CS reconstruction, the desired image should have a sparse representation in a known transform domain. However, the sparsity of photoacoustic signals is destroyed because noises always exist. Therefore, the original sparse signal cannot be effectively recovered using the general reconstruction algorithm. In this study, Bayesian compressive sensing (BCS) is employed to obtain highly sparse representations of photoacoustic images based on a set of noisy CS measurements. Results of simulation demonstrate that the BCS-reconstructed image can achieve superior performance than other state-of-the-art CS-reconstruction algorithms.

Multidimensional Chebyshev spaces, hierarchy of infinite-dimensional spaces and Kolmogorov-Gelfand widths by Ognyan Kounchev. The abstract reads:

Recently the theory of widths of Kolmogorov (especially of Gelfand widths) has received a great deal of interest due to its close relationship with the newly born area of Compressed Sensing. It has been realized that widths reflect properly the sparsity of the data in Signal Processing. However fundamental problems of the theory of widths in multidimensional Theory of Functions remain untouched, and their progress will have a major impact over analogous problems in the theory of multidimensional Signal Analysis. The present paper has three major contributions:

1. We introduce Multidimensional Chebyshev spaces, based on solutions of higher order elliptic equation, as a generalization of the onedimensional Chebyshev systems, more precisely of the ECT–systems.

2. Based on that we introduce a new hierarchy of infinite-dimensional spaces for functions defined in multidimensional domains; we define corresponding generalization of Kolmogorov’s widths.

3. We generalize the original results of Kolmogorov by computing the widths for special ”ellipsoidal” sets of functions defined in multidimensional domains

Structured Sparsity via Alternating Directions Methods by Zhiwei (Tony) Qin, Donald Goldfarb. The abstract reads:

 We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty l1=l2-norm and the l1=l1-norm. We propose a uni ed framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be e ciently solved. As the core building-block of this framework, we develop new algorithms using an alternating partial-linearization/splitting technique, and we prove that the accelerated versions of these algorithms require O(1p) iterations to obtain an  -optimal solution. To demonstrate the e ciency and relevance of our algorithms, we test them on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.

Spatially Regularized Compressed Sensing for High Angular Resolution Diffusion Imaging by Oleg Michailovich, Rathi, Y.; Dolui, S.. The abstract reads:

Despite the relative recency of its inception, the theory of compressive sampling (aka compressed sensing) (CS) has already revolutionized multiple areas of applied sciences, a particularly important instance of which is medical imaging. Specifically, the theory has provided a different perspective on the important problem of optimal sampling in magnetic resonance imaging (MRI), with an ever-increasing body of works reporting stable and accurate reconstruction of MRI scans from the number of spectral measurements which would have been deemed unacceptably small as recently as five years ago. In this paper, the theory of CS is employed to palliate the problem of long acquisition times, which is known to be a major impediment to the clinical application of high angular resolution diffusion imaging (HARDI). Specifically, we demonstrate that a substantial reduction in data acquisition times is possible through minimization of the number of diffusion encoding gradients required for reliable reconstruction of HARDI scans. The success of such a minimization is primarily due to the availability of spherical ridgelet transformation, which excels in sparsifying HARDI signals. What makes the resulting reconstruction procedure even more accurate is a combination of the sparsity constraints in the diffusion domain with additional constraints imposed on the estimated diffusion field in the spatial domain. Accordingly, the present paper describes an original way to combine the diffusion- and spatial-domain constraints to achieve a maximal reduction in the number of diffusion measurements, while sacrificing little in terms of reconstruction accuracy. Finally, details are provided on an efficient numerical scheme which can be used to solve the aforementioned reconstruction problem by means of standard and readily available estimation tools. The paper is concluded with experimental results which support the practical value of the proposed reconstruction methodology.

Energy-Efficient ECG Acquisition in Body Sensor Networks based on Compressive Sensing by Wei Zhuang, Tianxu Du, Huiqiang Tang. The abstract reads:

This paper presents a novel ECG signal measuring approach using compressive sensing method. The signal representing sparsity in any orthogonal basis can be well recovered using minimize L1 norm optimization, while satisfying the RIP condition for the measurement matrix   and orthogonal basis  . First, based on this theorem, an analysis for evaluating the sparsity of ECG signal in orthogonal basis domain is proposed. A set of ECG samples from MIT-BIH medical database are adopted into Fast Fourier Transformation (FFT) process. The results indicate these signals can be well represented in sparsity using conventional orthogonal transforms. Second, the lightweight recovery algorithm is proposed based on orthogonal matching pursuit using iterative function and least squared approximation. The simulation results show that the special features in ECG including QRS complex, R-R interval, PQ and ST duration, can be well recovered with negligible norm error. It also indicates that using this approach can significantly save the total power of ECG acquisition. 

On the Exponential reproducing Kernels for Sampling Signals with Finite Rate of Innovation by Jose Antonio Uriguen, Pier-Luigi Dragotti and Thierry Blu. The abstract reads:

The theory of Finite Rate of Innovation (FRI) broadened the traditional sampling paradigm to certain classes of parametric signals. In the presence of noise, the original procedures are not as stable, and a different treatment is needed. In this paper we review the ideal FRI sampling scheme and some of the existing techniques to combat noise. We then present alternative denoising methods for the case of exponential reproducing kernels. We first vary existing subspace-based approaches. We also discuss how to design exponential reproducing kernels that are most robust to noise

Sampling Curves with Finite Rate of Innovation by Hanjie Pan, Thierry Blu, Pier-Luigi Dragotti. The abstract reads:

We focus on a specific class of curves that can be parametrized with finite variables in two dimensions. The corresponding indicator plane, which is a binary image, has infinite bandwidth and can not be sampled and perfectly reconstructed with classical sampling theory. In this paper, we illustrate that it is possible to recover parameters from finite samples of the indicator plane and have a perfect reconstruction of the indicator plane. The algorithm presented here extends the application of FRI signals to multi-dimensional cases and may find its application in fields, like super-resolution.

PhD fellowships in statistical signal processing and machine learning

PhD fellowships in statistical signal processing and machine learning
Employer: Signal Processing Group, Universidad Carlos III
Location: Madrid (Madrid), Spain
Posted: May 04, 2011 Expires: Aug 04, 2011
Description:
The Signal Processing Group (SPG) of Universidad Carlos III opens two pre-doctoral positions for research in one or more of the following areas
- sensor networks,
- compressed sensing,
- localization and tracking,
- Monte Carlo statistical methods,
- distributed inference and
- machine learning.
SPG is a dynamic team conducting both pre-competitive and applied research in the fields of signal and image detection and classification, machine learning, Monte Carlo methods and information theory, with financial support both from public administrations (Spanish and European) and the industry.
The Department of Signal Theory & Communications is integrated into the Polytechnic School of Universidad Carlos III (www.uc3m.es/uc3m/eng/index-eng.html), where several Engineering degrees are imparted, and located in Leganés, a lively town 15 kms away from the center of Madrid and well communicated by public transport (train, subway and bus).

Pre-doctoral positions: Potential candidates should hold an Engineering, Mathematics, Physics or related degree. Successful applicants are expected to enroll the Department's Master and Ph. D. Program on Multimedia & Communications:
http://www.uc3m.es/portal/page/portal/postgrado_mast_doct/masters/interuniver_multmed_comunica
Working languages are English and Spanish, but most courses are taught in Spanish. Initial salary around 1,300 euros/month, and increasing yearly through a 4-year period depending on the student's progress and involvement in research projects.
To apply:
Please, contact:

Dr. Joaquín Míguez,
Associate Professor
Department of Signal Theory & Communications
Universidad Carlos III de Madrid

e-mail: joaquin.miguez@uc3m.es
www.tsc.uc3m.es/~jmiguez
tlf: +34 91 624 8736

Image Credit: NASA/JPL/Space Science Institute, W00067151.jpg was taken on May 07, 2011 and received on Earth May 08, 2011. The camera was pointing toward SATURN at approximately 1,802,117 kilometers away, and the image was taken using the MT2 and CL2 filters.