Friday, November 19, 2010

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):

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 \ell_1\ell_2 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
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

Thursday, November 18, 2010

CS: TFOCS (Templates for First-Order Conic Solvers) is out!, Itokawa's dust

This is nothing short of amazing, Hayabusa, the robotic equivalent to Apollo 13, a mission with a series of mishap has returned actual dust from an asteroid. Woohoo! Congratulations to the JAXA folks who made this happen. In a different direction, but equally exciting for us. Stephen Becker just sent me this:
Hi Igor,

We [ Michael Grant, Emmanuel Candes and Stephen Becker ] have a new first-order solver package for MATLAB, called TFOCS (Templates for First-Order Conic Solvers), that solves all the usual convex compressed-sensing problems, as well as matrix completion problems and variants. The package is designed to be modular, so that users can solve their own customized problems. For example, it is very easy to take the pre-built basis-pursuit solver that we provide, and modify it to add a constraint like x >= 0. The software can also handle complex numbers.

The code (free for all academics), paper and user guide are available at: http://tfocs.stanford.edu/

Because of the modular nature of the software, it is easy to change the first-order solver. We have included proximal gradient-descent, as well as 5 Nesterov-accelerated variants. Most importantly, we have put a lot of work into an efficient line search, so that supplying the Lipschitz bound if no longer necessary.


We're bringing this to your attention because we think readers of your blog will find it useful.

Cheers,
Stephen

Thanks Stephen.

The paper that introduced TFOCS is Templates for convex cone problems with applications to sparse signal recovery by S. Becker, E. J. Candès and M. Grant, Stanford University Technical Report, September 2010. The user guide is here.



Credit: JAXA, via
The Planetary Society Blog by Emily Lakdawalla

Wednesday, November 17, 2010

CS: Mallat's Invariants

Yesterday, I went to a presentation by Stephane Mallat on one of his most recent work focusing on defining a metric for objects such as images that go through some type of non-rigid deformation. In CS, we have elements of high dimensions that can be compared with the euclidian distance and for which one can apply random projections and expect similar neighborhood as in the original space.

But what happens when two objects of high dimensions are just a transformation of each other ? well not much as we rely on the euclidian distance in either the original space or in the reduced space provided by the random projections.

Mallat's approach is trying to give an answer to the following issue. Can we get a metric that allow objects that are deformation of each other to stay "close". For that he builds a nonlinear function called an invariant so that when the euclidian distance of two invariants of two very similar objects is performed, it is as close to zero as possible. For instance, the best known invariant for translation is the modulus of the Fourier transform  Things get sticky when we deal with non uniform translation as all bets are off now with the modulus of the Fourier transform. Mallat's provide his insight and how he builds his invariant function for translation in the following two videos and this presentation:
I wonder how we could build similar invariants for compressed sensing measurements (i,e random projections) or on compressive sensing hardware ? It would seem to be not possible as the reason Mallat uses complex wavelets is due to the need of avoiding singularities of the  modulus of the projected functions and projecting a function with random projections only brings out singularities. More on that later.

Tuesday, November 16, 2010

CS: Around the blogs in 80 hours and a review




Before we get to reading the blog entries of importance, here is the latest hack performing 3D Video Capture with the new Kinect.


Meena:
Bob:
Sarah:
John: Accelerated learning

ISW: Aptina Demos Wafer Level Camera Technology

Alex:
Greg: Paper posted to IEEE explorer: An Ultrawideband (UWB) Switched-Antenna-Array Radar Imaging System 

Suresh: All FOCS talks are online

Arthur: Generating a quasi Poisson distribution, version 2

Franck: Polynomial Learning of Distribution Families

Tara N. Sainath wrote in the SLTC Newsletter, November 2010 on Sparse Representations

Monday, November 15, 2010

CS: Threshold-ISD, Weak Compressed Sensing, Deterministic Matrices, Compressive auto-indexing in femtosecond nanocrystallography, randomized Hadamard transform, Compressive Sensing Microscope and more...

