Saturday, July 09, 2011

ICASSP 2011 Videos and Papers on Compressive Sensing.

Laurent Duval reminded that I may not have covered the videos of ICASSP specifically on Compressive Sensing. Here they are at the end of this entry. In the meantime, Google found the following ICASSP papers:

Compressed Sensing and Sparse Representation of Signals

0:20:22
Added: 15. 6. 2011 06:31

BEATING NYQUIST THROUGH CORRELATIONS: A CONSTRAINED RANDOM DEMODULATOR FOR SAMPLING OF SPARSE BANDLIMITED SIGNALS

Compressed Sensing and Sparse Representation of Signals
Presented by: Andrew Harms
Author(s): Andrew Harms, Princeton University, United States; Waheed U. Bajwa, Robert Calderbank, Duke University, United States
0:19:20
Added: 15. 6. 2011 06:56

COMPRESSIVE SENSING FOR OVER-THE-AIR ULTRASOUND

Compressed Sensing and Sparse Representation of Signals
Presented by: Petros Boufounos
Author(s): Petros Boufounos, Mitsubishi Electric Research Laboratories, United States
0:18:33
Added: 15. 6. 2011 07:14

SPARSE SPECTRAL FACTORIZATION: UNICITY AND RECONSTRUCTION ALGORITHMS

Compressed Sensing and Sparse Representation of Signals
Presented by: Juri Ranieri
Author(s): Yue Lu, Harvard University, United States; Martin Vetterli, Ecole Polytechnique Fédérale de Lausanne, Switzerland
0:19:35
Added: 15. 6. 2011 07:00

RAND PPM : A LOW POWER COMPRESSIVE SAMPLING ANALOG TO DIGITAL CONVERTER

Compressed Sensing and Sparse Representation of Signals
Presented by: Praveen Kumar Yenduri
Author(s): Praveen Yenduri, Anna Gilbert, Michael Flynn, Shahrzad Naraghi, University of Michigan, United States
0:23:25
Added: 15. 6. 2011 07:27

INCOHERENT COLOR FRAMES FOR COMPRESSIVE DEMOSAICING

Compressed Sensing and Sparse Representation of Signals
Presented by: Hayder Radha
Author(s): Abdolreza Abdolhosseini Moghadam, Mohammad Aghagolzadeh, Michigan State University, United States; Mrityunjay Kumar, Eastman Kodak Company, United States; Hayder Radha, Michigan State University, United States
0:29:13
Added: 15. 6. 2011 07:49

IMPROVED THRESHOLDS FOR RANK MINIMIZATION

Compressed Sensing and Sparse Representation of Signals
Presented by: Babak Hassibi
Author(s): Samet Oymak, M. Amin Khajehnejad, Babak Hassibi, California Institute of Technology, United States



Compressed Sensing: Theory and Methods

0:19:55
Added: 22. 6. 2011 05:08

LORENTZIAN BASED ITERATIVE HARD THRESHOLDING FOR COMPRESSED SENSING

Compressed Sensing: Theory and Methods
Presented by: Rafael Carrillo
Author(s): Rafael Carrillo, Kenneth Barner, University of Delaware, United States
0:15:34
Added: 22. 6. 2011 03:51

SPARSITY-UNDERSAMPLING TRADEOFF OF COMPRESSED SENSING IN THE COMPLEX DOMAIN

Compressed Sensing: Theory and Methods
Presented by: Zai Yang
Author(s): Zai Yang, Cishen Zhang, Nanyang Technological University, Singapore
0:23:36
Added: 22. 6. 2011 04:37

GENERALIZED RESTRICTED ISOMETRY PROPERTY FOR ALPHA-STABLE RANDOM PROJECTIONS

Compressed Sensing: Theory and Methods
Presented by: Gonzalo R. Arce
Author(s): Daniel Otero, Gonzalo R. Arce, University of Delaware, Colombia
0:19:27
Added: 18. 6. 2011 15:22

COMPRESSED SENSING SIGNAL RECOVERY VIA A* ORTHOGONAL MATCHING PURSUIT

Compressed Sensing: Theory and Methods
Presented by: Nazim Burak Karahanoglu
Author(s): Nazim Burak Karahanoglu, TUBITAK - BILGEM, Turkey; Hakan Erdogan, Sabanci University, Turkey
0:19:49
Added: 22. 6. 2011 05:50

WEIGHTED COMPRESSED SENSING AND RANK MINIMIZATION

