nips nips2009 nips2009-36 nips2009-36-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sundeep Rangan, Vivek Goyal, Alyson K. Fletcher
Abstract: The replica method is a non-rigorous but widely-accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to non-Gaussian maximum a posteriori (MAP) estimation. It is shown that with random linear measurements and Gaussian noise, the asymptotic behavior of the MAP estimate of an n-dimensional vector “decouples” as n scalar MAP estimators. The result is a counterpart to Guo and Verd´ ’s replica analysis of minimum mean-squared error estimation. u The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and zero norm-regularized estimation. In the case of lasso estimation the scalar estimator reduces to a soft-thresholding operator, and for zero normregularized estimation it reduces to a hard-threshold. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability.
[1] S. Rangan, A. K. Fletcher, and V. K. Goyal. Asymptotic analysis of MAP estimation via the replica method and applications to compressed sensing. arXiv:0906.3234v1 [cs.IT]., June 2009.
[2] S. F. Edwards and P. W. Anderson. Theory of spin glasses. J. Phys. F: Metal Physics, 5:965– 974, 1975.
[3] H. Nishimori. Statistical physics of spin glasses and information processing: An introduction. International Series of Monographs on Physics. Oxford Univ. Press, Oxford, UK, 2001.
[4] T. Tanaka. A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors. IEEE Trans. Inform. Theory, 48(11):2888–2910, November 2002.
[5] R. R. M¨ ller. Channel capacity and minimum probability of error in large dual antenna array u systems with binary modulation. IEEE Trans. Signal Process., 51(11):2821–2828, November 2003.
[6] D. Guo and S. Verd´ . Randomly spread CDMA: Asymptotics via statistical physics. IEEE u Trans. Inform. Theory, 51(6):1983–2010, June 2005.
[7] M. Talagrand. Spin Glasses: A Challenge for Mathematicians. Springer, New York, 2003.
[8] A. Montanari and D. Tse. Analysis of belief propagation for non-linear problems: The example of CDMA (or: How to prove Tanaka’s formula). arXiv:cs/0602028v1 [cs.IT]., February 2006.
[9] E. J. Cand` s, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruce tion from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489– 509, February 2006.
[10] D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306, April 2006.
[11] E. J. Cand` s and T. Tao. Near-optimal signal recovery from random projections: Universal e encoding strategies? IEEE Trans. Inform. Theory, 52(12):5406–5425, December 2006.
[12] B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM J. Computing, 24(2):227–234, April 1995.
[13] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM J. Sci. Comp., 20(1):33–61, 1999.
[14] R. Tibshirani. Regression shrinkage and selection via the lasso. J. Royal Stat. Soc., Ser. B, 58(1):267–288, 1996.
[15] D. L. Donoho, M. Elad, and V. N. Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory, 52(1):6–18, January 2006.
[16] J. A. Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inform. Theory, 50(10):2231–2242, October 2004.
[17] J. A. Tropp. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inform. Theory, 52(3):1030–1051, March 2006.
[18] M. J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ1 -constrained quadratic programming (lasso). IEEE Trans. Inform. Theory, 55(5):2183–2202, May 2009.
[19] D. L. Donoho and J. Tanner. Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Amer. Math. Soc., 22(1):1–53, January 2009. 9