Yilun Wang sent me the following:
Dear Igor,

Wotao and I have developed an algorithm called ``Threshold-ISD'', which was once mentioned in a Nuit Blanche post.

The algorithm was published at SIAM Journal on Imaging Sciences, 2010, and the code was available online at http://www.caam.rice.edu/~optimization/L1/ISD/

Could you please put it on the your page of reconstruction technologies at http://sites.google.com/site/igorcarron2/cs#reconstruction?

We are expecting that more people can be aware of it, test it and give us more feedback in order to further improve it.

Thanks you very much.

Yilun

Thanks Yilun. I have added Threshold-ISD to the reconstruction section of the big picture as I should have done a long time ago. Since the last version was released in June 2010, I hope more people will look at it as it solves the interesting problem of performing the better reconstruction with the measurements you already have.

In a different direction, Do you recall the entry about weak compressive sensing ? Well it looks like I was borrowing the idea from different people to a certain extent. In particular from here: and here:
They both look at [A I] which seem to suggest that they follow the analysis of the Donoho-Tanner phase transition. Now an analysis needs to be performed on how \epsilon changes all that in [\epsilon*A   I].

There is a new version of Kronecker Compressive Sensing by Marco Duarte, and Richard Baraniuk.

I also found this new presentation entitled Large-Scale Structured Sparse Learning by Jieping Ye

Compressive auto-indexing in femtosecond nanocrystallography by Filipe R.N.C. Mai, Chao Yang and Stefano Marchesini. The abstract reads:
Ultrafast nanocrystallography has the potential to revolutionize biology by enabling structural elucidation of proteins for which it is possible to grow crystals with 10 or fewer unit cells on the side. The success of nanocrystallography depends on robust orientation-determination procedures that allow us to average diffraction data from multiple nanocrystals to produce a three-dimensional (3D) diffraction data volume with a high signal-to-noise ratio. Such a 3D diffraction volume can then be phased using standard crystallographic techniques. “Indexing” algorithms used in crystallography enable orientation determination of diffraction data from a single crystal when a relatively large number of reflections are recorded. Here we show that it is possible to obtain the exact lattice geometry from a smaller number of measurements than standard approaches using a basis pursuit solver.
Improved analysis of the subsampled randomized Hadamard transform by Joel Tropp. The abstract reads:
This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers---for the first time---optimal constants in the estimate on the number of dimensions required for the embedding.
I mentioned that paper  before and had some people comment it on the blog while Bob explained the paper a day later, but there is now a new version of it with an added author, here it is again: Compressed Sensing with Coherent and Redundant Dictionaries by Emmanuel Candes, Yonina Eldar, Deanna Needell, and Paige Randall. The abstract reads:
This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an `1-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the rst of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of `1-analysis for such problems.


The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.

Abstract. We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal nuclear norm and an approximatively low-rank solution. Under the assumption that the linear measurements ful ll a suitable generalization of the Null Space Property known in the context of compressed sensing, the algorithm is guaranteed to recover iteratively any matrix with an error of the order of the best k-rank approximation. In certain relevant cases, for instance for the matrix completion problem, our version of this algorithm can take advantage of the Woodbury matrix identity, which allows to expedite the solution of the least squares problems required at each iteration. We present numerical experiments which con rm the robustness of the algorithm for the solution of matrix completion problems, and demonstrate its competitiveness with respect to other techniques proposed recently in the literature.