Compressed Sensing: Theory and Methods
Presented by: Babak Hassibi
Author(s): Samet Oymak, M. Amin Khajehnejad, Babak Hassibi, California Institute of Technology, United States
0:20:15
Added: 22. 6. 2011 03:53

LOW-RANK MATRIX COMPLETION WITH GEOMETRIC PERFORMANCE GUARANTEES

Compressed Sensing: Theory and Methods
Presented by: Wei Dai
Author(s): Wei Dai, Ely Kerman, Olgica Milenkovic, University of Illinois Urbana-Champaign, United States


Spectrum Sensing for Cognitive Radio

0:21:01
Added: 22. 6. 2011 01:34

DETECTION DIVERSITY OF MULTIANTENNA SPECTRUM SENSORS

Spectrum Sensing for Cognitive Radio
Presented by: Gonzalo Vazquez-Vilar
Author(s): Gonzalo Vazquez-Vilar, Roberto Lopez-Valcarce, University of Vigo, Spain; Ashish Pandharipande, Philips Research, Netherlands
0:20:10
Added: 21. 6. 2011 20:23

THE NON-BAYESIAN RESTLESS MULTI-ARMED BANDIT: A CASE OF NEAR-LOGARITHMIC REGRET

Spectrum Sensing for Cognitive Radio
Presented by: Qing Zhao
Author(s): Wenhan Dai, Tsinghua University, China; Yi Gai, Bhaskar Krishnamachari, University of Southern California, United States; Qing Zhao, University of California Davis, United States
0:19:23
Added: 22. 6. 2011 01:39

ON AUTOCORRELATION-BASED MULTIANTENNA SPECTRUM SENSING FOR COGNITIVE RADIOS IN UNKNOWN NOISE

Spectrum Sensing for Cognitive Radio
Presented by: Jitendra Tugnait
Author(s): Jitendra Tugnait, Auburn University, United States

Friday, July 08, 2011

The CLASH and ALPS reconstruction solvers

Volkan Cevher just sent me the following:

Hi Igor,

I hope things are going well.

I wanted to let you know of our new work the CLASH operator:


CLASH solves the Lasso problem *with hard thresholding.* So, it combines the geometrical properties of the ell1-ball with our model-based CS approach. The recovery results are quite encouraging. ...

The problem CLASH solves is quite similar to the problem Sina Jafarpour, Rob Schapire, and I are solving via game theoretic arguments. So, Sina and I will soon provide a comparison of the GAME algorithm and the CLASH on some real world problems involving face recognition.

