## Monday, April 04, 2011

### CS: Bob's adventures, Compressed Sensing based Method for ECG Compression, two theses and a postdoc

Bob's excellent adventures is featured on his blog and he has summarized everything in an arxiv paper entitled A Study on Sparse Vector Distributions and Recovery from Compressed Sensing by Bob L. Sturm. The abstract reads:

I empirically investigate the variability of several recovery algorithms on the distribution underlying the sparse vector sensed by a random matrix. a dependence that has been noted before, but, to my knowledge, not thoroughly investigated. I find that $\ell_1$-minimization \cite{Chen1998} and tuned two-stage thresholding \cite{Maleki2010} (subspace pursuit \cite{Dai2009} without the use of a sparsity oracle) are the most robust to changes in the sparse vector distribution; but they are outperformed to a large degree by greedy methods, such as orthogonal matching pursuit \cite{Pati1993} for sparse vectors distributed Normal and Laplacian. I also find that selecting the best solution from those produced by several recovery algorithms can significantly increase the probability of exact recovery.

Eric Trammel les us know on Twitter of a new paper and code in  Video Compressed Sensing with Multihypothesis by Eric Tramel and James E. Fowler. The abstract reads:
The compressed-sensing recovery of video sequences driven by multihypothesis predictions is considered. Specifically, multihypothesis predictions of the current frame are used to generate a residual in the domain of the compressed-sensing random projections. This residual
being typically more compressible than the original frame leads to improved reconstruction quality. To appropriately weight the hypothesis predictions, a Tikhonov regularization to an ill-posed least-squares optimization is proposed. This method is shown to outperform both recovery of the frame independently of the others as well as recovery based on single-hypothesis prediction.

The attendant code is here.

Sergey wonders about L1, robust statistics and compressed sensing

Over the week-end, I found one paper and two theses:

Compressed Sensing based Method for ECG Compression by Luisa F. Polania, Rafael E. Carrillo, Manuel Blanco-Velasco and Kenneth E. Barner. The abstract reads:
Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals that enables sampling rates signiﬁcantly below the classical Nyquist rate. Based on the fact that electrocardiogram (ECG) signals can be approximated by a linear combination of a few coefﬁcients taken from a Wavelet basis, we propose a compressed sensing-based approach for ECG signal compression. ECG signals generally show redundancy between adjacent heartbeats due to its quasi-periodic structure. We show that this redundancy implies a high fraction of common support between consecutive heartbeats. The contribution of this paper lies in the use of distributed compressed sensing to exploit the common support between samples of jointly sparse adjacent beats. Simulation results suggest that compressed sensing should be considered as a plausible methodology for ECG compression.

Yaniv Plan's thesis Compressed sensing, sparse approximation, and low-rank matrix estimation. The abstract reads;
The importance of sparse signal structures has been recognized in a plethora of applications ranging from medical imaging to group disease testing to radar technology. It has been shown in practice that various signals of interest may be (approximately) sparsely modeled, and that sparse modeling is often beneficial, or even indispensable to signal recovery. Alongside an increase in applications, a rich theory of sparse and compressible signal recovery has recently been developed under the names compressed sensing (CS) and sparse approximation (SA). This revolutionary research has demonstrated that many signals can be recovered from severely undersampled measurements by taking advantage of their inherent low-dimensional structure. More recently, an offshoot of CS and SA has been a focus of research on other low-dimensional signal structures such as matrices of low rank. Low-rank matrix recovery (LRMR) is demonstrating a rapidly growing array of important applications such as quantum state tomography, triangulation from incomplete distance measurements, recommender systems (e.g., the Netflix problem), and system identification and control. In this dissertation, we examine CS, SA, and LRMR from a theoretical perspective. We consider a variety of different measurement and signal models, both random and deterministic, and mainly ask two questions. How many measurements are necessary? How large is the recovery error? We give theoretical lower bounds for both of these questions, including oracle and minimax lower bounds for the error. However, the main emphasis of the thesis is to demonstrate the efficacy of convex optimization---in particular l1 and nuclear-norm minimization based programs---in CS, SA, and LRMR. We derive upper bounds for the number of measurements required and the error derived by convex optimization, which in many cases match the lower bounds up to constant or logarithmic factors. The majority of these results do not require the restricted isometry property (RIP), a ubiquitous condition in the literature.

