2010/01/25 by Yoshiyuki Kabashima, Tadashi Wadayama, Kabashima, Yoshiyuki +3 · 1 citation
Engineering · Medicine · #Advanced MRI Techniques and Applications #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1001.4298
openalex publication_date 2010/01/25 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing N-dimensional sparse vector bx=(xi) from its linear transformation by=bF bx of P dimensions on the basis of minimization of the Lp-norm ||bx||p= limepsilon to +0 sumi=1N |xi|p+epsilon. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio alpha=P/N and the density rho of non-zero elements in bx in the limit P,,N to infty while keeping alpha sim O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation alphac(rho) holds universally as long as bFrm TbF can be characterized asymptotically by a rotationally invariant random matrix ensemble and bF bFrm T is typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (em Phil. Trans. R. Soc. A, vol.~367, pp.~4273--4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.