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.
Earlier papers; superceded:
- Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
S. Rangan, A. K. Fletcher, and V. K. Goyal, arXiv:0906.3234, 17 Jun 2009; revised 26 Aug 2009.
- Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing
S. Rangan, A. K. Fletcher, and V. K. Goyal, Proc. 23rd Ann. Conf. Neural Information Processing Systems (Vancouver, Canada), December 2009.
- Extensions of Replica Analysis to MAP Estimation with Applications to Compressed Sensing
S. Rangan, A. K. Fletcher, and V. K. Goyal, Proc. IEEE Int. Symp. Information Theory (Austin, TX), June 2010, pp. 1543-1547.
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.