I have put together a list of preprints and papers on deterministic measurement matrices for compressed sensing. It is here in the Deterministic Compressed Sensing page. There is a new contribution in this area: Deterministic Compressed Sensing Matrices from Multiplicative 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 paper, a $K imes N$ measurement matrix for compressed sensing is deterministically constructed via multiplicative character sequences. Precisely, a constant multiple of a cyclic shift of an $M$-ary power residue or Sidelnikov sequence is arranged as a column vector of the matrix, through modulating a primitive $M$-th root of unity. The Weil bound is then used to show that the matrix has asymptotically optimal coherence for large $K$ and $M$, and to present a sufficient condition on the sparsity level for unique sparse solution. Also, the restricted isometry property (RIP) is statistically studied for the deterministic matrix. Numerical results show that the deterministic compressed sensing matrix guarantees reliable matching pursuit recovery performance for both noiseless and noisy measurements.

In the Matlab Central library, here is a new benchmark for MRI :Compressed Sensing Phantom (v1.0) by David Smith:
Description

CSPHANTOM is a test phantom tailored to compressed sensing MRI algorithm development. It is designed to be non-sparse under a gradient transform and to contain features difficult to reproduce with partial Fourier sampling. We hope that this phantom can be used to evaluate the quality and accuracy of compressed sensing MRI reconstruction algorithms in the noise-free domain so that real-world applications of CS MRI may be improved.

In this paper we present the design and implementation of a Compressive Sensing Microscopy (CSM) imaging system, which uses the Compressive Sensing (CS) method to realize optical-sectioning imaging. The theoretical aspect of the proposed system is investigated using the mathematical model of the CS method and an experimental prototype is constructed to verify the CSM design. Compared to conventional optical-sectioning microscopes (such as Laser Scanning Confocal Microscopes (LSCMs) or Programmable Array Microscopes (PAMs)), the CSM system realizes optical-sectioning imaging using a single-pixel photo detector and without any mechanical scanning process. The complete information of the imaging scene is reconstructed from the CS measurements numerically.

Compressive sensing principles and iterative sparse recovery for inverse and ill-posed problems by Evelyn Herrholz and Gerd Teschke. The abstract reads:
In this paper, we are concerned with compressive sampling strategies and sparse recovery principles for linear inverse and ill-posed problems. As the main result, we provide compressed measurement models for ill-posed problems and recovery accuracy estimates for sparse approximations of the solution of the underlying inverse problem. The main ingredients are variational formulations that allow the treatment of ill-posed operator equations in the context of compressively sampled data. In particular, we rely on Tikhonov variational and constrained optimization formulations. One essential difference to the classical compressed sensing framework is the incorporation of joint sparsity measures allowing the treatment of infinite-dimensional reconstruction spaces. The theoretical results are furnished with a number of numerical experiments.

I just found the following on an extensive search on arxiv, CS is mentioned: An inverse problem for the wave equation with one measurement and the pseudorandom noise by Tapio Helin, Matti Lassas, Lauri Oksanen. The abstract reads:
We consider the wave equation $(\p_t^2-\Delta_g)u(t,x)=f(t,x)$, in $\R^n$, $u|_{\R_-\times \R^n}=0$, where the metric $g=(g_{jk}(x))_{j,k=1}^n$ is known outside an open and bounded set $M\subset \R^n$ with smooth boundary $\p M$. We define a deterministic source $f(t,x)$ called the pseudorandom noise as a sum of point sources, $f(t,x)=\sum_{j=1}^\infty a_j\delta_{x_j}(x)\delta(t)$, where the points $x_j,\ j\in\Z_+$, form a dense set on $\p M$. We show that when the weights $a_j$ are chosen appropriately, $u|_{\R\times \p M}$ determines the scattering relation on $\p M$, that is, it determines for all geodesics which pass through $M$ the travel times together with the entering and exit points and directions. The wave $u(t,x)$ contains the singularities produced by all point sources, but when $a_j=\lambda^{-\lambda^{j}}$ for some $\lambda>1$, we can trace back the point source that produced a given singularity in the data. This gives us the distance in $(\R^n, g)$ between a source point $x_j$ and an arbitrary point $y \in \p M$. In particular, if $(\bar M,g)$ is a simple Riemannian manifold and $g$ is conformally Euclidian in $\bar M$, these distances are known to determine the metric $g$ in $M$. In the case when $(\bar M,g)$ is non-simple we present a more detailed analysis of the wave fronts yielding the scattering relation on $\p M$.

