CS: Sparse approx, Body Area Networks, Johnson-Lindenstrauss Transform, Superselectors, stochastic search method for dimensionality reduction in classification, Adaptive estimation of covariance matrices via Cholesky decomposition

Today, we have some blog entries, three papers and two articles in the blogosphere/press related to compressive sensing, without further due, here they are:

From the blogs:
Bob

• Greedy Decomposition of Stationary Signals
• Un Homme et Une Femme: Audio Fingerprinting and Matching in MATLAB
• Paper of the Day (Po'D): Recursive Nearest Neighbor Search in a Sparse Domain Applied to Comparing Audio Signals Edition
• Comparing Audio Signals in a Sparse Domain
• A Successful HAID 2010!

Gonzalo:

• Spectral Sensing at CIP 2010
• Final FCC rules for the unlicensed use of the TV white spaces today?
• FCC "final" rules. Cognitive radio or just unlicensed access?
• ECC Report 159: European white space devices

In the press:

• Michael Elad Talks About the field of Sparse Approximation (Michael Elad has also written a book on Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing)
• Qualcomm's ultralow power tech targets body area networks

From Suresh:

The Johnson-Lindenstrauss Transform: An Empirical Study (pdf is here) by Suresh Venkatasubramanian and Qiushi Wang. The abstract reads:

The Johnson-Lindenstrauss Lemma states that a set of $n$ points may be embedded in a space of dimension $O(\log n/\eps^2)$ while preserving all pairwise distances within a factor of $(1+\epsilon)$ with high probability. It has inspired a number of proofs that extend the result, simplify it, and improve the efficiency of computing the resulting embedding. The lemma is a critical tool in the realm of dimensionality reduction and high dimensional approximate computational geometry. It is also employed for data mining in domains that analyze intrinsically high dimensional objects such as images and text. However, while algorithms for performing the dimensionality reduction have become increasingly sophisticated, there is little understanding of the behavior of these embeddings in practice. In this paper, we present the first comprehensive study of the empirical behavior of algorithms for dimensionality reduction based on the JL Lemma.

Our study answers a number of important questions about the quality of the embeddings and the performance of algorithms used to compute them. Among our key results:

• Determining a likely range for the big-Oh constant in practice for the dimension of the target space, and demonstrating the accuracy of the predicted bounds.
• Finding `best in class’ algorithms over wide ranges of data size and source dimensionality, and showing that these depend heavily on parameters of the data as well its sparsity.
• Developing the best implementation for each method, making use of non-standard optimized codes for key subroutines.
• Identifying critical computational bottlenecks that can spur further theoretical study of efficient algorithms.

From arxiv:

Superselectors: Efficient Constructions and Applications by Ferdinando Cicalese, Ugo Vaccaro. The abstract reads:

We introduce a new combinatorial structure: the superselector. We show that superselectors subsume several important combinatorial structures used in the past few years to solve problems in group testing, compressed sensing, multi-channel conflict resolution and data security. We prove close upper and lower bounds on the size of superselectors and we provide efficient algorithms for their constructions. Albeit our bounds are very general, when they are instantiated on the combinatorial structures that are particular cases of superselectors (e.g., (p,k,n)-selectors, (d,\ell)-list-disjunct matrices, MUT_k(r)-families, FUT(k, a)-families, etc.) they match the best known bounds in terms of size of the structures (the relevant parameter in the applications). For appropriate values of parameters, our results also provide the first efficient deterministic algorithms for the construction of such structures.

A multivariate adaptive stochastic search method for dimensionality reduction in classification by Tian Siva Tian, Gareth M. James, Rand R. Wilcox. The abstract reads:

High-dimensional classification has become an increasingly important problem. In this paper we propose a "Multivariate Adaptive Stochastic Search" (MASS) approach which first reduces the dimension of the data space and then applies a standard classification method to the reduced space. One key advantage of MASS is that it automatically adjusts to mimic variable selection type methods, such as the Lasso, variable combination methods, such as PCA, or methods that combine these two approaches. The adaptivity of MASS allows it to perform well in situations where pure variable selection or variable combination methods fail. Another major advantage of our approach is that MASS can accurately project the data into very low-dimensional non-linear, as well as linear, spaces. MASS uses a stochastic search algorithm to select a handful of optimal projection directions from a large number of random directions in each iteration. We provide some theoretical justification for MASS and demonstrate its strengths on an extensive range of simulation studies and real world data sets by comparing it to many classical and modern classification methods.

Adaptive estimation of covariance matrices via Cholesky decomposition by Nicolas Verzelen. The abstract reads:

This paper studies the estimation of a large covariance matrix. We introduce a novel procedure called ChoSelect based on the Cholesky factor of the inverse covariance. This method uses a dimension reduction strategy by selecting the pattern of zero of the Cholesky factor. Alternatively, ChoSelect can be interpreted as a graph estimation procedure for directed Gaussian graphical models. Our approach is particularly relevant when the variables under study have a natural ordering (e.g. time series) or more generally when the Cholesky factor is approximately sparse. ChoSelect achieves non-asymptotic oracle inequalities with respect to the Kullback-Leibler entropy. Moreover, it satisfies various adaptive properties from a minimax point of view. We also introduce and study a two-stage procedure that combines ChoSelect with the Lasso. This last method enables the practitioner to choose his own trade-off between statistical efficiency and computational complexity. Moreover, it is consistent under weaker assumptions than the Lasso. The practical performances of the different procedures are assessed on numerical examples.

Image Credit: NASA/JPL/Space Science Institute, N00164032.jpg was taken on October 06, 2010 and received on Earth October 07, 2010. The camera was pointing toward ATLAS, and the image was taken using the CL1 and CL2 filters.

Partha Niyogi has left us

(Via Suresh)

Partha Niyogi is no longer with us. Here is a video of him back a year ago on a talk about Geometric Methods and Manifold Learning. Godspeed Partha.

CS: Clouds, Concentration of Measure for Block Diagonal Matrices, Deterministic Compressed Sensing Matrices, some meetings

To answer yesterday's question: Clouds, the probability of flying 100,000 feet up in the air and seeing only clouds is pretty high.  This is the reason why

• the Russians built space stations during the Cold war,
• we started the GeoCam project,
• we could not locate a boat off the California coast.... 
• it is a rare occurence when you can shoot Greenland from 30,000 fee as this image shows.

I ain't talking about doing NIR nor SWIR to see through clouds, but rather what if clouds could be used as lenses ?

Oh well, today we have  several papers and some announcements about meetings: First, I had thought I had seen that paper back in March but Michael Wakin tells me in what way the following paper is different from the previous installement:

This paper significantly expands upon our previous ICASSP and CISS publications. Section 3 contains a more general analysis for Distinct Block Diagonal (DBD) matrices and explains a connection between our concentration bounds for DBD matrices and Repeated Block Diagonal (RBD) matrices. Sections 4 and 5 of this paper contain almost all new material, including a list of signal families that have favorable properties for measurement via block diagonal matrices, and a discussion of connections with the compressive channel sensing problem.

Thanks Mike ! here is the paper: Concentration of Measure for Block Diagonal Matrices with Applications to Compressive Sensing by Jae Young Park, Han Lun Yap, Christopher J. Rozell, and Michael Wakin. The abstract reads:

Theoretical analysis of randomized, compressive operators often depends on a concentration of measure inequality for the operator in question. Typically, such inequalities quantify the likelihood that a random matrix will preserve the norm of a signal after multiplication. When this likelihood is very high for any signal, the random matrices have a variety of known uses in dimensionality
reduction and Compressive Sensing. Concentration of measure results are well-established for unstructured compressive matrices, populated with independent and identically distributed (i.i.d.) random entries. Many real-world acquisition systems, however, are subject to architectural constraints that make such matrices impractical. In this paper we derive concentration of measure bounds for two types of block diagonal compressive matrices, one in which the blocks along the main diagonal are random and independent, and one in which the blocks are random but equal. For both types of matrices, we show that the likelihood of norm preservation depends on certain properties of the signal being measured, but that for the best case signals, both types of block diagonal matrices can offer concentration performance on par with their unstructured, i.i.d. counterparts. We support our theoretical results with illustrative simulations as well as (analytical and empirical) investigations of several signal classes that are highly amenable to measurement using block diagonal matrices. Finally, we discuss applications of these results in establishing performance guarantees for solving signal processing tasks in the compressed domain (e.g., signal detection), and in establishing the Restricted Isometry Property for the Toeplitz matrices that arise in compressive channel sensing.

Deterministic Compressed Sensing Matrices from Additive Character Sequences by Nam Yul Yu. The abstract reads:

Compressed sensing is a novel technique where one can recover sparse signals from the undersampled measurements. In this correspondence, a $K \times N$ measurement matrix for compressed sensing is deterministically constructed via additive character sequences. The Weil bound is then used to show that the matrix has asymptotically optimal coherence for $N=K^2$, and to present a sufficient condition on the sparsity level for unique sparse recovery. Also, the restricted isometry property (RIP) is statistically studied for the deterministic matrix. Using additive character sequences with small alphabets, the compressed sensing matrix can be efficiently implemented by linear feedback shift registers. Numerical results show that the deterministic compressed sensing matrix guarantees reliable matching pursuit recovery performance for both noiseless and noisy measurements.

Kalman Filtering for Compressed Sensing by Dimitri Kanevsky, Avishy Carmi, Lior Horesh, Pini Gurfil, Bhuvana Ramabhadran, Tara N Sainath. The abstract reads:

Compressed sensing is a new emerging field dealing with the reconstruction of a sparse or, more precisely, a compressed representation of a signal from a relatively small number of observations, typically less than the signal dimension. In our previous work we have shown how the Kalman filter can be naturally applied for obtaining an approximate Bayesian solution for the compressed sensing problem. The resulting algorithm, which was termed CSKF, relies on a pseudo-measurement technique for enforcing the sparseness constraint. Our approach raises two concerns which are addressed in this paper. The first one refers to the validity of our approximation technique. In this regard, we provide a rigorous treatment of the CSKF algorithm which is concluded with an upper bound on the discrepancy between the exact (in the Bayesian sense) and the approximate solutions. The second concern refers to the computational overhead associated with the CSKF in large scale settings. This problem is alleviated here using an efficient measurement update scheme based on Krylov subspace method.

Derandomization and Group Testing by Mahdi Cheraghchi. The abstract reads:

The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of "positive" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using "randomness-conducting" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.

Interference Alignment as a Rank Constrained Rank Minimization by Dimitris S. Papailiopoulos, Alexandros G. Dimakis. The abstract reads:

We show that the maximization of the sum degrees-of-freedom for the static flat-fading multiple-input multiple-output (MIMO) interference channel is equivalent to a rank constrained rank minimization problem, when the signal spaces span all available dimensions. The rank minimization corresponds to maximizing interference alignment (IA) such that interference spans the lowest dimensional subspace possible. The rank constraints account for the useful signal spaces spanning all available spatial dimensions. That way, we reformulate all IA requirements to requirements involving ranks. Then, we present a convex relaxation of the RCRM problem inspired by recent results in compressed sensing and low-rank matrix completion theory that rely on approximating rank with the nuclear norm. We show that the convex envelope of the sum of ranks of the interference matrices is the sum of their corresponding nuclear norms and introduce tractable constraints that are asymptotically equivalent to the rank constraints for the initial problem. We also show that our heuristic relaxation can be also tuned to the multi-cell interference channel. Furthermore, we experimentally show that the proposed algorithm outperforms previous approaches for finding precoding and zero-forcing matrices for interference alignment.

Regularizers for Structured Sparsity by: Charles A. Micchelli, Jean M. Morales, Massimiliano Pontil. The abstract reads:

We study the problem of learning a sparse linear regression vector under additional conditions on the structure of its sparsity pattern. This problem is relevant in machine learning, statistics and signal processing. It is well known that a linear regression can benefit from the knowledge that the underlying regression vector is sparse. The combinatorial problem of selecting the nonzero components of this vector can be ``relaxed'' by regularizing the squared error with a convex penalty function like the $\ell_1$ norm. However, in many applications, additional conditions on the structure of the regression vector and its sparsity pattern are available. By incorporating this information into the learning method, may lead to a significant decrease of the estimation error. In this paper, we present a family of convex penalty functions, which encode prior knowledge on the structure of the vector formed by the absolute values of the regression coefficients. This family subsumes the $\ell_1$ norm and is flexible enough to include different models of sparsity patterns, which are of practical and theoretical importance. We establish the basic properties of these penalty functions and discuss some examples where they can be computed explicitly. Moreover, we present a convergent optimization algorithm for solving regularized least squares with these penalty functions. Numerical simulations highlight the benefit of structured sparsity and the advantage offered by our approach over the Lasso method and other related methods.

Real-time Robust Principal Components' Pursuit by Chenlu Qiu, Namrata Vaswani. The abstract reads:

In the recent work of Candes et al, the problem of recovering low rank matrix corrupted by i.i.d. sparse outliers is studied and a very elegant solution, principal component pursuit, is proposed. It is motivated as a tool for video surveillance applications with the background image sequence forming the low rank part and the moving objects/persons/abnormalities forming the sparse part. Each image frame is treated as a column vector of the data matrix made up of a low rank matrix and a sparse corruption matrix. Principal component pursuit solves the problem under the assumptions that the singular vectors of the low rank matrix are spread out and the sparsity pattern of the sparse matrix is uniformly random. However, in practice, usually the sparsity pattern and the signal values of the sparse part (moving persons/objects) change in a correlated fashion over time, for e.g., the object moves slowly and/or with roughly constant velocity. This will often result in a low rank sparse matrix.

For video surveillance applications, it would be much more useful to have a real-time solution. In this work, we study the online version of the above problem and propose a solution that automatically handles correlated sparse outliers. The key idea of this work is as follows. Given an initial estimate of the principal directions of the low rank part, we causally keep estimating the sparse part at each time by solving a noisy compressive sensing type problem. The principal directions of the low rank part are updated every-so-often. In between two update times, if new Principal Components' directions appear, the "noise" seen by the Compressive Sensing step may increase. This problem is solved, in part, by utilizing the time correlation model of the low rank part. We call the proposed solution "Real-time Robust Principal Components' Pursuit".

Universal Regularizers For Robust Sparse Coding and Modeling by Ignacio Ramırez and Guillermo Sapiro.. The abstract reads:

Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. It is now well understood that the choice of the sparsity regularization term is critical in the success of such models. Based on a codelength minimization interpretation of sparse coding, and using tools from universal coding theory, we propose a framework for designing sparsity regularization terms which have theoretical and practical advantages when compared to the more standard `0 or `1 ones. The presentation of the framework and theoretical foundations is complemented with examples that show its practical advantages in image denoising, zooming and classification.

Structured Sparse Principal Component Analysis by Rodolphe Jenatton, Guillaume Obozinski, Francis Bach. Theabstract

We present an extension of sparse PCA, or sparse dictionary learning, where the sparsity patterns of all dictionary elements are structured and constrained to belong to a prespecified set of shapes. This structured sparse PCA is based on a structured regularization recently introduced by Jenatton et al. (2009). While classical sparse priors only deal with cardinality, the regularization we use encodes higher-order information about the data. We propose an efficient and simple optimization procedure to solve this problem. Experiments  with two practical tasks, the denoising of sparse structured signals and face recognition, demonstrate the benefits of the proposed structured approach over unstructured approaches.

Network Flow Algorithms for Structured Sparsity by Julien Mairal Rodolphe Jenatton, Guillaume Obozinski, Francis Bach.. The abstract reads:

We consider a class of learning problems that involve a structured sparsity-inducing norm defined as the sum of $\ell_\infty$-norms over groups of variables. Whereas a lot of effort has been put in developing fast optimization methods when the groups are disjoint or embedded in a specific hierarchical structure, we address here the case of general overlapping groups. To this end, we show that the corresponding optimization problem is related to network flow optimization. More precisely, the proximal problem associated with the norm we consider is dual to a quadratic min-cost flow problem. We propose an efficient procedure which computes its solution exactly in polynomial time. Our algorithm scales up to millions of variables, and opens up a whole new range of applications for structured sparse models. We present several experiments on image and video data, demonstrating the applicability and scalability of our approach for various problems.

While waiting for the videos of the LVA meeting, I found the following list of meetings related to sparsity here.
And here is another one:

Spring-Summer School
June 20-21-22, 2011
Random matrices - Stochastic geometry - Compressed sensing


Speakers

* Jared Tanner (U. Edinburgh, UK)
Stochastic Geometry and Random Matrix Theory in Compressed Sensing
Stochastic geometry and random matrix theory can be used to model and analyse the efficacy of a new paradigm in signal processing, compressed sensing. This new perspective shows that if a signal is sufficiently simple, it can be acquired at a rate proportional to its information content rather than the worst case rate dictated by a larger ambient space containing it. These lectures will show how this phenomenon can be modelled using stochastic geometry, and will also show how standard eigen-analysis in random matrix theory can give similar results.
* Roman Vershynin (U. Michigan, USA)
Introduction to the non-asymptotic analysis of random matrices
This is a mini-course on basic non-asymptotic methods and concepts in random matrix theory. We will develop 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. Two applications will be discussed: for the problem of estimating covariance matrices in statistics, and for validating probabilistic constructions of measurement matrices in compressed sensing.

Location and period

Institut Henri Poincaré, Paris, from June 20 to June 22, 2011. Room 201 9:00am-05:30pm.

Audience

This school is addressed to non-specialists: participation of postdocs and PhD students is strongly encouraged.

Registration

The number of participants is limited to 30.

* Registration form
* List of participants

Organizers

D. Chafaï & A. Pajor (U. Paris-Est Marne-la-Vallée), A. Tsybakov (U. Pierre et Marie Curie Paris VI & CREST)

It's not deja vu ...

Sometimes, you see something and make a mental note of it. Then months later, you see something similar and recall that first impression of a while back, but it is still a surprise to you. In actuality every single time you notice, you somehow forget about it, either because it was not important or there is something deeper but you can't take action on it. I was watching this video this week-end and remembered something that I had forgotten, can you guess what it is ?

Homemade Spacecraft from Luke Geissbuhler on Vimeo.

CS; CTBT's feats, TwIST, Recovery of Frequency-Sparse Signals from Compressive Measurements, Recovering Spikes from Noisy Neuronal Calcium Signals, Compressive SD-OCT, a postdoc.

I mentioned the CTBT's capabilities before (CS: Is HIFT an instance of Imaging With Nature ? The data is available.). This week-end, I came across some of Lassino Zerbo's presentations on CTBT's engineering feats. Here are some interesting slides:

Or from one of her two presentations that has been spidered on Google:

Wow. I am sure I'll come back to it later.


Version 2 of the TwIST code (Two-step Iterative Shrinkage/Thresholding Algorithm for Linear Inverse Problems) is now available from the code's webpage.

Peng Zhang has a presentation on Compressed Sensing Approaches to Spectrum Sensing in Cognitive Radio Networks.

On November 1, Emmanuel Abbe (EPFL) will be making a presention at Yale a talk entitled:  A polarization approach to compressed sensing. The abstract of the presentation reads:

In 2008, a technique called channel polarization allowed to solve a problem open since 1948 by Shannon: the construction of low complexity codes that are provably capacity achieving. The polarization idea can be explained on the basis of a rather general probabilistic phenomenon: let X_1,...,X_n be i.i.d. Bernoulli(p) and transform (X_1,...,X_n) with the GF(2)-matrix that takes log(n) Kronecker products of [1 0; 1 1], then the output contains nH(p) entries which are roughly independent and uniformly distributed and n(1-H(p)) entries which are roughly deterministic given the past entries (H being the entropy function). Hence the Kronecker matrix `distills' the randomness of the original vector, and it does so at low computational cost, O(n log n). In this talk, we will use the idea behind polarization not for channel coding, but to propose a new approach to compressed sensing. With this approach, the sensing matrix has the attribute of being deterministic, whereas the signal is assumed to be statistically sparse. The reconstruction algorithm is shown to have a low complexity, and the overall scheme is based on algebraic arguments rather than convex optimization.

With reagrds to papers/preprints, here is what we have this week so far:
Recovery of Frequency-Sparse Signals from Compressive Measurements, (Slides) by Marco. Duarte and Richard Baraniuk. The abstract reads;

Compressive sensing (CS) is a new approach to simultaneous sensing and compression for sparse and compressible signals. While the discrete Fourier transform has been widely used for CS of frequency-sparse signals, it provides optimal sparse representations only for signals with components at integral frequencies. There exist redundant frames that provide compressible representations for frequency-sparse signals, but such frames are highly coherent and severely affect the performance of standard CS recovery. In this paper, we show that by modifying standard CS recovery algorithms to prevent coherent frame elements from being present in the signal estimate, it is possible to bypass the shortcomings introduced by the coherent frame. The resulting algorithm comes with theoretical guarantees and is shown to perform significantly better for frequencysparse signal recovery than its standard counterparts. The algorithm can also be extended to similar settings that use coherent frames.

Recovering Spikes from Noisy Neuronal Calcium Signals via Structured Sparse Approximation by  Eva Dyer, Marco. Duarte , Don. Johnson and Richard Baraniuk, The abstract reads:

Two-photon calcium imaging is an emerging experimental technique that enables the study of information processing within neural circuits in vivo. While the spatial resolution of this technique permits the calcium activity of individual cells within the field of view to be monitored, inferring the precise times at which a neuron emits a spike is challenging because spikes are hidden within noisy observations of the neuron’s calcium activity. To tackle this problem, we introduce the use of sparse approximation methods for recovering spikes from the time-varying calcium activity of neurons. We derive sufficient conditions for exact recovery of spikes with respect to (i) the decay rate of the spike-evoked calcium event and (ii) the maximum firing rate of the cell under test.We find—both in theory and in practice—that standard sparse recovery methods are not sufficient to recover spikes from noisy calcium signals when the firing rate of the cell is high, suggesting that in order to guarantee exact recovery of spike times, additional constraints must be incorporated into the recovery procedure. Hence, we introduce an iterative framework for structured sparse approximation that is capable of achieving superior performance over standard sparse recovery methods by taking into account knowledge that spikes are non-negative and also separated in time. We demonstrate the utility of our approach on simulated calcium signals in various amounts of additive Gaussian noise and under different degrees of model mismatch.

Behind a paywall: Compressive SD-OCT: the application of compressed sensing in spectral domain optical coherence tomography by Xuan Liu and Jin U. Kang. The abstract reads:

We applied compressed sensing (CS) to spectral domain optical coherence tomography (SD OCT) and studied its effectiveness. We tested the CS reconstruction by randomly undersampling the k-space SD OCT signal. We achieved this by applying pseudo-random masks to sample 62.5%, 50%, and 37.5% of the CCD camera pixels. OCT images are reconstructed by solving an optimization problem that minimizes the l1 norm of a transformed image to enforce sparsity, subject to data consistency constraints. CS could allow an array detector with fewer pixels to reconstruct high resolution OCT images while reducing the total amount of data required to process the images.

In other news, Laurent Jacques sent me the following postdoc announcement at UCL in Belgium (also posted on the compressive sensing jobs page)

October 1, 2010. Postdoc position,:"Optical Inverse Problem Solving in 3-D Deflectometry” (starting date: January 1st, 2011, application deadline: November 12th, 2010. )      

• 
  
       Advisors:
• Dr Laurent Jacques (ICTEAM-TELE, UCL)
• Prof. Philippe Antoine (IMCN, UCL)
• Prof. Benoît Macq (ICTEAM-TELE, UCL)

Optical Framework:

Improved functional performance is a general trend in ocular surgery today. As an example, multifocal intraocular lens (IOL) achieves different optical powers, as such to enable good near and distant vision. There are two types of multifocal lenses. A refractive multifocal lens is made of concentric rings whose refractive powers alternate from centre to periphery. Diffractive multifocal lens uses light diffraction at an interference grid made of micrometric steps. Such complex surfaces are a real challenge both for manufacturing and for characterization.

This position opening takes place in a 3-year regional project (DETROIT), funded by the Belgian Walloon Region. This project aims at characterizing surfaces by optical deflectometry. The principle is to measure the deviation of the light reflected by each point of the surface. This technique is an interesting alternative to interferometry in order to estimate the surface topography. Indeed measuring the deviation angle instead of the height has several advantages. It is insensitive to vibrations as it is not based on interferences. It is more effective in detecting local details and object contours than height measurement. In deflectometry, the shape of an object is numerically reconstructed from the gradient data with a high accuracy. As an example, 10nm flatness deviation over a 50mm window glass can be observed with high accuracy instrument.

Experimentally, the very short radius of curvature of the IOLs requires the use of wide acceptance optics as such to collect light that is reflected in a large range of angles. The drawback is the very narrow field of view. In order to reduce the acquisition time, a device that images the whole lens shall be preferred but inevitable distortion of the image will be numerically corrected based on the knowledge of instrument response. This solution is challenging but very attractive for industrial perspectives.

Numerical Methods:

Nowadays, assuming that a signal (e.g., a 1-D signal, an image or a volume of data) has a sparse representation, namely that this signal is linearly described with few elements taken in a suitable basis, is an ubiquitous hypothesis validated in many different scientific domains. Interestingly, this sparsity assumption is the heart of methods solving inverse problems, namely those estimating a signal from some linear distorting observations. Sparsity stabilizes (or regularizes) these signal estimation techniques often based on L1-norm (or Total Variation norm) minimization and greedy methods.

This postdoc position concerns the application of the sparsity principle for modeling and solving the optical inverse problem described in the previous section, that is, the reconstruction of the undistorted image of the IOL from the experimental measurements.

Job description:

The postdoc will be in charge of the numerical reconstruction development of the undistorted IOL image from the experimental measurements, taking into account (and modeling) the particularities of the sensing systems. Calibration of the response of the instrument will be carried out by another partner of the project. However, a close collaboration between the two teams is necessary. Moreover, the postdoc will co-supervise a PhD student working on the same topic and funded by the same project.

The optical development takes place in the 3-year project DETROIT. It involves two industrial partners, Physiol and Lambda-X and 3 university partners. Physiol is well-known for its development of IOL. Lambda-X has a large experience in optical characterization of optical components by means of deflectometry. The leading academic partner is the Atomic, Molecular and Optical Physics Laboratory (IMCN-PAMO) of University of Louvain (UCL, Louvain-la-Neuve, Belgium), helped by two other Belgian university partners: the Active Structures Laboratory of the University of Brussels (ASL, ULB), in charge of the development of fast adaptive optics, and the Communications and Remote Sensing laboratory (ICTEAM-TELE, UCL) which is responsible of the IOL image reconstruction and post-processing algorithms.

Research activity will be carried out in the ICTEAM-TELE Laboratory, and partly at IMCN-PAMO and at Lambda-X offices in Nivelles, Belgium.

Candidate's Profile:

PhD in Physics, Electrical Engineering, Computer Science or Applied Mathematics; Good knowledge of signal/image processing and classical optics are mandatory; Knowledge (even partial) in the following topics constitutes assets: Multispectral Imaging, Coded Aperture, Spatial Light Modulator, Convex Optimization methods, Sparsity Models, Image DeNoising and Debluring, Compressed Sensing. Programming experience with Matlab, C and/or C++. Good communications skills, both written and oral; Speaking fluently in English or French is required. Writing in English is mandatory.

We offer:

• A research position in a dynamic and advanced high-tech environment, working on leading-edge technologies in collaboration with industrial partners.
• 1-year contract (starting date: 1/1/2011)
• gross salary range: 35 000 - 45 000 Euros

Application:

Applications should include a full CV, including list of publications, and must be sent before November 12th, 2010.

Names and complete addresses of referees are welcome.

Please send applications by email to (and replace _DOT_ and _AT_):

laurent _DOT_ jacques _AT_ uclouvain _DOT_ be
        ph _DOT_ antoine _AT_ uclouvain _DOT_ be 

Questions about the subject or the position should be addressed to the same email address.

Nuits Blanches on Nuit Blanche

If you are looking for a Nuit Blanche in Toronto, please go here. If you are looking for a Nuit Blanche in Paris, please go here. There is nothing to see here, except maybe watching this 14 year old prescient clip from Good Will Hunting:

or commenting on another Surprise in the Donoho-Tanner Phase Transition ? or reading items from The other long entry of the week. That should do it.

Another Surprise in the Donoho-Tanner Phase Transition ?

[Update 2: Don't read this entry. It is wrong. Like Google Instant, I get to screw up real time, very publicly and with no net. Oh well :-)]

[Update: I think part of the answer stems from the use of sparsity fraction in the y-axis where sparsity is divided by the number of measurements not the number of samples. Increasing the number of measurements, decreases the sparsity fraction] 

The Donoho-Tanner phase transition for space recovery is an important milestone. There are still some details that need to be cleared up in my mind. For instance, I have seen a paper a while back (that for reasons I cannot find again) that showed a slightly different line for the phase transition. As I was completing the phase transition page, I came across a presentation by Victoria Stodden [1] (Model Selection with Many More Variables than Observations) that connected back to this other result I had seen somewhere else. We all know by now the following figure (and it's connection to P vs NP)

But here is the graph that was a little surprising to me:

What's surprising you say ? well the fact that with very few measurements, high noise, a sparse signal can be found with an l_1 approach.

My intuition would have been that with a sizable amount of measurements, high noise, a  sparse solution could be found but no, this is not the case. So to summarize:

Below a certain (very small) number of measurements, the recovery of a sparse signal is possible provided enough noise but there is a limit in the number of measurements above which an l_1 recovery of that sparse solution will be precluded (because it is combinatorial).

One can always hope that the combinatorial solution near the phase transition has very low constants in the exponent.

Any comments are welcome.

Reference:

[1] Breakdown Point of Model Selection when the Number of Variables Exceeds the Number of Observations, Victoria Stodden,  David L. Donoho

CS: The other long entry of the week.

Stefan Schiffer just sent me the following:

 Dear Igor,

I just wanted to provide you another implementation for the Compressive Sensing: The Big Picture page. It implements the feature sign search algorithm presented in

Jin, Bangti, Lorenz, Dirk A., Schiffler, Stefan 2009: Elastic-Net Regularization: Error estimates and Active Set Methods. Inverse Problems 25/11, 115022 (26pp).

One must be careful if using function handles with it.

The code rfss.m is here. Thanks Stefan ! I'll add it to the Big Picture shortly.

So you expected to go home for the week-end with nothing to take home. Well I have a good news/bad news. The bad news is, there is plenty to read, the good news is that some of these papers are likely important to you. Enjoy!

In what is expected to have some major impact here is :Task-Driven Dictionary Learning by Julien Mairal, Francis Bach, Jean Ponce. The abstract reads:

Abstract: Modeling data with linear combinations of a few elements from a learned dictionary has been the focus of much recent research in machine learning, neuroscience and signal processing. For signals such as natural images that admit such sparse representations, it is now well established that these models are well suited to restoration tasks. In this context, learning the dictionary amounts to solving a large-scale matrix factorization problem, which can be done efficiently with classical optimization tools. The same approach has also been used for learning features from data for other purposes, e.g., image classification, but tuning the dictionary in a supervised way for these tasks has proven to be more difficult. In this paper, we present a general formulation for supervised dictionary learning adapted to a wide variety of tasks, and present an efficient algorithm for solving the corresponding optimization problem. Experiments on handwritten digit classification, digital art identification, nonlinear inverse image problems, and compressed sensing demonstrate that our approach is effective in large-scale settings, and is well suited to supervised and semi-supervised classification, as well as regression tasks for data that admit sparse representations.

High Range Resolution Profiling for Stepped-Frequency Radar with Sparse Reconstruction by Yang Hu, Yimin Liu, Huadong Meng. The abstract reads:

Abstract: The newly emerging theory of compressed sensing (CS) enables restore of a sparse signal from inadequate number of linear projections. Based on compressed sensing theory, a new strategy of high-resolution range profiling of stepped-frequency (SF) radar with missing pulses is proposed. If a certain part of received pulses are missing, we demonstrate the proposed method is capable of reconstructing target profile with high fidelity. MATLAB simulation results are presented to verify the proposed method. Furthermore, we use collected data from real SF radar to generate target high-resolution range profile (HRRP). Results are compared with traditional 'Stretch' method to prove its applicability.

Action recognition in video by sparse representation on covariance manifolds of silhouette tunnels by Kai Guo, Prakash Ishwar, and Janusz. Konrad, The abstract reads:

A novel framework for action recognition in video using empirical covariance matrices of bags of low-dimensional feature vectors is developed. The feature vectors are extracted from segments of silhouette tunnels of moving objects and coarsely capture their shapes. The matrix logarithm is used to map the segment covariance matrices, which live in a nonlinear Riemannian manifold, to the vector space of symmetric matrices. A recently developed sparse linear representation framework for dictionary-based classification is then applied to the log-covariance matrices. The log-covariance matrix of a query segment is approximated by a sparse linear combination of the log-covariance matrices of training segments and the sparse coefficients are used to determine the action label of the query segment. This approach is tested on the Weizmann and the UT-Tower human action datasets. The new approach attains a segment-level classification rate of 96.74% for the Weizmann dataset and 96.15% for the UT-Tower dataset. Additionally, the proposed method is computationally and memory efficient and easy to implement.

Action recognition using sparse representation on covariance manifolds of optical flow by Kai Guo, Prakash Ishwar, and Janusz. Konrad, The abstract reads:

A novel approach to action recognition in video based on the analysis of optical flow is presented. Properties of optical flow useful for action recognition are captured using only the empirical covariance matrix of a bag of features such as flow velocity, gradient, and divergence. The feature covariance matrix is a low-dimensional representation of video dynamics that belongs to a Riemannian manifold. The Riemannian manifold of covariance matrices is transformed into the vector space of symmetric matrices under the matrix logarithm mapping. The log-covariance matrix of a test action segment is approximated by a sparse linear combination of the log-covariance matrices of training action segments using a linear program and the coefficients of the sparse linear representation are used to recognize actions. This approach based on the unique blend of a logcovariance- descriptor and a sparse linear representation is tested on the Weizmann and KTH datasets. The proposed approach attains leave-one-out cross validation scores of 94.4% correct classification rate for the Weizmann dataset and 98.5% for the KTH dataset. Furthermore, the method is computationally efficient and easy to implement.

 The Action recognition page is here.

The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices by Zhouchen Lin, Minming Chen, Leqin Wu, Yi Ma. The abstract reads:

This paper proposes scalable and fast algorithms for solving the Robust PCA problem, namely recovering a low-rank matrix with an unknown fraction of its entries being arbitrarily corrupted. This problem arises in many applications, such as image processing, web data ranking, and bioinformatic data analysis. It was recently shown that under surprisingly broad conditions, the Robust PCA problem can be exactly solved via convex optimization that minimizes a combination of the nuclear norm and the $\ell^1$-norm . In this paper, we apply the method of augmented Lagrange multipliers (ALM) to solve this convex program. As the objective function is non-smooth, we show how to extend the classical analysis of ALM to such new objective functions and prove the optimality of the proposed algorithms and characterize their convergence rate. Empirically, the proposed new algorithms can be more than five times faster than the previous state-of-the-art algorithms for Robust PCA, such as the accelerated proximal gradient (APG) algorithm. Moreover, the new algorithms achieve higher precision, yet being less storage/memory demanding. We also show that the ALM technique can be used to solve the (related but somewhat simpler) matrix completion problem and obtain rather promising results too. Matlab code of all algorithms discussed are available at this http URL

Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming by Alexandre Belloni, Victor Chernozhukov, Lie Wang. The abstract reads:

We propose a pivotal method for estimating high-dimensional sparse linear regression models, where the overall number of regressors $p$ is large, possibly much larger than $n$, but only $s$ regressors are significant. The method is a modification of LASSO, called square-root LASSO. The method neither relies on the knowledge of the standard deviation $\sigma$ of the regression errors nor does it need to pre-estimate $\sigma$. Despite not knowing $\sigma$, square-root LASSO achieves near-oracle performance, attaining the convergence rate $\sigma \sqrt{(s/n)\log p}$, and thus matching the performance of the standard LASSO that knows $\sigma$. Moreover, we show that these results are valid for both Gaussian and non-Gaussian errors, under some mild moment restrictions, using moderate deviation theory. Finally, we formulate the square-root LASSO as a solution to a convex conic programming problem, which allows us to use efficient computational methods, such as interior point methods, to implement the estimator.

Morphological dilation image coding with context weights prediction by Jiaji Wu, Yan Xing, Anand Paul, Yong Fang, Jechang Jeong, Licheng Jiao, Guangming Shi. The abstract reads:

This paper proposes an adaptive morphological dilation image coding with context weights prediction. The new dilation method is not to use fixed models, but to decide whether a coefficient needs to be dilated or not according to the coefficient's predicted significance degree. It includes two key dilation technologies: 1) controlling dilation process with context weights to reduce the output of insignificant coefficients, and 2) using variable-length group test coding with context weights to adjust the coding order and cost as few bits as possible to present the events with large probability. Moreover, we also propose a novel context weight strategy to predict coefficient's significance degree more accurately, which serves for two dilation technologies. Experimental results show that our proposed method outperforms the state of the art image coding algorithms available today.

If option pricing models have sparse representations, what is incoherent with these functions ? well I am thinking too much ahead. Instead let us look at the sparse representation thingy: A reduced basis for option pricing by Rama Cont, Nicolas Lantos, Olivier Pironneau. The abstract reads:

We introduce a reduced basis method for the efficient numerical solution of partial integro-differential equations which arise in option pricing theory. Our method uses a basis of functions constructed from a sequence of Black-Scholes solutions with different volatilities. We show that this choice of basis leads to a sparse representation of option pricing functions, yielding an approximation whose precision is exponential in the number of basis functions. A Galerkin method using this basis for solving the pricing PDE is presented. Numerical tests based on the CEV diffusion model and the Merton jump diffusion model show that the method has better numerical performance relative to commonly used finite-difference and finite-element methods. We also compare our method with a numerical Proper Orthogonal Decomposition (POD). Finally, we show that this approach may be used advantageously for the calibration of local volatility functions.

Behind a paywall, we have the following:

Compressed sensing for chemical shift-based water–fat separation by  Mariya Doneva, Peter Börnert, Holger Eggers, Alfred Mertins, John Pauly, Michael Lustig. The abstract reads:

Multi echo chemical shift-based water–fat separation methods allow for uniform fat suppression in the presence of main field inhomogeneities. However, these methods require additional scan time for chemical shift encoding. This work presents a method for water–fat separation from undersampled data (CS-WF), which combines compressed sensing and chemical shift-based water–fat separation. Undersampling was applied in the k-space and in the chemical shift encoding dimension to reduce the total scanning time. The method can reconstruct high quality water and fat images in 2D and 3D applications from undersampled data. As an extension, multipeak fat spectral models were incorporated into the CS-WF reconstruction to improve the water–fat separation quality. In 3D MRI, reduction factors of above three can be achieved, thus fully compensating the additional time needed in three-echo water–fat imaging. The method is demonstrated on knee and abdominal in vivo data.

A novel memory-efficient fast algorithm for 2-D compressed sensing by Huiyuan Wang Vieira, Jose Jesus, Brun. The abstract reads:

The basic theories of compressed sensing (CS) turn around the sampling and reconstruction of 1-D signals. To deal with 2-D signals (images), the conventional treatment is to convert them into1-D vectors. This has drawbacks, including huge memory demands and difficulties in the design and calibration of the optical imaging systems. As a result, in 2009 some researchers proposed the concept of compressed imaging (CI) with separable sensing operators. However, their work is only focused on the sampling phase. In this paper, we propose a scheme for 2-D CS that is memory- and computation-efficient in both sampling and reconstruction. This is achieved by decomposing the 2-D CS problem into two stages with the help of an intermediate image. The intermediate image is then solved by direct orthogonal linear transform and the original image is reconstructed by solving a set of 1-D l1-norm minimization sub-problems. The experimental results confirm the feasibility of the proposed scheme.

Three dimension double inversion recovery gray matter imaging using compressed sensing by Gho SM, Nam Y, Zho SY, Kim EY, Kim DH. The abstract reads:

The double inversion recovery (DIR) imaging technique has various applications such as black blood magnetic resonance imaging and gray/white matter imaging. Recent clinical studies show the promise of DIR for high resolution three dimensional (3D) gray matter imaging. One drawback in this case however is the long data acquisition time needed to obtain the fully sampled 3D spatial frequency domain (k-space) data. In this paper, we propose a method to solve this problem using the compressed sensing (CS) algorithm with contourlet transform. The contourlet transform is an effective sparsifying transform especially for images with smooth contours. Therefore, we applied this algorithm to undersampled DIR images and compared with a CS algorithm using wavelet transform by evaluating the reconstruction performance of each algorithm for undersampled k-space data. The results show that the proposed CS algorithm achieves a more accurate reconstruction in terms of the mean structural similarity index and root mean square error than the CS algorithm using wavelet transform.

Credit: NASA

CS: A Q&A with Felix Herrmann, SMALLbox

I took the opportunity of Felix Herrmann sending me the job opportunities for graduate studentship and postdocs to ask a question destined for people on the applied side of things:.

Felix,

The question applies specifically to the applied folks. In most systems that are being solved, we somehow hope that the RIP or some such property holds for our system so we can get on the solving of actual problems. It's all great and fun to pretend that but in the end nobody is really convince of the matter.

So here are my questions: In order to be more convincing, have you tried to show that your systems followed the Donoho-Tanner phase transition ? in the negative, is it because of time constraints or something else ?

Felix kindly responded with:

Hi Igor,

....

I have always been a fan of the phase diagram by Donoho/Tanner because they capture the recovery conditions for typical sparse vectors and acquisition matrices. This means they are less pessimistic and they reflect practical situations better.

However, in my field we are confronted with problem sizes that make it impossible to compute complete phase diagrams. In addition, we are typically relying on redundant sparsifying transformations for which the theory is relatively under developed.

Having said this, I looked in a recent paper at the "oversampling ratio" between the percentage of coefficients required to get a particular nonlinear approximation error and the degree subsampling required to get the same error. I borrowed this idea from Mallat's book and adapted it to the seismic problem. In principle, this sort of thing is somewhat similar to phase diagrams and it gives some assurances but I am afraid maybe not the type of assurances acquisition practitioners are looking for.

While useful, the method I presented in the paper is expensive to compute and does not really lead to a workflow that would provide practical principles to design acquisition scenarios based on compressive sampling. For instance, I am not aware of practical (read computationally feasible and doable in the field) ways to do QC etc. So in summary, while CS provides beautiful insights I think we still have a long way to go to bring this technology into the main stream.

Thanks Felix !
 
The paper is: Randomized sampling and sparsity: getting more information from fewer samples by Felix Herrmann. The abstract reads:

Many seismic exploration techniques rely on the collection of massive data volumes that are subsequently mined for information during processing. While this approach has been extremely successful in the past, current efforts toward higher resolution images in increasingly complicated regions of the Earth continue to reveal fundamental shortcomings in our workflows. Chiefly amongst these is the so-called “curse of dimensionality” exemplified by Nyquist’s sampling criterion, which disproportionately strains current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. In this paper, we offer an alternative sampling method leveraging recent insights from compressive sensing towards seismic acquisition and processing for data that are traditionally considered to be undersampled. The main outcome of this approach is a new technology where acquisition and processing related costs are no longer determined by overly stringent sampling criteria, such as Nyquist. At the heart of our approach lies randomized incoherent sampling that breaks subsampling related interferences by turning them into harmless noise, which we subsequently remove by promoting transform-domain sparsity. Now, costs no longer grow significantly with resolution and dimensionality of the survey area, but instead depend on transform-domain sparsity only. Our contribution is twofold. First, we demonstrate by means of carefully designed numerical experiments that compressive sensing can successfully be adapted to seismic exploration. Second, we show that accurate recovery can be accomplished for compressively sampled data volumes sizes that exceed the size of conventional transform-domain data volumes by only a small factor. Because compressive sensing combines transformation and encoding by a single linear encoding step, this technology is directly applicable to acquisition and to dimensionality reduction during processing. In either case, sampling, storage, and processing costs scale with transform-domain sparsity. We illustrate this principle by means of number of case studies.

On a different note, the SMALLbox toolbox was announced at the LVA conference. From the twitter feed:

SMALLbox provides a common API for various sparsity toolboxes like sparco, sparselab, etc.

From the website:

Sparse Models, Algorithms, and Learning for

Large-scale data (SMALL)

SMALL will develop a new foundational framework for processing signals, using adaptive sparse structured representations.
A key discriminating feature of sparse representations, which opened up the horizons to new ways of thinking in signal processing including compressed sensing, has been the focus on developing reliable algorithms with provable performance and bounded complexity.

Yet, such approaches are simply inapplicable in many scenarios for which no suitable sparse model is known. Moreover, the success of sparse models heavily depends on the choice of a "dictionary" to reflect the natural structures of a class of data, but choosing a dictionary is currently something of an "art", using expert knowledge rather than automatically applicable principles. Inferring a dictionary from training data is key to the extension of sparse models for new exotic types of data.

SMALL will explore new generations of provably good methods to obtain inherently data-driven sparse models, able to cope with large-scale and complicated data much beyond state-of-the-art sparse signal modelling. The project will develop a radically new foundational theoretical framework for the dictionary-learning problem, and scalable algorithms for the training of structured dictionaries. SMALL algorithms will be evaluated against state-of-the art alternatives and we will demonstrate our approach on a range of showcase applications. We will organise two open workshops to disseminate our results and get feedback from the research community.

The framework will deeply impact the research landscape since the new models, approaches and algorithms will be generically applicable to a wide variety of signal processing problems, including acquisition, enhancement, manipulation, interpretation and coding. This new line of attack will lead to many new theoretical and practical challenges, with a potential to reshape both the signal processing research community and the burgeoning compressed sensing industry.

Credit: SpaceX, Test firing of a Merlin 1C regeneratively cooled rocket engine on a single engine vertical test stand at the SpaceX test facility in McGregor, Texas. The next Falcon flight will occur no earlier than November 8th.

CS: Hackaday and La Recherche

My submission to Hackaday on the EPFL ECG system caught on only because of the iPhone aspect of it.  It would not be so bad if somehow this explanation had not been inserted in the summary:

....Oh, and why the iPhone? The device that displays the data makes little difference. In this case they’re transmitting via Bluetooth for a real-time display (seen in the video after the break). This could be used for a wide variety of devices, or monitored remotely via the Internet....

Not only that, but since the explanation about compressed sensing was somehow removed from the description of the hardware, many commenters seem to think that the prototype was built only to appeal to the latest shiny new iPhone story. As Pierre confirmed last night on Twitter, the iPhone performs a full l_1 minimization with wavelet frames in real time! wow ! As far as I could understand from the presentaiton, the encoding is following that of Piotr and Radu). The comments in the Hackaday entry are generally very instructive on how to communicate with a technical crowd that has not been exposed to compressive sensing before..The trolls are part of that game. 

For our french readers, the October edition of La Recherche has a piece on Compressive Sensing on page 20-21 entitled "Des signaux comprimés à l'enregistrement" with an interview of Emmanuel. The MRI photo is from Pierre's lab. The article points to the Big Picture as a reference document, woohoo!