Saturday, December 19, 2009

CS: Robust PCA, C-SALSA is released, KAUST Jobs

Manureva, the subject of this beautiful song (written by Serge Gainsbourg), was the name of a boat that disappeared one day to be never seen again. Jim Gray happens to be mentioned in today's breakthrough paper since data-intensive computing was advocated by him as the fourth paradigm for Scienti fic discovery. From this blog entry:

Amongst the many things that Jim talked about was the “Fourth Paradigm in Science”, the fact that scientific research has transitioned from “experimental” (thousands of years ago), to “theoretical” (few hundreds years ago), to “computational” (last few decades), to “data-intensive” (today).

The groundbreaking paper I am refering to is: Robust Principal Component Analysis? by Emmanuel Candes, Xiaodong Li, Yi Ma, and John Wright. The abstract reads:

This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the l_1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it o ers a principled way of removing shadows and specularities in images of faces.

Wow. I wonder how type of work will help in the dictionary learning ( see the presentation Dictionary learning for sparse representations using L1 minimization by Rémi Gribonval at MIA'09) and the calibration business. There is obviously some overlap with the background subtraction work of Volkan Cevher, Aswin Sankaranarayanan, Marco Duarte, Dikpal Reddy, Richard Baraniuk, and Rama Chellappa in Compressive sensing for background subtraction and now the question is, does this approach work well with compressed measurements ? I don't see why not as the compressed measurements are linear. I look forward to an implementation of this robust PCA algorithm.

While we are on the implementation of an algorithm, Mario Figueiredo just let me know of the release of C-SALSA mentioned earlier:

Hi Igor,

We have finally released our MATLAB implementation of C-SALSA,
which may be of interest to the CS community:

We have also released long versions of the papers describing SALSA and C-SALSA:
Thanks Mario ! I need to update the big picture in compressive sensing.

Finally, there are faculty OpeningS in Electrical Engineering at King Abdullah University of Science and Technology (KAUST). From the announcement:

KAUST invites applications for faculty positions in the area of Electrical Engineering. KAUST, located on the Red Sea coast of Saudi Arabia, is an international graduate-level research university dedicated to advancing science and technology through bold and collaborative research and to addressing challenges of regional and global significance, thereby serving the Kingdom, the region and the world. Newly opened in September 2009, KAUST is an independent and merit-based university and welcomes exceptional faculty, researchers and students from around the world. KAUST is committed to cutting-edge research in the globally significant areas of Energy, Water, and Food. In addition, KAUST emphasizes research on the discipline of Computational Science and Engineering serving as an enabling technology for all its research activities. KAUST invites applications for faculty position at all ranks in signal processing (with preference to bioinformatics, compressive sensing and/or image and video processing), information theory and coding (with preference to Genomics, and/or communication networks), Photonics and Optics (with preference to photonics materials and engineered photonic structures, metamaterials, plasmonics, integrated optics and optoelectronics, biophotonics, ultrafast photonics, and/or optical communications), and Electromagnetics (with preference to terahertz imaging, remote sensing, electromagnetic exploration, magneto-photonics, fundamentals of electromagnetic interaction, microwave photonics, and/or radiofrequency/microwave engineering). High priority will be given to the overall originality and promise of the candidate’s work rather than the candidate’s sub-area of specialization within Electrical Engineering.

The full announcement is here. It will be on the compressive sensing jobs page shortly.

No comments: