CS: RIPless theory of compressed sensing, Secrecy, PADDLE, Sparse PCA, non-asymptotic analysis of random matrices. Multiview CS, a postodc and a PhD studentship and more.

So it looks like there was too much burden brandishing the RIP argument :-) Here is a new paper on the subject: A probabilistic and RIPless theory of compressed sensing by Emmanuel J. Candes, Yaniv Plan. The abstract reads:

This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all models - e.g. Gaussian, frequency measurements - discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) - they make use of a much weaker notion - or a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s log n Fourier coefficients that are contaminated with noise.

One may note the reliance on a previous paper by David Gross in quantum state tomography, today we have another quantum paper (a significant revision actually):

Efficient measurement of quantum dynamics via compressive sensing by Alireza Shabani, Robert Kosut, Masoud Mohseni, Herschel Rabitz, M. A. Broome, M. P. Almeida, A. Fedrizzi, Andrew White. The abstract reads:

The resources required to characterise the dynamics of engineered quantum systems-such as quantum computers and quantum sensors-grow exponentially with system size. Here we adapt techniques from compressive sensing to exponentially reduce the experimental configurations required for quantum process tomography. Our method is applicable to dynamical processes that are known to be nearly-sparse in a certain basis and it can be implemented using only single-body preparations and measurements. We perform efficient, high-fidelity estimation of process matrices on an experiment attempting to implement a photonic two-qubit logic-gate. The data base is obtained under various decoherence strengths. We find that our technique is both accurate and noise robust, thus removing a key roadblock to the development and scaling of quantum technologies.

We have also several other papers from arxiv:

Perfect Secrecy Using Compressed Sensing by Mahmoud Ramezani Mayiami, Babak Seyfe, Hamid G. Bafghi. The abstract reads:

Abstract: In this paper we consider the compressed sensing-based encryption and proposed the conditions in which the perfect secrecy is obtained. We prove when the Restricted Isometery Property (RIP) is hold and the number of measurements is more than two times of sparsity level i.e. M \geq 2k, the perfect secrecy condition introduced by Shannon is achievable if message block is not equal to zero or we have infinite block length

PADDLE: Proximal Algorithm for Dual Dictionaries LEarning by Curzio Basso, Matteo Santoro, Alessandro Verri, Silvia Villa. The abstract reads:

Recently, considerable research efforts have been devoted to the design of methods to learn from data overcomplete dictionaries for sparse coding. However, learned dictionaries require the solution of an optimization problem for coding new data. In order to overcome this drawback, we propose an algorithm aimed at learning both a dictionary and its dual: a linear mapping directly performing the coding. By leveraging on proximal methods, our algorithm jointly minimizes the reconstruction error of the dictionary and the coding error of its dual; the sparsity of the representation is induced by an $\ell_1$-based penalty on its coefficients. The results obtained on synthetic data and real images show that the algorithm is capable of recovering the expected dictionaries. Furthermore, on a benchmark dataset, we show that the image features obtained from the dual matrix yield state-of-the-art classification performance while being much less computational intensive.

PADDLE is available from this page:

PADDLE is a Python package for learning dictionaries with frame-like properties, as well as achieving sparse coding of the training data. In particular, it provides algorithms for

• learning a dictionary together with a dual of itself, and
• learning a dictionary close to a tigth-frame.

of note another Python package called L1L2Py.

L1L2Py is a Python package to perform feature selection by means of regularization with double optimization.

Introduction to the non-asymptotic analysis of random matrices by Roman Vershynin. The abstract reads:

This is a tutorial on some basic non-asymptotic methods and concepts in random matrix theory. The reader will learn several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis in the 1970-2000's. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. A few basic applications are covered in this text, particularly for the problem of estimating covariance matrices in statistics and for validating probabilistic constructions of measurement matrices in compressed sensing. These notes are written particularly for graduate students and beginning researchers in different areas, including functional analysts, probabilists, theoretical statisticians, electrical engineers, and theoretical computer scientists

Sparse PCA: Convex Relaxations, Algorithms and Applications by Youwei Zhang, Alexandre d'Aspremont, Laurent El Ghaoui. The abstract reads:

Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This is known as sparse principal component analysis and has a wide array of applications in machine learning and engineering. Unfortunately, this problem is also combinatorially hard and we discuss convex relaxation techniques that efficiently produce good approximate solutions. We then describe several algorithms solving these relaxations as well as greedy algorithms that iteratively improve the solution quality. Finally, we illustrate sparse PCA in several applications, ranging from senate voting and finance to news data.

There is studentship sponsored by Philips Inc. The announcement is on the compressive sensing jobs page.

