Dynamical Functional Theory for Compressed Sensing

Burak Cakmak; Manfred  Opper; Ole Winther; Bernard Henri Fleury

doi:10.1109/ISIT.2017.8006908

Dynamical Functional Theory for Compressed Sensing

Burak Cakmak, Manfred Opper, Ole Winther, Bernard Henri Fleury

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

10 Citations (Scopus)

326 Downloads (Pure)

Abstract

We introduce a theoretical approach for designing generalizations of the approximate message passing (AMP) algorithm for compressed sensing which are valid for large observation matrices that are drawn from an invariant random matrix ensemble. By design, the fixed points of the algorithm obey the Thouless Anderson-Palmer (TAP) equations corresponding to the ensemble. Using a dynamical functional approach we are able to derive an effective stochastic process for the marginal statistics of a single component of the dynamics. This allows us to design memory terms in the algorithm in such a way that the resulting fields become Gaussian random variables allowing for an explicit analysis. The asymptotic statistics of these fields are consistent with the replica ansatz of the compressed sensing problem.

Original language	English
Title of host publication	2017 IEEE International Symposium on Information Theory (ISIT)
Number of pages	5
Publisher	IEEE
Publication date	2017
Pages	2143-2147
ISBN (Electronic)	978-1-5090-4096-4
DOIs	https://doi.org/10.1109/ISIT.2017.8006908
Publication status	Published - 2017
Event	2017 IEEE International Symposium on Information Theory - Achen, Germany Duration: 25 Jun 2017 → 30 Jun 2017 https://isit2017.org/ https://isit2017.org/

Conference

Conference	2017 IEEE International Symposium on Information Theory
Country/Territory	Germany
City	Achen
Period	25/06/2017 → 30/06/2017
Internet address	https://isit2017.org/ https://isit2017.org/

Series	I E E E International Symposium on Information Theory. Proceedings
ISSN	2157-8095

Access to Document

10.1109/ISIT.2017.8006908

1570337496Final published version, 252 KB

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@inproceedings{549236a9fa4f4db98b71854f2a8d89b1,

title = "Dynamical Functional Theory for Compressed Sensing",

abstract = "We introduce a theoretical approach for designing generalizations of the approximate message passing (AMP) algorithm for compressed sensing which are valid for large observation matrices that are drawn from an invariant random matrix ensemble. By design, the fixed points of the algorithm obey the Thouless Anderson-Palmer (TAP) equations corresponding to the ensemble. Using a dynamical functional approach we are able to derive an effective stochastic process for the marginal statistics of a single component of the dynamics. This allows us to design memory terms in the algorithm in such a way that the resulting fields become Gaussian random variables allowing for an explicit analysis. The asymptotic statistics of these fields are consistent with the replica ansatz of the compressed sensing problem. ",

author = "Burak Cakmak and Manfred Opper and Ole Winther and Fleury, {Bernard Henri}",

year = "2017",

doi = "10.1109/ISIT.2017.8006908",

language = "English",

series = "I E E E International Symposium on Information Theory. Proceedings",

publisher = "IEEE",

pages = "2143--2147",

booktitle = "2017 IEEE International Symposium on Information Theory (ISIT)",

address = "United States",

note = "2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

url = "https://isit2017.org/, https://isit2017.org/",

}

Cakmak, B, Opper, M, Winther, O & Fleury, BH 2017, Dynamical Functional Theory for Compressed Sensing. in 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, I E E E International Symposium on Information Theory. Proceedings, pp. 2143-2147, 2017 IEEE International Symposium on Information Theory, Achen, Germany, 25/06/2017. https://doi.org/10.1109/ISIT.2017.8006908

Dynamical Functional Theory for Compressed Sensing. / Cakmak, Burak; Opper, Manfred ; Winther, Ole et al.
2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017. p. 2143-2147 (I E E E International Symposium on Information Theory. Proceedings).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Dynamical Functional Theory for Compressed Sensing

AU - Cakmak, Burak

AU - Opper, Manfred

AU - Winther, Ole

AU - Fleury, Bernard Henri

PY - 2017

Y1 - 2017

N2 - We introduce a theoretical approach for designing generalizations of the approximate message passing (AMP) algorithm for compressed sensing which are valid for large observation matrices that are drawn from an invariant random matrix ensemble. By design, the fixed points of the algorithm obey the Thouless Anderson-Palmer (TAP) equations corresponding to the ensemble. Using a dynamical functional approach we are able to derive an effective stochastic process for the marginal statistics of a single component of the dynamics. This allows us to design memory terms in the algorithm in such a way that the resulting fields become Gaussian random variables allowing for an explicit analysis. The asymptotic statistics of these fields are consistent with the replica ansatz of the compressed sensing problem.

AB - We introduce a theoretical approach for designing generalizations of the approximate message passing (AMP) algorithm for compressed sensing which are valid for large observation matrices that are drawn from an invariant random matrix ensemble. By design, the fixed points of the algorithm obey the Thouless Anderson-Palmer (TAP) equations corresponding to the ensemble. Using a dynamical functional approach we are able to derive an effective stochastic process for the marginal statistics of a single component of the dynamics. This allows us to design memory terms in the algorithm in such a way that the resulting fields become Gaussian random variables allowing for an explicit analysis. The asymptotic statistics of these fields are consistent with the replica ansatz of the compressed sensing problem.

U2 - 10.1109/ISIT.2017.8006908

DO - 10.1109/ISIT.2017.8006908

M3 - Article in proceeding

T3 - I E E E International Symposium on Information Theory. Proceedings

SP - 2143

EP - 2147

BT - 2017 IEEE International Symposium on Information Theory (ISIT)

PB - IEEE

T2 - 2017 IEEE International Symposium on Information Theory

Y2 - 25 June 2017 through 30 June 2017

ER -

Dynamical Functional Theory for Compressed Sensing

Abstract

Conference

Access to Document

AUB Link

Fingerprint

Cite this