CS: The long post of the week.

First things first, the Compressive Sensing Group on LinkedIn has reached 472 members. If you are a student looking for work or a post-doc I would advise you to be on LinkedIn and also join that group. To the industry folks, joining the group is a good way to show your interest in this new and exciting area of future growth for you and your company. Since LinkedIn is a pretty conservative social network, I would not expect too many people contacting you for a job without much thoughts from the requester. In the meantime, all the job postings I can find are listed here in the Compressive Sensing Jobs page. Please note that I currently do not remove previous postings as they provide some sense as to where the field is going. A new post-doc position is featured at the end of this post.

In the day before yesterday's posting, I mentioned several Q&A's sites but I forgot the call for people to join on the Theoretical Computer Science one as mentioned by Suresh. It is here. They currently have 231 people committed, they need more.

As a follow-up to yesterday's remark by Waheed Bajwa, Simon Foucart sent me the following (a pdf more readable version of this is here):

Following a discussion on Restricted Isometry Constants in the complex setting, it is worth pointing out that the condition $\delta_{2 k } \lt \sqrt{2}-1 \approx 0.41421$ by Cand\`es [The restricted isometry property and its implications for compressed sensing] --- or the condition $\delta_{2 k} \lt 3/(4 + \sqrt{6}) \approx 0.4652$ by myself [A note on guaranteed sparse recovery via $\ell_1$-minimization] --- is in fact valid for the complex case, even if the polarization identity does not take the same form. Indeed, Cand\`es uses it to prove that

$$\langle \Phi u, \Phi v \rangle \le \delta_{2 k} \|u\|_2 \|v\|_2$$

if $u$ and $v$ are disjointly supported and if ${\rm supp}(u) \cup {\rm supp}(v)$
has size at most $2 k$. However, this can be seen without polarization by using the alternative expression of the Restricted Isometry Constant

$$\delta_{2 k }= \sup_{|K| \le 2k} \|\Phi_K^* \Phi_K - I\|_{2 \to 2}.$$

Indeed, with $K:={\rm supp}(u) \cup {\rm supp}(v)$, one has

\begin{eqnarray*}
\langle \Phi u, \Phi v \rangle
& = & \langle \Phi_K u_K, \Phi_K v_K \rangle - \langle u_K, v_K \rangle
= \langle (\Phi_K^* \Phi_K - I) u_K, v_K \rangle\\
& \le & \|(\Phi_K^* \Phi_K - I) u_K \|_2 \|v_K\|_2
\le \delta_{2 k } \|u_K \|_2 \|v_K\|_2 = \delta_{2 k } \|u \|_2 \|v\|_2.
\end{eqnarray*}

Speaking about real and complex settings, it is also worth pointing out that, for real measurement matrices, the recovery of all $k$-sparse vectors via $\ell_1$-minimization is independent of the underlying field, because the real and complex null space properties are equivalent, see the preprint [Real vs. complex null space properties for sparse vector recovery] by Gribonval and myself. Actually, even more is true in the context of joint sparsity, see the preprint [The null space property for sparse recovery from multiple measurement vectors] by Lai and Liu.

Thanks Simon for clearing this up.

So since this is the LPoW, here are the new papers and preprints ny webcrawler has found, enjoy:

The 22-page chapter on Compressive Optical Imaging: Architectures and Algorithms by Roummel Marcia, Rebecca Willett. Zachary Harmany is out.

Sparsity-regularized photon-limited imaging by Zachary Harmany, Roummel Marcia, and Rebecca Willett. The abstract reads:

In many medical imaging applications (e.g., SPECT, PET), the data are a count of the number of photons incident on a detector array. When the number of photons is small, the measurement process is best modeled with a Poisson distribution. The problem addressed in this paper is the estimation of an underlying intensity from photon-limited projections where the intensity admits a sparse or low-complexity representation. This approach is based on recent inroads in sparse reconstruction methods inspired by compressed sensing. However, unlike most recent advances in this area, the optimization formulation we explore uses a penalized negative Poisson loglikelihood objective function with nonnegativity constraints (since Poisson intensities are naturally nonnegative). This paper describes computational methods for solving the nonnegatively constrained sparse Poisson inverse problem. In particular, the proposed approach incorporates sequential separable quadratic approximations to the log-likelihood and computationally efficient partition-based multiscale estimation methods.

Hyperspectral target detection from incoherent projections by Kalyani Krishnamurthy, Maxim Raginsky, and Rebecca Willett. The abstract reads:

This paper studies the detection of spectral targets corrupted by a colored Gaussian background from noisy, incoherent projection measurements. Unlike many detection methods designed for incoherent projections, the proposed approach a) is computationally efficient, b) allows for spectral backgrounds behind potential targets, and c) yields theoretical guarantees on detector performance. In particular, the theoretical performance bounds highlight fundamental tradeoffs among the number of measurements collected, the spectral resolution of targets, the amount of background signal present, signal-to noise ratio, and the similarity between potential targets in a dictionary.

Gradient Projection for Linearly Constrained Convex Optimization in Sparse Signal Recovery by Zachary Harmany, Daniel Thompson, Rebecca Willett, and Roummel Marcia. The abstract reads:

The l_2-l_1 compressed sensing minimization problem can be solved efficiently by gradient projection. In imaging applications, the signal of interest corresponds to nonnegative pixel intensities; thus, with additional nonnegativity constraints on the reconstruction, the resulting constrained minimization problem becomes more challenging to solve. In this paper, we propose a gradient projection approach for sparse signal recovery where the reconstruction is subject to nonnegativity constraints. Numerical results are presented to demonstrate the effectiveness of this approach.

Compressive Acquisition of Dynamic Scenes by Aswin C. Sankaranarayanan, Pavan K. Turaga, Richard G. Baraniuk and Rama Chellappa. The abstract reads:

Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals and images that enables sampling rates significantly below the classical Nyquist rate. Despite significant progress in the theory and methods of CS, little headway has been made in compressive video acquisition and recovery. Video CS is complicated by the ephemeral nature of dynamic events, which makes direct extensions of standard CS imaging architectures and signal models infeasible. In this paper, we develop a new framework for video CS for dynamic textured scenes that models the evolution of the scene as a linear dynamical system (LDS). This reduces the video recovery problem to first estimating the model parameters of the LDS from compressive measurements, from which the image frames are then reconstructed. We exploit the low-dimensional dynamic parameters (the state sequence) and high-dimensional static parameters (the observation matrix) of the LDS to devise a novel compressive measurement strategy that measures only the dynamic part of the scene at each instant and accumulates measurements over time to estimate the static parameters. This enables us to considerably lower the compressive measurement rate considerably.
We validate our approach with a range of experiments including classification experiments that highlight the effectiveness of the proposed approach.

By the way, this link to the pdf does not work.

A Data-Driven fMRI Analysis using K-SVD Sparse Dictionary Learning by Kangjoo Lee, and Jong Chul Ye. The introduction reads:

Statistical parametric mapping (SPM) is widely used for the statistical analysis of brain activity with fMRI. However, if the general linear model employs a fixed form of a canonical HRF, the ignorance of experimental and individual variance can lead to inaccurate detection of the real activation area. A variety of data-driven methods, which combine independent component analysis (ICA) with statistical analysis of fMRI dataset, were suggested to overcome the problem, such as the `HYBICA’ approach [1] and the unified `SPM-ICA’ method [2]. However, recent study demonstrates that representation of the brain fMRI using sparse components is more promising rather than independent components [3]. Also, the real brain fMRI signal may be regarded as a combination of small set of dynamic components, where each of them has different signal patterns and sparsely distributed in each voxel. Hence, we employ the K-SVD [4], a powerful sparse dictionary learning algorithm, to decompose the neural signal into dictionary atoms with specific local responses. Using the trained sparse dictionary as a design matrix in SPM, we extract which signal components contribute to the neural activation. We show the proposed method adapts the individual variation and extract the activation better than conventional methods.

Statistical Parametric mapping of fMRI Data using Sparse Dictionary Learning by Kangjoo Lee, and Jong Chul Ye. The abstract reads:

Statistical parametric mapping (SPM) of functional magnetic resonance imaging (fMRI) uses a canonical hemodynamic response function (HRF) to construct the design matrix within the general linear model (GLM) framework. Recently, there has been many research on data-driven method on fMRI data, such as the independence component analysis (ICA). The main weakness of ICA for fMRI is its restrictive assumption, especially independence. Furthermore, recent study demonstrated that sparsity is more important than independency in ICA analysis for fMRI. Hence, we propose sparse learning algorithm, such as K-SVD, as an alternative, that decomposes the dictionary-atoms using sparsity rather than independence of the components. For the fMRI finger tapping task data, we employed the K-SVD algorithm to extract the time-course signal atoms of brain activation. The activation maps using trained dictionary as a design matrix showed tightly localized signals in a small set of brain areas.

Cryptotomography: reconstructing 3D Fourier intensities from randomly oriented single-shot diffraction patterns, N. D. Loh, M. Bogan, V. Elser, A. Barty, S. Boutet, S. Bajt, J. Hajdu, T. Ekeberg, F. R. N. C. Maia, J. Schulz, M. M. Seibert, B. Iwan, N. Timneanu, S. Marchesini, I. Schlichting, R. L. Shoeman, L. Lomb, M. Frank, M. Liang, H. N. Chapman. The abstract reads:

We reconstructed the 3D Fourier intensity distribution of mono-disperse prolate nano-particles using single-shot 2D coherent diffraction patterns collected at DESY's FLASH facility when a bright, coherent, ultrafast X-ray pulse intercepted individual particles of random, unmeasured orientations. This first experimental demonstration of cryptotomography extended the Expansion-Maximization-Compression (EMC) framework to accommodate unmeasured fluctuations in photon fluence and loss of data due to saturation or background scatter. This work is an important step towards realizing single-shot diffraction imaging of single biomolecules.

On the role of sparsity in Compressed Sensing and Random Matrix Theory by Roman Vershynin. The abstract reads:

We discuss applications of some concepts of Compressed Sensing in the recent work on invertibility of random matrices due to Rudelson and the author. We sketch an argument leading to the optimal bound (N^-(1/2)) on the median of the smallest singular value of an N x N matrix with random independent entries. We highlight the parts of the argument where sparsity ideas played a key role.

Solving Inverse Problems with Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity by Guoshen Yu, Guillermo Sapiro, and Stephane Mallat [slides are here]. The abstract reads:

A general framework for solving image inverse problems is introduced in this paper. The approach is based on Gaussian mixture models, estimated via a computationally efficient MAP-EM algorithm. A dual mathematical interpretation of the proposed framework with structured sparse estimation is described, which shows that the resulting piecewise linear estimate stabilizes the estimation when compared to traditional sparse inverse problem techniques. This interpretation also suggests an effective dictionary motivated initialization for the MAP-EM algorithm. We demonstrate that in a number of image inverse problems, including inpainting, zooming, and deblurring, the same algorithm produces either equal, often significantly better, or very small margin worse results than the best published ones, at a lower computational cost.

Matrix Completion by the Principle of Parsimony by Augusto Ferrante, Michele Pavon. The abstract reads:

Dempster's covariance selection method is extended first to general nonsingular matrices and then to full rank rectangular matrices. Dempster observed that his completion solved a maximum entropy problem. We show that our generalized completions are also solutions of a suitable entropy-like variational problem.

Decomposition Approach for Low-rank Matrix Completion by Rick Ma, Samuel Cheng. The abstract reads:

In this paper, we describe a low-rank matrix completion method based on matrix decomposition. An incomplete matrix is decomposed into submatrices which are filled with a proposed trimming step and then are recombined to form a low-rank completed matrix. The divide-and-conquer approach can significantly reduce computation complexity and storage requirement. Moreover, the proposed decomposition method can be naturally incorporated into any existing matrix completion methods to attain further gain. Unlike most existing approaches, the proposed method is not based on norm minimization nor SVD decomposition. This makes it possible to be applied beyond real domain and can be used in arbitrary fields including finite fields.

A soft-threshold filtering approach for reconstruction from a limited number of projections by Hengyong Yu and Ge Wang. The abstract reads:

In the medical imaging field, discrete gradient transform (DGT) is widely used as a sparsifying operator to define the total variation (TV). Recently, TV minimization has become a hot topic in image reconstruction and is usually implemented using the steepest descent method (SDM). SinceTVminimization with the SDM takes a long computational time, here we construct a pseudoinverse of the DGT and adapt a soft-threshold filtering algorithm, whose convergence and efficiency have been theoretically proven. Also, we construct a pseudo-inverse of the discrete difference transform (DDT) and design an algorithm for L1 minimization of the total difference. These two methods are evaluated in numerical simulation. The results demonstrate the merits of the proposed techniques.

Compressed sensing inspired image reconstruction from overlapped projections by Lin Yang, Yang Lu,and Ge Wang. The abstract reads:

The key idea discussed in this paper is to reconstruct an image from overlapped projections so that the data acquisition process can be shortened while the image quality remains essentially uncompromised. To perform image reconstruction from overlapped projections, the conventional reconstruction approach (e.g., filtered backprojection (FBP) algorithms) cannot be directly used because of two problems. First, overlapped projections represent an imaging system in terms of summed exponentials, which cannot be transformed into a linear form. Second, the overlapped measurement carries less information than the traditional line integrals. To meet these challenges, we propose a compressive sensing-(CS-) based iterative algorithm for reconstruction from overlapped data. This algorithm starts with a good initial guess, relies on adaptive linearization, and minimizes the total variation (TV). Then, we demonstrated the feasibility of this algorithm in numerical tests.

Sampling and Reconstruction of Transient Signals by Parallel Exponential Filters by H. Olkkonen and Juuso Olkkonen. The abstract reads:

This brief introduces a new method for sampling of transient analog waveforms based on the parallel exponential filters. The signal is fed to the parallel network consisting of resistor–capacitor (RC) circuits, outputs of which are simultaneously sampled. We show that N previous samples of the input signal can be reconstructed from single output samples of N parallel RC circuits. The parallel sampling method increases the sampling rate of the data acquisition system by a factor of N. In particular, the method is useful in increasing the sampling rate of the Flash-type analog-to-digital VLSI circuits. We present the parallel RC network, develop the reconstruction algorithm, and briefly describe a variety of applications such as measurement and

reconstruction of pulses produced by ultrawideband transmitters, radiation detectors, and pulse lasers.

From the Rice repository, we have the following new papers:

Data Acquisition through joint Compressive Sensing and Principal Component Analysis by Riccardo Masiero, Giorgio Quer, Daniele Munaretto, Michele Rossi, Joerg Widmer, Michele Zorzi. The abstract reads:

In this paper we look at the problem of accurately reconstructing distributed signals through the collection of a small number of samples at a data gathering point. The techniques that we exploit to do so are Compressive Sensing (CS) and Principal Component Analysis (PCA). PCA is used to find transformations that sparsify the signal, which are required for CS to retrieve, with good approximation, the original signal from a small number of samples. Our approach dynamically adapts to non-stationary real world signals through the online estimation of their correlation properties in space and time; these are then exploited by PCA to derive the transformations for CS. The approach is tunable and robust, independent of the specific routing protocol in use and able to substantially outperform standard data collection schemes. The effectiveness of our recovery algorithm, in terms of number of transmissions in the network vs reconstruction error, is demonstrated for synthetic as well as for real world signals which we gathered from an actual wireless sensor network (WSN) deployment.We stress that our solution is not limited toWSNs but it can be readily applied to other types of network infrastructures
that require the online approximation of large and distributed data sets.

Map-Based Compressive Sensing Model for Wireless Sensor Network Architecture, A Starting Point by Mohammadreza Mahmudimanesh, Abdelmajid Khelil, Nasser Yazdani. The abstract reads:

Sub-Nyquist sampling techniques for Wireless Sensor Networks (WSN) are gaining increasing attention as an alternative method to capture natural events with desired quality while minimizing the number of active sensor nodes. Among those techniques, Compressive Sensing (CS) approaches are of special interest, because of their mathematically concrete foundations and efficient implementations. We describe how the geometrical representation of the sampling problem can influence the effectiveness and efficiency of CS algorithms. In this paper we introduce a Map-based model which exploits redundancy attributes of signals recorded from natural events to achieve an optimal representation of the signal.

Reordering for Better Compressibility: Efficient Spatial Sampling in Wireless Sensor Networks by Mohammadreza Mahmudimanesh, Abdelmajid Khelil and Neeraj Suri. The abstract reads:

Compressed Sensing (CS) is a novel sampling paradigm that tries to take data-compression concepts down to the sampling layer of a sensory system. It states that discrete compressible signals are recoverable from sub-sampled data, when the data vector is acquired by a special linear transform of the original discrete signal vector. Distributed sampling problems especially in Wireless Sensor Networks (WSN) are good candidates to apply CS and increase sensing efficiency without sacrificing accuracy. In this paper, we discuss how to reorder the samples of a discrete spatial signal vector by defining an alternative permutation of the sensor nodes (SN). Accordingly, we propose a method to enhance CS in WSN through improving signal compressibility by finding a sub-optimal permutation of the SNs. Permutation doesn't involve physical relocation of the SNs. It is a reordering function computed at the sink to gain a more compressible view of the spatial signal. We show that sub-optimal reordering stably maintains a more compressible view of the signal until the state of the environment changes so that another up-to-date reordering has to be computed. Our method can increase signal reconstruction accuracy at the same spatial sampling rate, or recover the state of the operational environment with the same quality at lower spatial sampling rate. Sub-sampling takes place during the interval that our reordered version of the spatial signal remains more compressible than the original signal.

SPARLS: The Sparse RLS Algorithm by Behtash Babadi, Nicholas Kalouptsidis, and, Vahid Tarokh. The abstract reads:

We develop a Recursive L1-Regularized Least Squares (SPARLS) algorithm for the estimation of a sparse tap-weight vector in the adaptive filtering setting. The SPARLS algorithm exploits noisy observations of the tap-weight vector output stream and produces its estimate using an Expectation- Maximization type algorithm. We prove the convergence of the SPARLS algorithm to a near-optimal estimate in a stationary environment and present analytical results for the steady state error. Simulation studies in the context of channel estimation, employing multi-path wireless channels, show that the SPARLS algorithm has significant improvement over the conventional widely-used Recursive Least Squares (RLS) algorithm in terms of mean squared error (MSE). Moreover, these simulation studies suggest that the SPARLS algorithm (with slight modifications) can operate with lower computational requirements than the RLS algorithm, when applied to tap-weight vectors with fixed support.

This paper was featured as a preprint 15 months ago!

Compressive sampling based interior tomography for dynamic carbon nanotube Micro-CT by Hengyong Yu, Guohua Cao, Laurel Burk, Yueh Lee, Jianping Lu, Pete Santago, Otto Zhou, Ge Wang. The abstract reads:

In the computed tomography (CT) field, one recent invention is the so-called carbon nanotube (CNT) based field emission x-ray technology. On the other hand, compressive sampling (CS) based interior tomography is a new innovation. Combining the strengths of these two novel subjects, we apply the interior tomography technique to local mouse cardiac imaging using respiration and cardiac gating with a CNT based micro-CT scanner. The major features of our method are: (1) it does not need exact prior knowledge inside an ROI; and (2) two orthogonal scout projections are employed to regularize the reconstruction. Both numerical simulations and in vivo mouse studies are performed to demonstrate the feasibility of our methodology.

Supplemental analysis on compressed sensing based interior tomography by Hengyong Yu, Jiansheng Yang, Ming Jiang and Ge Wang. The abstract reads:

Recently, in the compressed sensing framework we proved that an interior ROI can be exactly reconstructed via the total variation minimization if the ROI is piecewise constant. In the proofs, we implicitly utilized the property that if an artifact image assumes a constant value within the ROI, then this constant must be zero. Here we prove this property in the space of square integrable functions.

Also behind a paywall, there is:

High-resolution imaging of moving train by ground-based radar with compressive sensing by Xie Xiao-Chun and Zhang Yun-Hua. The abstract reads:

A compressive sensing (CS) based method for ISAR imaging with a stepped-frequency chirp signal (SFCS) is presented. It is outlined that by using the CS technique, the data rate has been remarkably reduced in bandwidth synthesis processing for SFCS to achieve a high range resolution. Imaging results of a moving train demonstrate the effectiveness of the proposed method.

Finally, Panos Tsakalides sent me the following post-doc announcement:

FOUNDATION FOR RESEARCH AND TECHNOLOGY - HELLAS (FORTH)
INSTITUTE OF COMPUTER SCIENCE
Postal address: N. Plastira 100, GR-700 13 Heraklion, Crete, Greece
Tel.: +30 2810 391730, Fax: +30 2810 391601, Email: ics@ics.forth.gr, URL: www.ics.forth.gr
Building a competitive
Greece
MINISTRY OF DEVELOPMENT, GENERAL SECRETARIAT FOR RESEARCH AND TECHNOLOGY
Project: CS-ORION: An FP7-PEOPLE-IAPP EU-funded project at FORTH-ICS
Position: Post-doctoral researcher
Start date: Fall (Sept-Nov) 2010
Duration: 24 months
Salary: 39.000-42.000 €/year (gross income depending on family status)
Description:
The Telecommunications and Networks Laboratory (TNL) of the Institute of Computer Science (ICS) at the Foundation for Research and Technology-Hellas (FORTH), is seeking recent PhD graduates for a post-doctoral position in the general field of Compressed Sensing-CS. The successful candidate will have the opportunity to work on one or more of the following topics:
CS for remote imaging in aerial and terrestrial surveillance, CS for video representation and coding, and compressed radar imaging.
The successful candidate will be offered the opportunity to:
* Have access to laboratory space and significant resources, and interact with researchers
from other FORTH-ICS labs.
* Work within a team with a strong international flavour including many researchers of non-Greek origin.
* Collaborate with academic and industrial partners in Greece, France, and the US.
* Work on a research subject which best fits his/her background and future goals, within the general areas described above.
Required skills:
* A PhD in computer science, electrical engineering, or related field.
* Background in image and/or video processing, especially in the area of sparse
approximation and compressive sensing and the ability to perform original research, as evidenced by a strong publication record.
* Excellent programming skills in Matlab and/or C/C++.
Eligibility:
* Recent PhD graduates (less than 10 years after obtaining their BS degree).
* Non-Greek nationals, who have not resided in Greece more than 12 months in the 3 years prior to the appointment.
* Greek nationals who have resided and held their primary activities outside the EU and its Associated Countries for at least 3 of the last 4 years.
* FORTH is an equal opportunity employer; female candidates are particularly encouraged to apply.
About FORTH-ICS:
FORTH is the premier research institution in Greece, housed in a new state-ofthe-
art building in the middle of olive groves, located in Heraklion, Crete, Greece. FORTH has a long successful history of attracting international scholars to Crete, as evidenced by the significant size of its research community with a non-Greek origin. FORTH-ICS has established itself as an internationally known and highly competitive research institute, with a modern infrastructure and a broad range of research & development (R&D) and educational activities.
To apply, please send a cover letter and a CV to Prof. Tsakalides.
Contact: P. Tsakalides, e-mail: tsakalid@ics.forth.gr, http:// www.ics.forth.gr/~tsakalid

Credit: Gizmodo, DOE, NPR piece on Starfish-Prime