Thomas Strohmer sent me the following Postdoc opportunity (also on the ompressive sensing jobs page. )

POST-DOCTORAL POSITION IN MATHEMATICS, University of California, Davis

The Department of Mathematics at the University of California, Davis, is soliciting applications for a Postdoctoral Scholar position with a starting date between March 2011 and October 2011.
To be considered for the Postdoctoral Scholar position, the Department seeks applicants with a strong knowledge base in Sparse Approximations, Compressive Sensing and/or Optimization. Applicants are required to have completed their Ph.D. by August 31, 2011 (or before the starting date, if the starting date is earlier). The position requires working on research related to two defense-based projects (DTRA/NSF and DARPA), lead by Professor Thomas Strohmer. The research is concerned with developing theory and algorithms for sparse recovery in connection with threat detection and radar. The candidate should also have excellent programming
skills in Matlab. The annual salary of this position is $60,000, plus some travel funds. The position carries no teaching duties, but teaching may be possible upon request. The appointment is renewable for a total of up to three years, assuming satisfactory performance.

The UC Davis Math and Applied Math programs have been ranked among the nation’s top programs by the National Research Council in its most recent report. Additional information about the Department may be found at http://www.math.ucdavis.edu/. Our postal address is Department of Mathematics, University of California, One Shields Avenue, Davis, CA 95616-8633.
Applications will be accepted until the positions are filled. To guarantee full consideration, the application should be received by December 15, 2010 by submitting the AMS Cover Sheet and supporting documentation (CV, publication list, letters of reference, brief research statement) electronically through http://www.mathjobs.org/. The University of California is an affirmative action/equal opportunity employer.

David Brady is the  co-founder and a chief scientist of  Centice. He's done some of the early implementation of compressive sensing hardware and even wrote a book about how CS  gets into optics (.Optical Imaging and Spectroscopy).Prasant Potuluri, the CTO of  Centice also did compressive sensing in his thesis on Multiplexed Optical Sensors for Reference Structure Tomography and Compressive Spectroscopy. Well, whyy do I write this ? Because Centice just raised funding ((Innovation Ventures-Backed Centice Verifies Most of $1.3M Equity Offering ) which really underscores the fact that you can do compressive sensing and be a successful entrepreneur :-). Congratulations David.and Prasant !

Finally, we have some papers on multi-view sensors using compressive sensing:

A Multi-Sensor Compressed Sensing Receiver: Performance Bounds and Simulated Results by Benjamin Miller, Joel Goodman, and Keith Forsythe, John Z. Sun and Vivek K Goyal. The abstract reads:

Multi-sensor receivers are commonly tasked with detecting, demodulating and geolocating target emitters over very wide frequency bands. Compressed sensing can be applied to persistently monitor a wide bandwidth, given that the received signal can be represented using a small number of coefficients in some basis. In this paper we present a multi-sensor compressive sensing receiver that is capable of reconstructing frequency-sparse signals using block reconstruction techniques in a sensor-frequency basis. We derive performance bounds for time-difference and angle of arrival (AoA) estimation of such a receiver, and present simulated results in which we compare AoA reconstruction performance to the bounds derived

and the other one behind a paywall:

Compressed sensing joint reconstruction for multi-view images by X. Li, Z. Wei, and L. Xiao. The abstract reads:

The problem of compressed sensing joint reconstruction of multi-view images in camera networks is considered. Noting that the neighbouring images are visually similar, the multi-view correlation is captured by the sparse prior of the difference images between two contiguous multi-view images. Thus the joint reconstruction is formulated as an unconstrained optimisation problem, which contains a quadratic fidelity term and two regularisation terms encouraging the sparse priors for multi-view images and their difference images, respectively. Moreover, an effective iterative algorithm is presented to solve the optimisation problem. Experimental results with the real multi-view images show that the proposed method can perform joint reconstruction with greater accuracy than CS image-by-image reconstruction.

Credits: Montage by Emily Lakdawalla. Ida, Dactyl, Braille, Annefrank, Gaspra, Borrelly: NASA / JPL / Ted Stryk. Steins: ESA / OSIRIS team. Eros: NASA / JHUAPL. Itokawa: ISAS / JAXA / Emily Lakdawalla. Mathilde: NASA / JHUAPL / Ted Stryk. Lutetia: ESA / OSIRIS team / Emily Lakdawalla. Halley: Russian Academy of Sciences / Ted Stryk. Tempel 1, Hartley 2: NASA / JPL / UMD. Wild 2: NASA / JPL. All asteroids and comets visited by spacecraft as of November 2010