Friday, November 12, 2010

Good Taste in All Manners this Month

Echoing last month's Good Taste In All Manners This Week., here is this month's list of sites from which readers came. The following pages and blogs link to or cited Nuit Blanche..

I hereby officially declare their authors to have good taste in all manners.

You can be on that distinguished list too! You know the drill:

In no particular order:

Latent Variable Analysis and Signal Separation / LVA2010 Videos

Prasad Sudhakar just sent me the following (Thanks to Laurent Duval for a similar e-mail ) about the videos made at the LVA 2010 meeting:

Dear Igor,

Here are the links to the videos and slides of keynote and panel sessions recorded at the LVA 2010 conference:

* Keynote Talk - When tensor decomposition meets compressed sensing, by Pierre Comon (CNRS, University of Nice, France)

* Keynote Talk - Discrimination with deformation for classification, by Stéphane Mallat (Ecole Polytechnique)

* Keynote Talk - Detecting DNA Strands in Multiplexed SERRS, by Mark Girolami (University of Glasgow, UK)

* Keynote Talk - 2nd order statistics + A 3rd data dimension = Just weight and see!, by Arie Yeredor (Tel-Aviv University, Israel)

* Panel session - Evaluation: SiSEC 2010 and remaining challenges, by Shoko Araki (NTT CS Labs, Japan),
Fabian Theis (Helmholtz Zentrum München, Germany), Guido Nolte (Fraunhofer Institute FIRST IDA, Germany)

Please click on the link above or visit the LVA 2010 web site:

The video of the Panel session on "The future of latent variable analysis and signal separation" will be released soon.

Best,
Prasad


Thanks Prasad and Laurent 

From the site:


pierre99half.jpgPierre Comon (CNRS, University of Nice, France): When tensor decomposition meets compressed sensing (video, slides)

Chair: Christian Jutten
Tensor decompositions have been increasingly used in Signal Processing during the last decade. In particular, Tucker and HOSVD decompositions are attractive for compression purposes, and the Canonical Polyadic decomposition (CP), sometimes referred to as Parafac, allows to restore identifiability in some Blind Identification problems, as pointed out already twenty years ago with the birth of Independent Component Analysis. There exist sufficient conditions under which the CP is essentially unique. These conditions have been first stated by Kruskal in the seventies, and impose a bound between tensor rank and the so-called k-rank of matrix factors, itself closely related to the notion of matrix spark used in Sparse Component Analysis. It is possible to relate this uniqueness condition to the so-called coherence condition obtained in the framework of compressed sensing. A computationally feasible variant of Kruskal’s uniqueness condition is obtained, where the coherence appears as a proxy for k-rank. Problems of sparsest recovery with infinite continuous dictionaries, lowest-rank tensor representation, and Blind Source Separation are addressed in a uniform fashion.
These statements are illustrated by an application in antenna array processing, namely blind localization and extraction of radiating sources from structured multiple antennas. With appropriate bounds on a certain distance between radiating sources, one can always guarantee the existence and uniqueness of a best rank-r approximation of a tensor, and hence of source estimates. 
Pierre Comon graduated in 1982, and received the Doctorate degree in 1985, both from the University of Grenoble, France. He later received the Habilitation to Lead Researches in 1995, from the University of Nice, France. He has been for nearly 13 years in industry, first with Crouzet-Sextant, Valence, France, between 1982 and 1985, and then with Thomson Marconi, Sophia-Antipolis, France, between 1988 and 1997. He spent 1987 with the ISL laboratory, Stanford University, CA. He joined in 1997 the Eurecom Institute, Sophia-Antipolis, France, and left during the fall of 1998. He is now research director with CNRS since 1998 at laboratory I3S, University of Nice Sophia-Antipolis, France, where he heads the Stic Doctoral School. His research interests include High-Order Statistics (HOS), Blind Deconvolution and Equalization, tensor-based Factor Analysis and Statistical Signal and Array Processing.
He was Associate Editor of the IEEE Transactions on Signal Processing from 1995 to 1998, and a member of the French National Committee of Scientific Research from 1995 to 2000. He was the coordinator of the European Basic Research Working Group on HOS "ATHOS", from 1992 to 1995. Between 1992 and 1998, he was a member of the Technical and Scientific Council of the Thomson Group. Between 2001 and 2004 he acted as launching Associate Editor with the IEEE Transactions on Circuits and Systems I, in the area of Blind Techniques. He is Fellow of the IEEE. He is now Associate Editor of the Elsevier journal Signal Processing.

