Nuit Blanche Readers' Mailbag

I have been overcommited this past week on a number of things but here is the all important reader's mailbag entry of the week. But first let me ask a stupid question, has anybody tried to devise a sparse Randomized PCA algorithm ? If so I'd like to hear about it.

First let us start with Bob who found a mistake in one of the implementation of CoSAMP I link to. Bob seems to have corrected it:

Igor,

the code to which you link for CoSaMP here http://sites.google.com/site/igorcarron2/cscodes is not correct. The cosamp3.m looks better, but what is with the limit of the iterations to 101? I have included my corrected code here: 

http://media.aau.dk/null_space_pursuits/2011/07/algorithm-power-hour-compressive-sampling-matching-pursuit-cosamp.html

Thanks Bob, I'll change the page to forward to your blog on this topic. Let us note that his new blog is called: Pursuits in the Null Space

Bob's got other interesting entries ( I am hving some problems myself with the AMP one, maybe I should use GAMP:

• Algorithm Power Hour: Subspace Pursuit (SP)
• Algorithm Power Hour: Approximate Message Passing (AMP).

From: Daniel Reetz

Igor,

Thought you might enjoy this:
http://www.gizmag.com/pfca-tiny-lensless-camera/19134/

Best,
Daniel

Yes I did enjoy it, I'll probably come back to it later as it has some similarities with what I did this past week. Thanks Dan.

From Max Little:

Hi Igor

I've read your CS blog with much interest and enjoyment for a while now, thanks for the tidy summaries and links: very helpful!

I wanted to draw your attention to a recent two-part paper we just published which contains lots of new algorithms of relevance to CS:

http://rspa.royalsocietypublishing.org/content/early/2011/06/07/rspa.2010.0671.abstract

http://rspa.royalsocietypublishing.org/content/early/2011/06/07/rspa.2010.0674.abstract

The main idea is noise removal from piecewise constant signals, which is a hard signal processing problem of enduring interest (particular to computer vision). It turns out that CS-like techniques, e.g. L0 and L1-based optimization, as used in algorithms such as total variation denoising, are particularly useful for this problem. I've also released a Matlab library with fast implementations of many of these new solver algorithms:

http://www.maxlittle.net/software/pwctools.zip

Hope you and/or your readers find it interesting/useful!

Best wishes,

Max Little

Thanks Max. By looking at Max's page, it looks like a larger paper, that includes the two paper highlighted above, is: Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals by Max A. Little, Nick S. Jones. The abstract reads:

Removing noise from signals which are piecewise constant (PWC) is a challenging signal processing problem that arises in many practical scientific and engineering contexts. For example, in exploration geosciences, noisy drill hole records must be separated into constant stratigraphic zones, and in biophysics, the jumps between states and dwells of a molecular structure need to be determined from noisy fluorescence microscopy signals. This problem is one for which conventional linear signal processing methods are fundamentally unsuited. A wide range of PWC denoising methods exists, including total variation regularization, mean shift clustering, stepwise jump placement, running median filtering, convex clustering shrinkage, bilateral filtering, wavelet shrinkage and hidden Markov models. This paper builds on results from the image processing community to show that the majority of these algorithms, and more proposed in the wider literature, are each associated with a special case of a generalized functional, that, when minimized, solves the PWC denoising problem. We show how the minimizer can be obtained by a range of computational solver algorithms, including stepwise jump placement, quadratic or linear programming, finite differences with and without adaptive step size, iterated running medians, least angle regression, piecewise-linear regularization path following, or coordinate descent. Using this generalized functional, we introduce several novel PWC denoising methods, which, for example, combine the global behaviour of mean shift clustering with the local smoothing of total variation diffusion, and show example solver algorithms for these new methods. Head-to-head comparisons between these methods are performed on synthetic data, revealing that our new methods have a useful role to play. Finally, overlaps between the generalized methods of this paper and others such as wavelet shrinkage, hidden Markov models, and piecewise smooth filtering are touched on.

Credit: NASA. Patch of the last Space Shuttle flown into space (STS-135).