By the way, I would appreciate if you could re-feature our ALPS codes (http://lions.epfl.ch/ALPS). We came up with some nice theory for step size selection etc., which makes the algorithms quite fast without sacrificing stability. My favorites are 1-ALPS(0) or 1-ALPS(2).

best,
Volkan


Volkan also let me know that the ICML slides corresponding to the CLASH algorithm will be put on the site in the near future. In the meantime, the description of CLASH reads:

CLASH: Combinatorial Selection and Least Absolute Shrinkage Algorithm 
CLASH (Combinatorial selection and Least Absolute SHrinkage) is a new sparse signal approximation algorithm that leverages prior information beyond sparsity to obtain approximate solutions to the Lasso problem. The algorithm is presented in "Combinatorial Selection and Least Absolute Shrinkage via the CLASH Algorithm", Technical Report, by Anastasios Kyrillidis and Volkan Cevher.

CLASH algorithm alters the selection process of Lasso algorithm by exploiting additional signal structure, dubbed as combinatorial sparsity model, and introduces approximate combinatorial selection with provable convergence guarantees.

More information can be found here. The solver can be downloaded here.

With regards to the ALPS solver, his favorites algorithms are mentioned in the description page here:

Description
ALPS (ALgebraic PursuitS) is a MATLAB implementation of a series of accelerated Iterative Hard Thresholding (IHT) methods for sparse signal reconstruction from dimensionality reducing, linear measurements.

ALPS includes three accelerated IHT methods designed to solve the following sparse linear regression problem:

where u is the M-tupled real valued observation vector, A is the MxN real measurement matrix (M less than N) and x is a K-sparse N-tuple vector signal.


Hard thresholding methods for sparse recovery
0-ALPS(#) is a memoryless IHT algorithm that uses an adaptive step size selection rule.
1-ALPS(#) employs memory for acceleration in addition to the adaptive step size selection. The algorithm uses a linear combination of past estimates during each iteration with a momentum term, which is automatically computed.
infinity-ALPS(#) uses a weighted sum of all the previously computed gradients during each iteration. The gradient weights are automatically calculated.
For all these schemes, we follow the naming convention [0,1,infinity]-ALPS(#), as described in "On Accelerated Hard Thresholding Methods for Sparse Approximation", where (#) is the binary number generated by the following options: SolveNewtonb, GradientDescentx, and SolveNewtonx. Please see the paper for their description.



Image Credit: NASA/Goddard Space Flight Center/Arizona State University, Sunrise on the Moon. On June 10, 2011, NASA's Lunar Reconnaissance Orbiter angled its orbit 65° to the west, allowing the spacecraft's cameras to capture a dramatic sunrise view of the moon's Tycho crater.

Thursday, July 07, 2011

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



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:

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:

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

Monday, July 04, 2011

Compressive Sensing Literature and More This Week

Much tweeting, blogging and literature this week. But first, Angshul Majumdar sent me the following:

Hi Igor

I have made some joint-sparse (MMV) reconstruction code available on Matlab Central. Here is the link

It contains functions for constrained and unconstrained algorithms for analysis and synthesis prior. Currently, the functions are for convex problem, but can be easily extended to the non-convex case.
Hope you find it useful :)

Angshul Majumdar

Thanks Angshul.

Pierre Vandergheynst tweets from FOCM on CS related matters.

In the comment section of one recent entry, Bob let us know that he blogged during SPARS, here are the entries:
Looks like some good discussions took place there. Of interest, Bob is opening a new blog called Null Space Pursuits. The RSS feed is here.


On Variable Density Compressive Sampling by Gilles Puy, Pierre Vandergheynst, and Yves Wiaux. The abstract reads:
Incoherence between sparsity basis and sensing basis is an essential concept for compressive sampling. In this context, we advocate a coherence-driven optimization procedure for variable density sampling. The associated minimization problem is solved by use of convex optimization algorithms. We also propose a refinement of our technique when prior information is available on the signal support in the sparsity basis. The effectiveness of the method is confirmed by numerical experiments. Our results also provide a theoretical underpinning to state-of-the-art variable density Fourier sampling procedures used in magnetic resonance imaging.
While Tibault Reveyrand  tweeted about this ICASSP paper:

We propose a compressive method for tracking doubly selective channels within multicarrier systems, including OFDMsystems. Using the recently introduced concept of modified compressed sensing (MOD-CS), the sequential delay-Doppler sparsity of the channel is exploited to improve estimation performance through a recursive estimation mode. The proposed compressive channel tracking algorithm uses a MOD-CS version of OMP with reduced complexity. Simulation results demonstrate substantial performance gains over
conventional compressive channel estimation.
I also found the following on the interweb:

The synthesis-based sparse representation model for signals has drawn a considerable interest in the past decade. Such a model assumes that the signal of interest can be decomposed as a linear combination of a {\em few} atoms from a given dictionary. In this talk we concentrate on an alternative, analysis-based model, where an analysis operator -- hereafter referred to as the "Analysis Dictionary" - multiplies the signal, leading to a sparse outcome. Our goal is to learn the analysis dictionary from a set of signal examples, and the approach taken is parallel and similar to the one adopted by the K-SVD algorithm that serves the corresponding problem in the synthesis model. We present the development of the algorithm steps, which include a tailored pursuit algorithm termed "Backward Greedy" algorithm and a penalty function for the dictionary update stage. We demonstrate its effectiveness in several experiments, treating synthetic data and real images, showing a successful and meaningful recovery of the analysis dictionary.

It's a little old: Compressive multiple view projection incoherent holography by  Adi Stern,. The abstract reads:
This Letter presents a new approach for imaging using a linear (vector) sensor. It exploits the fact that visual information within common human intelligible images may be compressed within only a partial set of radial strips of its Fourier domain. We present two imaging schemes, one coherent and the other incoherent, that capture the partial set of radial strips of the object Fourier domain. Two main advantages of the new approach are that the image is captured directly in a compressed form and that the acquisition time is shorter compared with conventional scanning imaging systems.
From Arxiv:

Compressed sensing (CS) is an emerging field that has attracted considerable research interest over the past few years. Previous review articles in CS limit their scope to standard discrete-to-discrete measurement architectures using matrices of randomized nature and signal models based on standard sparsity. In recent years, CS has worked its way into several new application areas. This, in turn, necessitates a fresh look on many of the basics of CS. The random matrix measurement operator must be replaced by more structured sensing architectures that correspond to the characteristics of feasible acquisition hardware. The standard sparsity prior has to be extended to include a much richer class of signals and to encode broader data models, including continuous-time signals. In our overview, the theme is exploiting signal and measurement structure in compressive sensing. The prime focus is bridging theory and practice; that is, to pinpoint the potential of structured CS strategies to emerge from the math to the hardware. Our summary highlights new directions as well as relations to more traditional CS, with the hope of serving both as a review to practitioners wanting to join this emerging field, and as a reference for researchers that attempts to put some of the existing ideas in perspective of practical applications.
Fast and Efficient Compressive Sensing using Structurally Random Matrices by Thong T. Do, Lu Gan, Nam H. Nguyen, Trac D. Tran. The abstract reads:
This paper introduces a new framework of fast and efficient sensing matrices for practical compressive sensing, called Structurally Random Matrix (SRM). In the proposed framework, we pre-randomize a sensing signal by scrambling its samples or flipping its sample signs and then fast-transform the randomized samples and finally, subsample the transform coefficients as the final sensing measurements. SRM is highly relevant for large-scale, real-time compressive sensing applications as it has fast computation and supports block-based processing. In addition, we can show that SRM has theoretical sensing performance comparable with that of completely random sensing matrices. Numerical simulation results verify the validity of the theory as well as illustrate the promising potentials of the proposed sensing framework

Coherence-Pattern Guided Compressive Sensing with Unresolved Grids by Albert Fannjiang, Wenjing Liao. The abstract reads:
Highly coherent sensing matrices arise in discretization of continuum imaging problems such as radar and medical imaging when the grid spacing is below the Rayleigh threshold. Algorithms based on techniques of band exclusion (BE) and local optimization (LO) are proposed to deal with such coherent sensing matrices. These techniques are embedded in the existing compressed sensing algorithms such as Orthogonal Matching Pursuit (OMP), Subspace Pursuit (SP), Iterative Hard Thresholding (IHT), Basis Pursuit (BP) and Lasso, and result in the modified algorithms BLOOMP, BLOSP, BLOIHT, BP-BLOT and Lasso-BLOT, respectively.
Under appropriate conditions, it is proved that BLOOMP can reconstruct sparse, widely separated objects up to one Rayleigh length in the Bottleneck distance {\em independent} of the grid spacing. One of the most distinguishing attributes of BLOOMP is its capability of dealing with large dynamic ranges.
The BLO-based algorithms are systematically tested with respect to four performance metrics: dynamic range, noise stability, sparsity and resolution. With respect to dynamic range and noise stability, BLOOMP is the best performer. With respect to sparsity, BLOOMP is the best performer for high dynamic range while for dynamic range near unity BP-BLOT and Lasso-BLOT with the optimized regularization parameter have the best performance. In the noiseless case, BP-BLOT has the highest resolving power up to certain dynamic range.
The algorithms BLOSP and BLOIHT are good alternatives to
BLOOMP and BP/Lasso-BLOT: they are faster than both BLOOMP and BP/Lasso-BLOT and shares, to a lesser degree, BLOOMP's amazing attribute with respect to dynamic range.
Detailed comparisons with existing algorithms such as Spectral Iterative Hard Thresholding (SIHT) and the frame-adapted BP are given.


Accelerated Linearized Bregman Method by Bo Huang, Shiqian Ma, Donald Goldfarb. The abstract reads:
In this paper, we propose and analyze an accelerated linearized Bregman (ALB) method for solving the basis pursuit and related sparse optimization problems. This accelerated algorithm is based on the fact that the linearized Bregman (LB) algorithm is equivalent to a gradient descent method applied to a certain dual formulation. We show that the LB method requires $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution and the ALB algorithm reduces this iteration complexity to $O(1/\sqrt{\epsilon})$ while requiring almost the same computational effort on each iteration. Numerical results on compressed sensing and matrix completion problems are presented that demonstrate that the ALB method can be significantly faster than the LB method.

Signal Compression in Wireless Sensor Networks by Marco F. Duarte, Godwin Shen, Antonio Ortega, and Richard Baraniuk. The abstract reads:
Signal compression is an important tool for reducing the communication costs and increasing the lifetime of wireless sensor network deployments. In this paper, we overview and classify an array of proposed compression methods, with an emphasis on illustrating the differences between the various approaches.

Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent by Feng Niu, Benjamin Recht, Christopher R e and Stephen J. Wright. The abstract reads:
Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking. We present an update scheme called Hogwild! which allows processors access to shared memory with the possibility of over- writing each other's work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then Hogwild! achieves a nearly optimal rate of convergence. We demonstrate experimentally that Hogwild! outperforms alternative schemes that use locking by an order of magnitude.




Many applications in cellular systems and sensor networks involve a random subset of a large number of users asynchronously reporting activity to a base station. This paper examines the problem of multiuser detection (MUD) in random access channels for such applications. Traditional orthogonal signaling ignores the random nature of user activity in this problem and limits the total number of users to be on the order of the number of signal space dimensions. Contention-based schemes, on the other hand, suffer from delays caused by colliding transmissions and the hidden node problem. In contrast, this paper presents a novel pairing of an asynchronous non-orthogonal code-division random access scheme with a convex optimization-based MUD algorithm that overcomes the issues associated with orthogonal signaling and contention-based methods. Two key distinguishing features of the proposed MUD algorithm are that it does not require knowledge of the delay or channel state information of every user and it has polynomial-time computational complexity. The main analytical contribution of this paper is the relationship between the performance of the proposed MUD algorithm in the presence of arbitrary or random delays and two simple metrics of the set of user codewords. The study of these metrics is then focused on two specific sets of codewords, random binary codewords and specially constructed algebraic codewords, for asynchronous random access. The ensuing analysis confirms that the proposed scheme together with either of these two codeword sets significantly outperforms the orthogonal signaling-based random access in terms of the total number of users in the system

Image Credit: NASA/JPL/Space Science Institute
N00173225.jpg was taken on June 26, 2011 and received on Earth June 27, 2011. The camera was pointing toward TITAN at approximately 2,873,752 kilometers away, and the image was taken using the CL1 and CB3 filters.

Friday, July 01, 2011

Sparse Modeling Software now Open Source !

Julien Mairal just sent me the following:

Hi Igor,

I just wanted to let you know that I have released the sources of my software SPAMS, under licence GPLv3. To summarize the content of the toolbox, it contains:
  • Numerous sparse solvers based on proximal methods, which can handle many regularization functions, (l0, l1, group Lasso, tree-structured group Lasso, tree-structured l0, overlapping group Lasso, total variation or fused Lasso), and numerous loss functions, (square, logistic, multiclass logistic), while providing duality gaps to control the convergence of algorithms. It also handles sparse matrices for large scale problems.
  • Coordinate descent and block-coordinate descent algorithm
  • Implementations of LARS and OMP, which to the best of my knowledge are the fastest available.
  • Dictionary learning and matrix factorization algorithms (NMF, sparse PCA...)
  • Fast projections algorithms onto some convex sets.
So far, I only provided binaries for Matlab, mainly for Linux computers. I hope this will be a good news for Mac, Windows users, which I hope will be able to compile it on these plateforms and benefit from the latest version!
This should be also possible to interface the toolbox with Python and R, but this will require additional work.

Best regards

Julien

Thanks Julien!


Image Credit: NASA/JPL/Space Science Institute
N00173231.jpg was taken on June 26, 2011 and received on Earth June 27, 2011. The camera was pointing toward TITAN at approximately 2,931,796 kilometers away, and the image was taken using the CL1 and CB3 filters. 

Thursday, June 30, 2011

ICASSP 2011 videos

Petros boufounos let us know on the twitter that the ICASSP 2011 videos of the talks given there are out on this site. Enjoy!

The Generalized Approximate Message Passing (GAMP) MATLAB package

Jort Gemmeke continues on providing us some information from SPARS11. Here is the latest refering to the last post about an implementation of the Approximate Message Passing (AMP). There is another, probably more sturdy and supported instance, the Generalized Approximate Message Passing (GAMP) MATLAB package:

Oops, missed this one somehow. Referred to in Volkan's oral presentation today.

http://gampmatlab.sourceforge.net

Jort

From the Gamp wiki:
Overview:   Generalized Approximate Message Passing (GAMP) is an approximate, but computationally efficient method for estimation problems withlinear mixing. In the linear mixing problem an unknown vector, LaTeX: \mathbf{x}, with independent components, is first passed through linear transform LaTeX: \mathbf{z}=\mathbf{A}\mathbf{x} and then observed through a general probabilistic, componentwise measurement channel to yield a measurement vector LaTeX: \mathbf{y}. The problem is to estimate LaTeX: \mathbf{x} and LaTeX: \mathbf{z} from LaTeX: \mathbf{y} and LaTeX: \mathbf{A}. This problem arises in a range of applications including compressed sensing.
Optimal solutions to linear mixing estimation problems are, in general, computationally intractable as the complexity of most brute force algorithms grows exponentially in the dimension of the vector LaTeX: \mathbf{x}. GAMP approximately performs the estimation through a Gaussian approximation of loopy belief propagation that reduces the vector-valued estimation problem to a sequence of scalar estimation problems on the components of the vectors LaTeX: \mathbf{x} and LaTeX: \mathbf{z}.
This project is intended to develop the theory and applications of GAMP. We also provide open source MATLAB software for others who would like to experiment with the algorithm.


The contributors of this fine package include:
  • Jason Parker, Ohio State
Thanks Jort.

Approximate Message Passing (AMP) Code for Compressive Sensing.

Jort Gemmeke sent me the following:

Hi Igor,

David Donoho had a nice plenary here at SPARS2011 about approximate message passing for CS. After a bit of googling the subject, I stumbled over a matlab solver. Although its a very simple algorithm, still nice that someone implemented it already...you can find it here:

http://people.epfl.ch/ulugbek.kamilov

Maybe something for your big picture pages? Unless I didn't look well enough, I didnt see it there.

Cheers,

Jort

Jort is right, it is not there. Ulugbek Kamilov did make available his code featuring the Approximate Message Passing (AMP) code and I will feature it soon in the big picture. Ulugbek Kamilov's master's Thesis is Optimal Quantization for Sparse Reconstruction with Relaxed Belief Propagation. The abstract of the thesis reads:

Compressive sensing theory has demonstrated that sparse signals can be recovered from a small number of random linear measurements. However, for practical purposes, like storage, transmission, or processing with modern digital equipment, continuous-valued compressive sensing measurements need to be quantized. In this thesis we examine the topic of optimal quantization of compressive sensing measurements under reconstruction with messagepassing algorithms by following the work on generalization of relaxed belief propagation (BP) for arbitrary measurement channels. Relaxed BP is an iterative reconstruction algorithm proposed for the task of estimation from random linear measurements. It was inspired by the traditional belief propagation algorithm widely used in decoding of low-density parity-check (LDPC) codes. One of the aspects that makes relaxed belief propagation so appealing is the state evolution framework, which predicts asymptotic error behavior of the algorithm. We utilize the predictive capability of the framework to design mean-square optimal scalar quantizers under relaxed BP signal reconstruction. We demonstrate that error performance of the reconstruction can be significantly improved by using state evolution optimized quantizers, compared to quantizers obtained via traditional design schemes. We finally propose relaxed BP as a practical algorithm for reconstruction from measurements digitized with binned quantizers, which further improve error performance of the reconstruction.

The attendant code for AMP and phase transition related computation is here. I just tried and compared it with SL0, a fast code on its own but relying on finding the SVD of a potentially large matrix and the results are indeed very impressive for a 1-d signal of size 100,000. The code I used:

clear
% Number of iterations of the algorithm
T = 1000;

% Stopping criterion (tolerance for successfull decoding)
tol = 1e-4;
m = 200;
k = 2;
N = 100000;

A = (1/sqrt(m)) .* randn(m, N);

% Sparse signal (with uniform distribution of non-zeros)
x = [sign(rand(k,1) - 0.5); zeros(N-k,1)];
x = x(randperm(N));

% Generate Measurements
y = A*x;
tstart = tic;
% Recover x using AMP
x1 = reconstructAmp(A, y, T, tol);
t_elapsed_AMP = toc(tstart)
sigma_min = 0.00004;
sdf=0.95;
tstart = tic;
x2= SL0(A, y, sigma_min,sdf);
t_elapsed_SL0 = toc(tstart)
figure(1)
plot(x1,'*')
figure(2)
plot(x2,'o')


The results read:

t_elapsed_AMP =

3.2762

t_elapsed_SL0 =

172.2139
Thanks Jort.

Wednesday, June 29, 2011

Multicore LASSO

Danny Bickson let me know the following about a recent blog entry:
Today we released very efficient multicore code for computing LASSO / sprase logistic regression, following our ICML paper. The code is called via a matlab wrapper.

Let us note the paper uses a battery of tests coming from compressive sensing. Thanks Danny! The project's page is here.

Printfriendly