Stéphane Mallat (Ecole Polytechnique, France): Discrimination and deformation estimation with recursive interferometry (video, slides)
Chair: Rémi Gribonval
Signals are often transformed by non-linear deformation operators, including non rigid translations, scalings and rotations for images. These operators belong to complex Lie groups and play the role of "unknown latent variables". Identifying deformations provides important information such as depth or velocity for images.
To classify signals despite unknown deformations, invariant representations have been studied in image and audio processing. We shall first review state of the art learning and computer vision approaches. They include wavelet transforms, deep learning neural network architectures, and histogram-based representations such as "bags of words" and SIFT.
The efficiency and limitations of these algorithms raise important representation issues. To answer these problems,we introduce a recursive interferometric transformation which builds nearly invariants descriptors of groups of deformations, while preserving necessary information to discriminate signals. Recursive interferometry linearizes non-linear deformations which are then calculated through solutions of multiple linear systems. Applications will be shown to discriminate and estimate the deformations of structured image patterns and random textures.
Stéphane Mallat was born in Paris, France. He received the Ph.D. degree in electrical engineering from the University of Pennsylvania, Philadelphia, in 1988. In 1988, he joined the Computer Science Department of the Courant Institue of Mathematical Sciences where he was Assoiate Professor in 1994 and Professsor in 1996. Since 1995, he has been a full Professor in the Applied Mathematics Department at Ecole Polytechnique, Paris. From 2001 to 2008 he was a co-founder and CEO of a start-up company.
Dr. Mallat is an IEEE fellow. He received the 1990 IEEE Signal Processing Society's paper award, the 1993 Alfred Sloan fellowship in Mathematics, the 1997 Outstanding Achievement Award from the SPIE Optical Engineering Society, the 1997 Blaise Pascal Prize in applied mathematics from the French Academy of Sciences, the 2004 European IST Grand Prize, the 2004 INIST-CNRS prize for most cited French researcher in engineering and computer science, and the 2007 IST Grand Pize of the French Academy of Sciences. His research interests include computer vision, signal processing and applied harmonic analysis.