We propose the use of compressive sensing (CS) in the context of a multi-input multioutput (MIMO) radar system that is implemented by a small scale network. Each receive node compressively samples the incoming signal, and forwards a small number of samples to a fusion center. At the fusion center, all received data are jointly processed to extract information on the potential targets via the CS approach. Since CS-based MIMO radar would require many fewer measurements than conventional MIMO radar for reliable target detection, there would be power savings during the data transmission to the fusion center, which would prolong the life of the wireless network. First, we propose a direction of arrival (DOA)-Doppler estimation approach. Assuming that the targets are sparsely located in the DOA-Doppler space, based on the samples forwarded by the receive nodes, the fusion center formulates an ℓ1-optimization problem, the solution of which yields the target DOA-Doppler information. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than required by conventional approaches. Second, we propose the use of step frequency to CS-based MIMO radar, which enables high range resolution, while transmitting narrowband pulses. For slowly moving targets, a novel approach is proposed that achieves significant complexity reduction by successively estimating angle-range and Doppler in a decoupled fashion and by employing initial estimates to further reduce the search space. Numerical results show that the achieved complexity reduction does not hurt resolution. Finally, we investigate optimal designs for the measurement matrix that is used to linearly compress the received signal. One optimality criterion amounts to decorrelating the bases that span the sparse space of the incoming signal and simultaneously enhancing signal-to-interference ratio (SIR). Another criterion targets SIR improvement only. It is shown via simulations that, in certain cases, the measurement matrices obtained based on the aforementioned criteria can improve detection accuracy as compared to the typically used Gaussian random measurement matrix.

Also I found this position:
Postdoctoral Positions in Wireless Communications / Media Security
DESCRIPTION
The Signal Processing in Communications Group (GPSC, www.gts.tsc.uvigo.es/gpsc), headed by Prof. Fernando Pérez-González and affiliated using the Department of Signal Concept and Communications at University of Vigo, Spain, invites applications for postdoctoral positions within the fields of wireless communications and multimedia safety. The selected candidates will join GPSC to investigate fundamentals and algorithm design/evaluation for communication, sensor networks and information forensics. Places of particular curiosity contain:
* Sensor networks
* Watermarking
* Compressed Sensing
GPSC is shaped by six faculty members, MSc and PhD pupils, and postdocs, and participates in many study jobs funded by the European Commission and the Spanish Authorities. Among these, the COMONSENS project (www.comonsens.org), led at University of Vigo by Prof. Roberto López-Valcarce, integrates investigators from 10 distinct top rated investigation institutions in Spain. GPSC members also actively collaborate together with the Galician R&D Center in Advanced Telecommunications (GRADIANT, www.gradiant.org) in diverse contracts with ICT companies. Thus, the selected candidates will enjoy unique opportunities to participate in exciting analysis assignments with both industry and academia.
DESIRABLE BACKGROUND
* A Ph.D. degree in Electrical Engineering is required.
* Applications from candidates with three or more years of postdoctoral experience will be given preference.
* Knowledge and experience in sensor networks, cognitive radio, watermarking & data hiding algorithms, multimedia forensics and/or compressed sensing
* Good verbal and written skills in English are required
* Strong publications in international conferences and journals in the area of communications
* Postdoctoral experience in a recognized group with expertise within the field is a plus
* Experience in the organization, management and training of technical staff/students is a plus
* Communication, computing and interpersonal skills are important
* Capacity to work both independently and within a team
CONTRACT CONDITIONS
The initial appointment will be for one year, with annual renewaldependent on performance. Expected start date is April 2011. Successful applicants will be offered a yearly gross salary from the range of 33,000 -40,000 €, as well as health benefits.
APPLICATIONS
Interested candidates may apply to Prof. Roberto López-Valcarce(valcarce[ at ]gts.uvigo.es). Applications should incorporate electronic copies of the following:
* A cover letter addressing the specified job qualifications.
* A letter of recommendation by a senior Professor/Researcher.
* A copy of the publication deemed as best representative of the candidate’s creative study.
Priority consideration will be given to applications received by late March, 2011.
Applications will be accepted until position is filled.
Prof. Roberto López?Valcarce
Departamento de Teoría de la Señal y Comunicaciones
ETSET. University of Vigo, 36310 Vigo. Spain
Phone: +34 986 818659,
e?mail: valcarce[ at ]gts.uvigo.es

Credit: NASA/JPL/University of Arizona

Icy Craters on Mars
ESP_016954_2245

Newly formed impact craters have been discovered on Mars over the past several years. When craters form over dusty regions the impact blast blows the bright dust off the terrain over a wide area, leaving a dark spot.