Finite Sample Analysis of Approximate Message Passing Algorithms
dc.contributor.author  Rush, C  en 
dc.contributor.author  Venkataramanan, Ramji  en 
dc.date.accessioned  20181117T00:30:14Z  
dc.date.available  20181117T00:30:14Z  
dc.date.issued  20181101  en 
dc.identifier.issn  00189448  
dc.identifier.uri  https://www.repository.cam.ac.uk/handle/1810/285325  
dc.description.abstract  Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in highdimensional problems such as compressed sensing and lowrank 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 highdimensional regression, where the goal is to estimate a highdimensional vector $\beta_0$ from a noisy measurement $y=A \beta_0 + w$. AMP is a lowcomplexity, 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 nonasymptotic results for AMP in other settings such as lowrank matrix estimation.  
dc.publisher  IEEE  
dc.title  Finite Sample Analysis of Approximate Message Passing Algorithms  en 
dc.type  Article  
prism.endingPage  7286  
prism.issueIdentifier  11  en 
prism.publicationDate  2018  en 
prism.publicationName  IEEE Transactions on Information Theory  en 
prism.startingPage  7264  
prism.volume  64  en 
dc.identifier.doi  10.17863/CAM.32697  
dcterms.dateAccepted  20180306  en 
rioxxterms.versionofrecord  10.1109/TIT.2018.2816681  en 
rioxxterms.licenseref.uri  http://www.rioxx.net/licenses/allrightsreserved  en 
rioxxterms.licenseref.startdate  20181101  en 
dc.contributor.orcid  Rush, C [0000000168572855]  
dc.contributor.orcid  Venkataramanan, Ramji [0000000179155432]  
dc.identifier.eissn  15579654  
rioxxterms.type  Journal Article/Review  en 
pubs.funderprojectid  European Commission (631489)  
pubs.funderprojectid  EPSRC (EP/N013999/1)  
pubs.funderprojectid  Isaac Newton Trust (1540 (R))  
rioxxterms.freetoread.startdate  20191101 
Files in this item
This item appears in the following Collection(s)

Cambridge University Research Outputs
Research outputs of the University of Cambridge