Mark Girolami (University of Glasgow, UK): Bayesian non-negative matrix factorisation methods to detect dye labelled DNA oligonucleotides in multiplexed Raman spectra (video, slides)
Chair: Vincent Vigneron
Recent advances in the development of technology based on Raman scattering as a chemical analytical technique have made it possible to quantitatively detect spectral mixtures of multiple DNA sequences. However, to fully exploit these techniques inferential methodologies are required which can deconvolute the observed mixture and infer the composition of distinct DNA sequences present in the overall composite. Inferring the spectral decomposition is posed as a model selection problem for a non-negative bilinear statistical model, and the required Markov chain Monte Carlo inferential methodology is developed. In particular a Gibbs sampler and Reversible Jump Markov chain Monte Carlo methods are presented along with techniques based on estimation of the marginal likelihood. The results reported in this paper are particularly encouraging highlighting that for multiplexed Raman spectra, inference of the composition of original sequences present in the mixture is possible to acceptable levels of accuracy. This statistical methodology makes the exploitation of multiplexed surface enhanced resonance Raman scattering spectra in disease identification a reality.
Mark Girolami has been Professor of Computing & Inferential Science since 2006 at the University of Glasgow, where he holds a joint appointment in the Department of Computing Science and the Department of Statistics. He was awarded an EPSRC Advanced Research Fellowship in 2007. He obtained his PhD in 1998 with a thesis on Independent Component Analysis (ICA), and in 2009 he was awarded the SPIE Pioneer Award  for the impact his contributions to ICA have had on advancing neuro-imaging analysis technology. At Glasgow he leads the cross-disciplinary Inference Research Group (www.dcs.gla.ac.uk/inference) currently consisting of 17 researchers (8 Post Doctoral RAs and 9 PhD students) where the main focus of research is methodological development in statistical inference and machine learning with major applications in computational and systems biology. Other recent successful applications include statistical modeling of telecom fraud and counterfeit currency detection.
His research is funded by current grants from EPSRC, BBSRC, the British Heart Foundation, Microsoft Research Europe and various industrial collaborators. He is also co-investigator on a recently announced Cancer Research UK five year Programme Grant worth £1.5M. Along with UK based industrial collaborators he is an author of three international patents that have emerged from his research work. Girolami is a member of the EPSRC Peer Review College (2005–2010), he serves on the Medical Research Council (MRC) Bioinformatics Training Panel (2005–2010) and is an associate-editor for IEEE Trans Neural Networks and Pattern Recognition Letters. 

Arie Yeredor (Tel-Aviv University, Israel): 2nd order statistics + A 3rd data dimension = Just weight and see! (video, slides)

Chair: Fabian Theis
Although insufficient for separation in "classical" (temporally iid) ICA, second order statistics (SOS) can become a viable, and even optimal ICA tool when the sources exhibit temporal diversity. Asymptotic optimality can then be attained (for Gaussian sources) by full, proper exploitation of SOS. In a sense, early work on SOS-based separation (e.g., AMUSE, SOBI, TDSEP) exploited SOS only "half-way through", in forming the equations - but not in their ``weighting". Moreover, these methods only considered the particular case of stationary sources. Nonstationary sources were considered later on, but still only through particular cases, like block-stationarity or cyclostationarity.
In many cases of interest the sources are not stationary, nor do they take any particular form of non-stationarity. However, repeated experiments (different realizations sharing the same temporal covariance patterns) may be available, e.g., when synchronized to some external stimulus, such as in fMRI. The resulting data is three-dimensional (with an experiment-index dimension), allowing convenient estimation of the covariance patterns.
We shall show how to exploit the estimated SOS for asymptotic optimality (assuming Gaussian sources) in such cases. Maximum Likelihood (ML) separation will first be considered for the semi-blind case, with known covariance patterns. Then we shall show that asymptotically, there is no performance degradation in the ``fully-blind" case, when these covariance patterns are estimated from the data. Significant performance improvement over competing methods will be demonstrated, showing how the ML estimate can be interpreted as an optimally weighted set of least-squares equations.
Arie Yeredor received the B.Sc. (summa cum laude) and Ph.D. degrees in electrical engineering from Tel-Aviv University (TAU) in  1984 and 1997, respectively. Currently, he is with the Department of Electrical Engineering—Systems, School of Electrical Engineering, TAU, where he has been awarded the yearly Best Lecturer of the Faculty of Engineering Award five times. He also holds a consulting position with NICE Systems Inc., Ra’anana, Israel, in the fields of speech and audio processing, video processing, and emitter location algorithms.
Dr. Yeredor served as Associate Editor for the IEEE Signal Processing Letters and for the IEEE Transactions on Circuits and Systems—Part II: Express briefs, and he now serves as Associate Editor for the IEEE Transactions on Signal Processing and also as Technical Co-Chair of the 3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP'09 in Aruba). He is a member of the IEEE Signal Processing Society’s Signal Processing Theory and Methods (SPTM) Technical Committee. His research interests are in statistical signal processing (mainly BSS/ICA), sensor-array and multi-channel signal processing, estimation theory and linear-algebraic tools in signal processing.



