Signal Transformation and Information Representation Group :: Professor Vivek K Goyal
[ home ]   [ research ]   [ teaching ]   [ publications ]   [ software ]   [ people ]   [ join]   [ funding ]   [ contact ]  


This entire web site is perpetually a work in progress, but this part is especially incomplete.  We will eventually post code related to some older projects including WEBRC multicast congestion control and a few techniques for multiple description coding.

Replica Method Analysis of Estimation Problems (Including Compressed Sensing)

We provided the first analytical framework to enable computation of the exact asymptotic performance of a large class of estimators, including the lasso estimator. This is based on generalizing Guo and Verdú's replica method analysis of high-dimensional estimation problems with linear mixing and additive white Gaussian noise.


  • As a visitor to the STIR group in Summer 2010, Aycan Corum wrote matlab code that is available for download here [zip file].  Please acknowledge use of this code through reference to this web page and citation of the first paper below.

Main paper:

Earlier papers; superceded:

Generalized Approximate Message Passing

Generalized Approximate Message Passing (GAMP) is a computationally-efficient approximate method for estimation problems with linear mixing. In the linear mixing problem an unknown vector x with independent components is first passed through linear transform z=Ax then observed through a general probabilistic, componentwise measurement channel to yield a measurement vector y. The problem is to estimate x and z from y and A. This problem arises in a range of applications including compressed sensing.  Optimal solutions to linear mixing estimation problems are, in general, computationally intractable since the complexity of most brute force algorithms grows exponentially in the dimension of the vector 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 x and z.


  • A sourceforge project gampmatlab allows public download of code.  Sundeep Rangan is the curator and main contributor.

Relevant papers:

home / research / teaching / publications / software / people / join / funding / contact © Massachusetts Institute of Technology
Link: Research Laboratory of Electronics at MIT Link: MIT