Show simple item record

dc.contributor.authorRush, Cen
dc.contributor.authorVenkataramanan, Ramjien
dc.date.accessioned2018-11-17T00:30:14Z
dc.date.available2018-11-17T00:30:14Z
dc.date.issued2018-11-01en
dc.identifier.issn0018-9448
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/285325
dc.description.abstractApproximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in high-dimensional problems such as compressed sensing and low-rank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector $\beta_0$ from a noisy measurement $y=A \beta_0 + w$. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix $A$, AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with i.i.d. Gaussian measurement matrices with finite size $n \times N$. The result shows that the probability of deviation from the state evolution prediction falls exponentially in $n$. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations $t$ can grow no faster than order $\frac{\log n}{\log \log n}$ for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation.
dc.publisherIEEE
dc.titleFinite Sample Analysis of Approximate Message Passing Algorithmsen
dc.typeArticle
prism.endingPage7286
prism.issueIdentifier11en
prism.publicationDate2018en
prism.publicationNameIEEE Transactions on Information Theoryen
prism.startingPage7264
prism.volume64en
dc.identifier.doi10.17863/CAM.32697
dcterms.dateAccepted2018-03-06en
rioxxterms.versionofrecord10.1109/TIT.2018.2816681en
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2018-11-01en
dc.contributor.orcidRush, C [0000-0001-6857-2855]
dc.contributor.orcidVenkataramanan, Ramji [0000-0001-7915-5432]
dc.identifier.eissn1557-9654
rioxxterms.typeJournal Article/Reviewen
pubs.funder-project-idEuropean Commission (631489)
pubs.funder-project-idEPSRC (EP/N013999/1)
pubs.funder-project-idIsaac Newton Trust (1540 (R))
rioxxterms.freetoread.startdate2019-11-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record