Image Credit: NASA/JPL/Space Science Institute ,
N00164999.jpg was taken on October 31, 2010 and received on Earth November 08, 2010. The camera was pointing toward BERGELMIR, and the image was taken using the CL1 and CL2 filters.

Thursday, November 11, 2010

So you want to be a rocket scientist ? uh!



This week on the Robust Mathematical Modeling blog, I give the example of the modeling issues arising out of the thermal management design process used in spacecrafts, and yes rocket scientists are people too! they have complex models to do deal with. If you want to contribute a similar description of a specific domain in engineering or science where the three difficulties that are usually met in any real world project include: :
  • The data are missing or corrupted ;
  • The laws describing the phenomena are not completely known ;
  • The objectives are multiple and contradictory

then please contact me I could feature you in a future blog entry.

Wednesday, November 10, 2010

CS: A note on calibrating a Random Imager, Quantization using Compressive Sensing, Robust Matrix Decomposition with Outliers

One of the most intriguing instances of a compressive imager is the MIT Random Lens Imager (a paper that has never been published). The most interesting part of this paper is really putting in perspective the fact that compressed sensing enables a better calibration of a strange imager. But what could be considered strange you ask ? According to Mark Neifeld in a presentation made at the Duke-AFRL Meeting a year ago entitled Adaptation for Task-Specific Compressive Imaging , any imager could be considered strange::

Which is why yesterday's paper (Using Cloud Shadows to Infer Scene Structure and Camera Calibration by Nathan Jacobs, Brian Bies, Robert Pless.) on calibration is important. What is interesting there is that unlike most other calibration procedures where much attention goes in defining an exact target with known dimensions,


the authors take the view that enough observations should lead to a self consistent and, by the same token , a unique model that can easily map to the reality of the situation. Now the big question is finding out how  to compare two world views, and we are getting to an interesting although close to a philosophical problem. Sure enough, if you want your random imager to perform hyperspectral decomposition, you can check that easily but what about if you want your imager to catch only those parts of the scene that your brain will remember ten days from now, it's a different problem, it's a different  mapping. On a different note, I wonder how this approach would work on the photographs taken by our flight from a 120,000 feet high altitude balloon.  as one can clearly see the clouds moving (the camera is also moving albeit at a different speed)  For those of you interested in having an opportunity for a similar flight, you ought to get on the conference call with Greg Guzik on Friday, November 12, 2010 at 10:00 am (central time).

Today, we have two papers from arxiv:

Quantization using Compressive Sensing by Rajiv Soundararajan, Sriram Vishwanath. The abstract reads:
The problem of compressing a real-valued sparse source using compressive sensing techniques is studied. The rate distortion optimality of a coding scheme in which compressively sensed signals are quantized and then reconstructed is established when the reconstruction is also required to be sparse. The result holds in general when the distortion constraint is on the expected $p$-norm of error between the source and the reconstruction. A new restricted isometry like property is introduced for this purpose and the existence of matrices that satisfy this property is shown.
Robust Matrix Decomposition with Outliers by Daniel Hsu, Sham M. Kakade, Tong Zhang. The abstract reads:
Suppose a given observation matrix can be decomposed as the sum of a low-rank matrix and a sparse matrix (outliers), and the goal is to recover these individual components from the observed sum. Such additive decompositions have applications in a variety of numerical problems including system identification, latent variable graphical modeling, and principal components analysis. We study conditions under which recovering such a decomposition is possible via a combination of $\ell_1$ norm and trace norm minimization. We are specifically interested in the question of how many outliers are allowed so that convex programming can still achieve accurate recovery, and we obtain stronger recovery guarantees than previous studies. Moreover, we do not assume that the spatial pattern of outliers is random, which stands in contrast to related analyses under such assumptions via matrix completion.

Printfriendly