Name
Title | ||
|---|---|---|
Statistical mechanical analysis of a typical reconstruction limit of compressed sensing |
Abstract | ||
|---|---|---|
We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing N-dimensional sparse vector x = (xi) from its linear transformation y = Fx of P dimensions on the basis of minimization of the Lp-norm ∥x∥p = lim∈→+0 ΣNi=1 |xi|p+∈. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio α = P/N and the density ρ of non-zero elements in x in the limit P, N → ∞ while keeping α ~ O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation αc(ρ) holds universally as long as FT F can be characterized asymptotically by a rotationally invariant random matrix ensemble and FFT is typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (Phil. Trans. R. Soc. A, vol. 367, pp. 4273-4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/ISIT.2010.5513526 | international symposium on information theory |
Keywords | DocType | Volume |
signal reconstruction,sparse matrices,statistical analysis,n-dimensional sparse vector reconstruction,asymptotically negligible reconstruction errors,compressed sensing reconstruction,compression matrices,linear transformation,nonzero elements density,rotationally invariant random matrix,statistical mechanical analysis,statistical mechanics,compressed sensing | Journal | abs/1001.4298 |
ISBN | Citations | PageRank |
978-1-4244-7891-0 | 7 | 0.59 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiyuki Kabashima | 1 | 136 | 27.83 |
| tadashi | 2 | 92 | 27.26 |
| Toshiyuki Tanaka | 3 | 255 | 23.32 |